# Proposal: Add scan, takeWhile, dropWhile, and iterate to the stdlib

**URL:** <https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806>\
**Category:** Discussion\
**Created:** [December 28, 2015, 11:59pm UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806 "2015-12-28T23:59:30Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Lily\_Ballard](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lily_ballard/32/5050_2.png) [@Lily\_Ballard](https://forums.swift.org/u/Lily_Ballard)\
**Post date:** [December 28, 2015, 11:59pm UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/1 "2015-12-28T23:59:30Z")

</div>

## 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:

```swift
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:

```swift
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:

```swift
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

```swift
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)), ...]`.

---

<div class="post-metadata">

**Author:** ![SusanCheng](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/susancheng/32/9439_2.png) [@SusanCheng](https://forums.swift.org/u/SusanCheng)\
**Post date:** [December 29, 2015, 2:10pm UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/2 "2015-12-29T14:10:23Z")

</div>

Consider this:

```swift
extension CollectionType where Generator.Element : Equatable {
    /// Returns a subsequence, until a element equal to \`value\`, containing the
    /// initial elements.
    ///
    /// If none of elements equal to value, the result contains all
    /// the elements of self.
    ///
    /// - Complexity: O(self.count)
    @warn_unused_result
    public func prefixUntil(element: Self.Generator.Element) ->
Self.SubSequence {
        return self.prefixUpTo(self.indexOf(element) ?? self.endIndex)
    }
}

extension CollectionType {

    /// Returns a subsequence, until a element satisfying the predicate, containing the
    /// initial elements.
    ///
    /// If none of elements satisfying the predicate, the result contains all
    /// the elements of self.
    ///
    /// - Complexity: O(self.count)
    @warn_unused_result
    public func prefixUntil(@noescape predicate: (Self.Generator.Element) throws -> Bool) rethrows -> Self.SubSequence {
        return self.prefixUpTo(try self.indexOf(predicate) ?? self.endIndex)
    }
}

extension CollectionType where Generator.Element : Equatable, Index : BidirectionalIndexType {
    /// Returns a subsequence, until a element equal to value, containing the
    /// final elements of self.
    ///
    /// If none of elements equal to value, the result contains all
    /// the elements of self.
    ///
    /// - Complexity: O(self.count)
    @warn_unused_result
    public func suffixUntil(element: Self.Generator.Element) -> Self.SubSequence {
        return self.suffixFrom(self.reverse().indexOf(element)?.base ?? self.startIndex)
    }
}

extension CollectionType where Index : BidirectionalIndexType {
    /// Returns a subsequence, until a element satisfying the predicate, containing the
    /// final elements of self.
    ///
    /// If none of elements satisfying the predicate, the result contains all
    /// the elements of self.
    ///
    /// - Complexity: O(self.count)
    @warn_unused_result
    public func suffixUntil(@noescape predicate: (Self.Generator.Element) throws -&gt; Bool) rethrows -&gt; Self.SubSequence {
        return self.suffixFrom(try self.reverse().indexOf(predicate)?.base ?? self.startIndex)
    }
}

```

and here are my utilities: [https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Foundation.swift](https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Foundation.swift)

---

<div class="post-metadata">

**Author:** ![trs](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/trs/32/2038_2.png) [@trs](https://forums.swift.org/u/trs)\
**Post date:** [December 29, 2015, 9:55pm UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/3 "2015-12-29T21:55:50Z")

</div>

+1

---

<div class="post-metadata">

**Author:** ![Lily\_Ballard](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lily_ballard/32/5050_2.png) [@Lily\_Ballard](https://forums.swift.org/u/Lily_Ballard)\
**Post date:** [January 10, 2016, 12:20am UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/4 "2016-01-10T00:20:15Z")

</div>

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

```swift
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.

---

<div class="post-metadata">

