[swift-evolution] Proposal: Add scan, takeWhile, dropWhile, and iterate to the stdlib

[Kevin Ballard]

Re-reading this proposal, I actually want to make a couple of changes. To better match the existing set of SequenceType methods, the extensions for dropWhile() and takeWhile() on SequenceType should in fact be members of the protocol that return Self.SubSequence, with default implementations provided that return AnySequence<Self.Generator.Element>. This matches how prefix(), dropFirst(), etc. are all handled.

The downside to this is any existing type that conforms to SequenceType but not CollectionType and that defines its SubSequence as anything other than AnySequence<Self.Generator.Element> will have to provide its own implementation of dropWhile() and takeWhile(). However, AFAIK in the stdlib every type that conforms to SequenceType also either conforms to CollectionType or leaves SubSequence at the default definition of AnySequence. And it's reasonable to assume that third-party code matches this behavior, because otherwise the third-party SequenceType has to implement a bunch of methods already like dropFirst() and prefix() that one does not normally expect third-party code to implement.

As such, the resulting API actually looks like

protocol SequenceType {
    // ...
    func dropWhile(@noescape dropElement: (Self.Generator.Element) throws -> Bool) rethrows -> Self.SubSequence
    func takeWhile(@noescape takeElement: (Self.Generator.Element) throws -> Bool) rethrows -> Self.SubSequence
}

extension SequenceType {
    func scan<T>(initial: T, @noescape combine: (T, Self.Generator.Element) throws -> T) rethrows -> [T]
    func dropWhile(@noescape dropElement: (Self.Generator.Element) throws -> Bool) rethrows -> AnySequence<Self.Generator.Element>
    func takeWhile(@noescape takeElement: (Self.Generator.Element) throws -> Bool) rethrows -> AnySequence<Self.Generator.Element>
}

The API on collectionType, LazySequenceType, and LazyCollectionType all remain the same.

-Kevin Ballard

On Mon, Dec 28, 2015, at 03:59 PM, Kevin Ballard wrote:
> ## Introduction
> 
> Add a few more functional sequence utilities to the standard library.
> 
> ## Motivation
> 
> We have map, filter, and reduce, but we're missing a bunch of useful utilities like scan, iterate, takeWhile, and dropWhile. Interestingly, the stdlib includes an implementation of scan in the doc comment for LazySequenceType, it just doesn't actually provide it as API.
> 
> ## Proposed solution
> 
> We extend SequenceType with 3 new methods scan, takeWhile, and dropWhile. We also add a single global function iterate.
> 
> ## Detailed design
> 
> We add the following extension to SequenceType:
> 
> extension SequenceType {
>     func scan<T>(initial: T, @noescape combine: (T, Self.Generator.Element) throws -> T) rethrows -> [T]
>     func dropWhile(@noescape dropElement: (Self.Generator.Element) throws -> Bool) rethrows -> [Self.Generator.Element]
>     func takeWhile(@noescape takeElement: (Self.Generator.Element) throws -> Bool) rethrows -> [Self.Generator.Element]
> }
> 
> These all take functions, so to follow convention they're @noescape and return arrays. We also provide an extension of CollectionType that overrides a couple of these methods:
> 
> extension CollectionType {
>     func dropWhile(@noescape dropElement: (Self.Generator.Element) throws -> Bool) rethrows -> Self.SubSequence
>     func takeWhile(@noescape takeElement: (Self.Generator.Element) throws -> Bool) rethrows -> Self.SubSequence
> }
> 
> We also provide lazy versions:
> 
> extension LazySequenceType {
>     func scan<T>(initial: T, combine: (T, Self.Generator.Element) -> T) -> LazyScanSequence<Self.Elements, T>
>     func dropWhile(dropElement: (Self.Generator.Element) -> Bool) -> LazyDropWhileSequence<Self.Elements>
>     func takeWhile(takeElement: (Self.Generator.Element) -> Bool) -> LazyTakeWhileSequence<Self.Elements>
> }
> 
> extension LazyCollectionType {
>     func dropWhile(dropElement: (Self.Generator.Element) -> Bool) -> LazyDropWhileCollection<Self.Elements>
>     func takeWhile(takeElement: (Self.Generator.Element) -> Bool) -> LazyTakeWhileCollection<Self.Elements>
> }
> 
> No collection variant of scan is provided because that would require storing the last value in the index itself, which would cause problems if the combine function isn't pure.
> 
> LazyDropWhileCollection would behave similarly to LazyFilterCollection in that it runs the predicate against the elements to drop when accessing startIndex; unlike LazyFilterCollection, because there's nothing else to skip after that point, the index itself can actually be Self.Elements.Index (just like a slice). LazyTakeWhileCollection also runs the predicate against the first element when accessing startIndex, but it does need a unique index type (because endIndex has to be some sentinel value, as it doesn't know where the end is until you reach that point; this index type would therefore only conform to ForwardIndexType).
> 
> And finally, we provide a global function
> 
> func iterate<T>(initial: T, _ f: T -> T) -> IterateSequence<T>
> 
> This function is inherently lazy and yields an infinite list of nested applications of the function, so iterate(x, f) yields a sequence like [x, f(x), f(f(x)), ...].
> 
> -Kevin Ballard