SE-0008: Add a Lazy flatMap for Sequences of Optionals #

Introduction ##

Currently, the Swift standard library has two versions of flatMap. One which flattens a sequence of sequences after a transformation:

[1, 2, 3]
  .flatMap { n in n..<5 } 
// [1, 2, 3, 4, 2, 3, 4, 3, 4]

And another which flattens a sequence of Optionals:

(1...10)
  .flatMap { n in n % 2 == 0 ? n/2 : nil }
// [1, 2, 3, 4, 5]

However, there is only a lazy implementation for the first version:

[1, 2, 3]
  .lazy
  .flatMap { n in n..<5 }
// LazyCollection<FlattenBidirectionalCollection<LazyMapCollection<Array<Int>, Range<Int>>>>

(1...10)
  .lazy
  .flatMap { n in n % 2 == 0 ? n/2 : nil }
// [1, 2, 3, 4, 5]

Swift Evolution Discussions: Lazy flatMap for Optionals, Review

Motivation ##

Seeing as the already-existing flatMap has a lazy version for nested sequences, a missing lazy version for sequences of Optionals seems like a gap. The usefulness of lazy sequences is well documented, especially when refactoring imperative nested for-loops into chains of methods, which can unnecessarily allocate intermediate arrays if done eagerly.

Proposed Approach ##

Making use of already-existing types in the standard library, flatMap's functionality can be achieved with a map-filter-map chain:

extension LazySequenceType {
  
  @warn_unused_result
  public func flatMap<T>(transform: Elements.Generator.Element -> T?)
    -> LazyMapSequence<LazyFilterSequence<LazyMapSequence<Elements, T?>>, T> {
      return self
        .map(transform)
        .filter { opt in opt != nil }
        .map { notNil in notNil! }
  }
}

Detailed Design ##

A version for LazyCollectionTypes is almost identical:

extension LazyCollectionType {
  
  @warn_unused_result
  public func flatMap<T>(transform: Elements.Generator.Element -> T?)
    -> LazyMapCollection<LazyFilterCollection<LazyMapCollection<Elements, T?>>, T> {
      return self
        .map(transform)
        .filter { opt in opt != nil }
        .map { notNil in notNil! }
  }
}

However, a "bidirectional" version cannot be written in this way, since no FilterBidirectionalCollection exists.

The other form of flatMap uses a flatten method on nested sequences, which has both a CollectionType form and a form for CollectionTypes with BidirectionalIndexTypes.

However, Swift's current type system doesn't allow a similar method to be defined on sequences of Optionals. This means we have to rely on filter, which only has a SequenceType and CollectionType implementation.

Alternatives considered ##

Custom struct ###

It would also be possible to add a new struct, and a method on LazySequenceType:

public struct FlatMapOptionalGenerator<G: GeneratorType, Element>: GeneratorType {
  private let transform: G.Element -> Element?
  private var generator: G
  public mutating func next() -> Element? {
    while let next = generator.next() {
      if let transformed = transform(next) {
        return transformed
      }
    }
    return nil
  }
}

public struct FlatMapOptionalSequence<S: LazySequenceType, Element>: LazySequenceType {
  private let transform: S.Generator.Element -> Element?
  private let sequence: S
  public func generate() -> FlatMapOptionalGenerator<S.Generator, Element> {
    return FlatMapOptionalGenerator(transform: transform, generator: sequence.generate())
  }
}

extension LazySequenceType {
  public func flatMap<T>(transform: Generator.Element -> T?) -> FlatMapOptionalSequence<Self, T> {
    return FlatMapOptionalSequence(transform: transform, sequence: self)
  }
}

However, this implementation does not have a LazyCollectionType version. To add one, and a bidirectional implementation, six new types (three SequenceTypes, three GeneratorTypes) would have to be added to the standard library.

New Filter struct ###

This would involve adding a FilterBidirectionalCollection to the standard library. Arguably, this is a gap currently. It would allow both flatMap versions to mirror each other, with minimal new types.

Make Optional Conform to SequenceType ###

This is a far-reaching, separate proposal, but it would solve the issue that this proposal seeks to solve. It's worth bearing in mind, though, that Optional probably wouldn't have a BidirectionalIndexType, so the bidirectional version of flatMap wouldn't exist on Optionals, anyway.