**Author:** ![Lily\_Ballard](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lily_ballard/32/5050_2.png) [@Lily\_Ballard](https://forums.swift.org/u/Lily_Ballard)\
**Post date:** [January 10, 2016, 1:30am UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/5 "2016-01-10T01:30:22Z")

</div>

Proposal PR submitted as [Add scan, takeWhile, dropWhile, and iterate to the stdlib by lilyball · Pull Request #95 · apple/swift-evolution · GitHub](https://github.com/apple/swift-evolution/pull/95)

---

<div class="post-metadata">

**Author:** ![dabrahams](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/dabrahams/32/9815_2.png) [@dabrahams](https://forums.swift.org/u/dabrahams)\
**Post date:** [March 6, 2016, 5:38am UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/6 "2016-03-06T05:38:06Z")

</div>

> ## 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.

One of my concerns here is that while map, filter, and reduce are mostly  
“lingua franca” terms-of-art among programmers everywhere, these others  
are much less commonly-known and some of them aren't very descriptive of  
what they do. There are lots more like these in the FP lexicon. It was  
easy to draw the line at map/filter/reduce (which also don't follow the  
usual grammar for API guidelines), but if we take the ones in this  
proposal, where do we stop?

Because your PR has comments describing these methods (i.e. it's more  
complete) I'll leave further remarks there.

---

<div class="post-metadata">

**Author:** ![Adriano\_Ferreira](https://avatars.discourse-cdn.com/v4/letter/a/a3d4f5/32.png) [@Adriano\_Ferreira](https://forums.swift.org/u/Adriano_Ferreira)\
**Post date:** [January 7, 2016, 3:03pm UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/7 "2016-01-07T15:03:28Z")

</div>

+1

---

<div class="post-metadata">

**Author:** ![sethfri](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/sethfri/32/8680_2.png) [@sethfri](https://forums.swift.org/u/sethfri)\
**Post date:** [January 11, 2016, 5:48am UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/8 "2016-01-11T05:48:15Z")

</div>

I'm not familiar with any of the functions listed and would love to see  
more about them and their usefulness to Swift as part of the proposal.

Thanks!

Seth

---

<div class="post-metadata">

**Author:** ![John\_Randolph1](https://avatars.discourse-cdn.com/v4/letter/j/c67d28/32.png) [@John\_Randolph1](https://forums.swift.org/u/John_Randolph1)\
**Post date:** [January 14, 2016, 1:14am UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/9 "2016-01-14T01:14:28Z")

</div>

I’d like to see this functionality added, but I would suggest some different names. When Marcel Weiher wrote his paper on Higher-order Messaging in Objective-C (available here: [http://www.metaobject.com/papers/Higher\_Order\_Messaging\_OOPSLA\_2005.pdf](http://www.metaobject.com/papers/Higher_Order_Messaging_OOPSLA_2005.pdf)) He used “select”, “filter”, “each” and so on. To my eye, words like “takeWhile” in your proposal causes some confusion with an ordinary “while”.

If you change “dropWhile” and “takeWhile” to “filter” and “select”, it becomes much clearer, IMHO.

-jcr

---

<div class="post-metadata">

**Author:** ![Erica\_Sadun](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/erica_sadun/32/243_2.png) [@Erica\_Sadun](https://forums.swift.org/u/Erica_Sadun)\
**Post date:** [March 6, 2016, 4:48pm UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/10 "2016-03-06T16:48:51Z")

</div>

Let not to the adoption of great FP admit impediments \<[http://www.shakespeare-online.com/sonnets/116.html&gt;\](http://www.shakespeare-online.com/sonnets/116.html&gt;%5C).  
Names are not an ever-fixed mark that travels between languages  
and are never shaken. While map, filter, and reduce are  
terms of art, Swift offers new opportunities to incorporate  
other time tested FP with names better descriptive of what they do.  
If names be flawed, brief hours (or weeks) bikeshedding  
can be the wandering functions's guiding star  
moving them towards Swift's welcoming harbor.

-- E

---

<div class="post-metadata">

**Author:** ![trs](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/trs/32/2038_2.png) [@trs](https://forums.swift.org/u/trs)\
**Post date:** [March 6, 2016, 3:10pm UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/11 "2016-03-06T15:10:46Z")

</div>

> > ## 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.
> 
> One of my concerns here is that while map, filter, and reduce are mostly  
> “lingua franca” terms-of-art among programmers everywhere, these others  
> are much less commonly-known and some of them aren't very descriptive of  
> what they do. There are lots more like these in the FP lexicon. It was

I for one would love to see them added to the stdlib.

-Thorsten

---

<div class="post-metadata">

**Author:** ![Vincent\_Esche](https://avatars.discourse-cdn.com/v4/letter/v/b3f665/32.png) [@Vincent\_Esche](https://forums.swift.org/u/Vincent_Esche)\
**Post date:** [January 7, 2016, 5:43pm UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/12 "2016-01-07T17:43:25Z")

</div>

+1

- Vincent

---

<div class="post-metadata">

**Author:** ![sethfri](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/sethfri/32/8680_2.png) [@sethfri](https://forums.swift.org/u/sethfri)\
**Post date:** [January 11, 2016, 5:55am UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/13 "2016-01-11T05:55:37Z")

</div>

To clear my thoughts up a bit, that wasn't an "I'm too lazy to Google what  
these functions normally do" comment, but rather an "I believe proposals  
should provide as much context as possible about what you'd like to add  
along with the benefits of doing so" comment.

---

<div class="post-metadata">

**Author:** ![jtbandes](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jtbandes/32/463_2.png) [@jtbandes](https://forums.swift.org/u/jtbandes)\
**Post date:** [January 14, 2016, 1:16am UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/14 "2016-01-14T01:16:25Z")

</div>

They're different. We already have `filter` in stdlib; `takeWhile` is more like

```swift
var results: [Element] = []
for element in self {
    if !predicate(element) { break }
    results.append(element)
}
return results

```

Jacob Bandes-Storch

---

<div class="post-metadata">

**Author:** ![Lily\_Ballard](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lily_ballard/32/5050_2.png) [@Lily\_Ballard](https://forums.swift.org/u/Lily_Ballard)\
**Post date:** [January 11, 2016, 6:20am UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/15 "2016-01-11T06:20:00Z")

</div>

When the proposal is "we have a bunch of functions that match functions used in other languages, lets add a few more from the same category of functions that we missed", does there really need to be much explanation beyond "they're useful in the other languages that have them, they'd be useful for the same reasons in Swift"?

If requested, I can provide examples of usage. But if you're not already sold on the benefits of working with sequences in a functional manner, it's out of scope of the proposal to convince you of the merits of that style of programming. And if you are already sold on the benefits of doing so, then adding these functions shouldn't need much explanation.

Here's a few toy examples, if it helps:

```swift
// list of all powers of 2 below some limit
iterate(1, apply: { $0 * 2 }).takeWhile({ $0 < limit })

// first "word" of a string, skipping whitespace
let cs = NSCharacterSet.whitespaceCharacterSet()
String(str.unicodeScalars.skipWhile({ cs.longCharacterIsMember($0.value) })
                         .takeWhile({ !cs.longCharacterIsMember($0.value) }))

// running total of an array of numbers
numbers.scan(0, combine: +).dropFirst()

// infinite fibonacci sequence
iterate((0,1), apply: { ($1, $0+$1) }).lazy.map({$1})

```

---

<div class="post-metadata">

**Author:** ![sethfri](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/sethfri/32/8680_2.png) [@sethfri](https://forums.swift.org/u/sethfri)\
**Post date:** [January 11, 2016, 6:26am UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/16 "2016-01-11T06:26:16Z")

</div>

I wasn't suggesting you should convince the reviewers of the merits of  
functional style programming. I'm coming at it from the perspective of "Hey  
I'm not very familiar with functional style. What cool new things could  
these functions help me do if they're added to the stdlib?".

Not all of your reviewers are necessarily going to be familiar with these  
functions from other languages; I simply think more detail would make the  
proposal more compelling. Ultimately up to you.

Thanks,  
Seth

---

<div class="post-metadata">

**Author:** ![Chris\_Lattner](https://avatars.discourse-cdn.com/v4/letter/c/bc8723/32.png) [@Chris\_Lattner](https://forums.swift.org/u/Chris_Lattner)\
**Post date:** [January 12, 2016, 1:11am UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/17 "2016-01-12T01:11:13Z")

</div>

I agree with what you’re saying, but the flip-side is: how do we scope what we accept into the standard library? Just existing in some other language doesn’t mean that we should (automatically) accept new standard library functionality.

I’m not arguing for or against your proposal, just trying to say that this rationale isn’t enough to justify adding things to the Swift standard library.

-Chris

---

<div class="post-metadata">

**Author:** ![Dany\_St-Amant](https://avatars.discourse-cdn.com/v4/letter/d/9fc348/32.png) [@Dany\_St-Amant](https://forums.swift.org/u/Dany_St-Amant)\
**Post date:** [January 14, 2016, 1:54am UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/18 "2016-01-14T01:54:08Z")

</div>

The dropWhile sounds weird to me, I usually would see such functionality as a dropUntil; I discard stuff until I see what I want.  
Your example below doesn’t use dropWhile, but skipWhile; which sounds a bit better that dropWhile as one skip what he doesn’t want.

What do the other languages use? A dropWhile, skipWhile or dropUntil concept?

Dany

---

<div class="post-metadata">

**Author:** ![Lily\_Ballard](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lily_ballard/32/5050_2.png) [@Lily\_Ballard](https://forums.swift.org/u/Lily_Ballard)\
**Post date:** [January 11, 2016, 6:28am UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/19 "2016-01-11T06:28:08Z")

</div>

Sounds like you want usage examples, then. Are the ones I gave useful?

---

<div class="post-metadata">

**Author:** ![sethfri](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/sethfri/32/8680_2.png) [@sethfri](https://forums.swift.org/u/sethfri)\
**Post date:** [January 11, 2016, 6:38am UTC](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806/20 "2016-01-11T06:38:25Z")

</div>

Yes, thank you!

[Next page](https://forums.swift.org/t/proposal-add-scan-takewhile-dropwhile-and-iterate-to-the-stdlib/806.md?page=2)