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


(Thorsten Seitz) #1

Wouldn’t droppingFirst() and droppingWhile() satisfy the naming conventions?

The downside is that these are a bit long.

My hesitation with “skip” is that I’m used to “skip” in the context of streams, not collections, i.e. where I’m forwarding a read position (or cursor) while ignoring the elements passed and not returning the rest.

-Thorsten

···

Am 22. Januar 2016 um 08:56 schrieb Kevin Ballard via swift-evolution swift-evolution@swift.org:

I’m tempted to say we should rename dropFirst() / dropWhile() to skipFirst() / skipWhile(), i.e. use Rust’s name, because “skip” doesn’t sound like a mutating verb but I do see why people say “drop” does. But yeah, that would be a different proposal entirely.

-Kevin Ballard

On Jan 21, 2016, at 5:02 PM, Andrew Bennett cacoyi@gmail.com wrote:

Great point Kevin, you’ve convinced me. I’m also happy with dropWhile for this reason. My issues with “drop” should be resolved in a separate proposal.

On Fri, Jan 22, 2016 at 11:17 AM, Kevin Ballard via swift-evolution swift-evolution@swift.org wrote:

I’m rather opposed to the idea of taking the methods that take indexes and overloading them to take predicates instead. They’re extremely different functionality. An index is a value that, once generated, is constant-time to use, and therefore the functions that take them are typically O(1). For example, CollectionType.suffixFrom() is documented explicitly as being O(1).

But functions taking a predicate must be O(N), because they have to evaluate the predicate on every element in turn until it returns true (or false, depending on the method in question).

So if we overload suffixFrom() to take a predicate, then we have one function with one overload that’s always O(1), and one overload that’s always O(N), and that is a great way to confuse people and hide performance issues.

This is also why I’m particularly fond of the takeWhile / dropWhile terminology. Besides the rather extensive precedent, the inclusion of the word “while” makes it clear that it’s iterating over the sequence/collection, which means it’s intuitively O(N).

-Kevin Ballard

On Thu, Jan 21, 2016, at 02:57 PM, David Smith wrote:

To be honest these all seem equally “weird” looking to me, so my hope is that it’s just a matter of familiarity :blush: My personal inclination is still that overloading suffixFrom with a predicate-taking variant is the way to go. That way it occupies the same mental slot as the existing suffixFrom method, and all you have to decide when using it is “do I want to specify where to suffix from, or how to find where to suffix from?”. e.g. it basically becomes sugar that turns

let idx = foo.indexOf { … }

let suffix = foo.suffixFrom(idx)

into

let suffix = foo.suffixFrom { … }

with the bonus feature that it works on single-pass sequences.

David

On Jan 13, 2016, at 11:52 PM, Kevin Ballard via swift-evolution swift-evolution@swift.org wrote:

“suffixAfter” sounds like the equivalent of dropFirst(_:), i.e. it sounds like it should take a count of elements to skip. Similarly, actually trying an expression that takes a predicate looks weird:

seq.suffixAfter({ isspace($0) })

Even knowing what it’s supposed to do, it’s hard for me to read that expression in any sensible fashion.

Also, I’m not sure the “noun phrase” convention really makes sense for SequenceType methods. They’re not technically mutating methods, but single-pass collections are in fact destructively mutated by Array-returning sequence methods (and the methods that return SubSequence also destructively mutate upon any access to the returned subsequence). Which is to say, despite not being marked as “mutating”, they do in fact behave like mutating methods for single-pass sequences. Which suggests that verb phrases are perfectly fine.

-Kevin Ballard

On Wed, Jan 13, 2016, at 08:36 PM, David Smith via swift-evolution wrote:

Rob Rix pointed out that “suffixAfter” would meet all my original criteria. Not sure if keeping the original “match the stuff to drop rather than the stuff to keep” semantics are critical, but this gives us an option for either way :blush:

David

On Jan 13, 2016, at 6:40 PM, David Smith via swift-evolution swift-evolution@swift.org wrote:

Naming conventions would suggest that something returning a new collection should be named with a noun phrase describing what it returns. Unfortunately, most of the ones I can think of off the top of my head are fairly clunky. “suffixFromFirstNonMatchingElement” describes what it does, but I haven’t thought of a non-painful way to say that yet. “suffixExcluding” is almost right, but it incorrectly implies (to my eye at least) that the returned collection excludes all elements matching the predicate, rather than just matching prefixes. Hm, what about flipping the predicate and getting a “suffixFrom” overload that takes a predicate for the first matching element to be included, rather than the last matching element to be excluded?

David

On Jan 13, 2016, at 5:54 PM, Dany St-Amant via swift-evolution swift-evolution@swift.org wrote:

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

Le 11 janv. 2016 à 01:20, Kevin Ballard via swift-evolution swift-evolution@swift.org a écrit :

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

// 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})

-Kevin Ballard

On Mon, Dec 28, 2015, at 03:59 PM, Kevin Ballard wrote:

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]

}


swift-evolution mailing list

swift-evolution@swift.org

https://lists.swift.org/mailman/listinfo/swift-evolution


swift-evolution mailing list

swift-evolution@swift.org

https://lists.swift.org/mailman/listinfo/swift-evolution


swift-evolution mailing list

swift-evolution@swift.org

https://lists.swift.org/mailman/listinfo/swift-evolution


swift-evolution mailing list

swift-evolution@swift.org

https://lists.swift.org/mailman/listinfo/swift-evolution


swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Lily Ballard) #2

I think it's more important here to be consistent with the existing
methods (e.g. use `dropWhile()` because we have `dropFirst()`) and any
renaming can be discussed as a separate proposal.

-Kevin Ballard

···

On Fri, Jan 22, 2016, at 04:17 AM, Thorsten Seitz wrote:

Wouldn't `droppingFirst()` and `droppingWhile()` satisfy the naming
conventions? The downside is that these are a bit long. My hesitation
with "skip" is that I'm used to "skip" in the context of streams, not
collections, i.e. where I'm forwarding a read position (or cursor)
while ignoring the elements passed and not returning the rest.

-Thorsten

Am 22. Januar 2016 um 08:56 schrieb Kevin Ballard via swift-evolution > <swift-evolution@swift.org>:

I’m tempted to say we should rename dropFirst() / dropWhile() to
skipFirst() / skipWhile(), i.e. use Rust’s name, because “skip”
doesn’t sound like a mutating verb but I do see why people say “drop”
does. But yeah, that would be a different proposal entirely.

-Kevin Ballard

On Jan 21, 2016, at 5:02 PM, Andrew Bennett <cacoyi@gmail.com> >>> wrote:

Great point Kevin, you've convinced me. I'm also happy with
`dropWhile` for this reason. My issues with "drop" should be
resolved in a separate proposal.

On Fri, Jan 22, 2016 at 11:17 AM, Kevin Ballard via swift-evolution >>> <swift-evolution@swift.org> wrote:

__
I'm rather opposed to the idea of taking the methods that take
indexes and overloading them to take predicates instead. They're
extremely different functionality. An index is a value that, once
generated, is constant-time to use, and therefore the functions
that take them are typically O(1). For example,
CollectionType.suffixFrom() is documented explicitly as being O(1).

But functions taking a predicate must be O(N), because they have to
evaluate the predicate on every element in turn until it returns
true (or false, depending on the method in question).

So if we overload suffixFrom() to take a predicate, then we have
one function with one overload that's always O(1), and one overload
that's always O(N), and that is a great way to confuse people and
hide performance issues.

This is also why I'm particularly fond of the takeWhile / dropWhile
terminology. Besides the rather extensive precedent, the inclusion
of the word "while" makes it clear that it's iterating over the
sequence/collection, which means it's intuitively O(N).

-Kevin Ballard

On Thu, Jan 21, 2016, at 02:57 PM, David Smith wrote:

To be honest these all seem equally "weird" looking to me, so my
hope is that it's just a matter of familiarity :blush: My personal
inclination is still that overloading suffixFrom with a predicate-
taking variant is the way to go. That way it occupies the same
mental slot as the existing suffixFrom method, and all you have to
decide when using it is "do I want to specify where to suffix
from, or how to find where to suffix from?". e.g. it basically
becomes sugar that turns

let idx = foo.indexOf { … } let suffix = foo.suffixFrom(idx)

into

let suffix = foo.suffixFrom { … }

with the bonus feature that it works on single-pass sequences.

David

On Jan 13, 2016, at 11:52 PM, Kevin Ballard via swift-evolution >>>>>> <swift-evolution@swift.org> wrote:

"suffixAfter" sounds like the equivalent of dropFirst(_:), i.e.
it sounds like it should take a count of elements to skip.
Similarly, actually trying an expression that takes a predicate
looks weird:

seq.suffixAfter({ isspace($0) })

Even knowing what it's supposed to do, it's hard for me to read
that expression in any sensible fashion.

Also, I'm not sure the "noun phrase" convention really makes
sense for SequenceType methods. They're not technically mutating
methods, but single-pass collections are in fact destructively
mutated by Array-returning sequence methods (and the methods that
return SubSequence also destructively mutate upon any access to
the returned subsequence). Which is to say, despite not being
marked as "mutating", they do in fact behave like mutating
methods for single-pass sequences. Which suggests that verb
phrases are perfectly fine.

-Kevin Ballard

On Wed, Jan 13, 2016, at 08:36 PM, David Smith via swift- >>>>>> evolution wrote:

Rob Rix pointed out that "suffixAfter" would meet all my
original criteria. Not sure if keeping the original "match the
stuff to drop rather than the stuff to keep" semantics are
critical, but this gives us an option for either way :blush:

David

On Jan 13, 2016, at 6:40 PM, David Smith via swift-evolution <swift- >>>>>>> evolution@swift.org> wrote:

Naming conventions would suggest that something returning a new
collection should be named with a noun phrase describing what
it returns. Unfortunately, most of the ones I can think of off
the top of my head are fairly clunky.
"suffixFromFirstNonMatchingElement" describes what it does, but
I haven't thought of a non-painful way to say that yet.
"suffixExcluding" is almost right, but it incorrectly implies
(to my eye at least) that the returned collection excludes all
elements matching the predicate, rather than just matching
prefixes. Hm, what about flipping the predicate and getting a
"suffixFrom" overload that takes a predicate for the first
matching element to be included, rather than the last matching
element to be excluded?

David

On Jan 13, 2016, at 5:54 PM, Dany St-Amant via swift-evolution >>>>>>>>> <swift-evolution@swift.org> wrote:

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

Le 11 janv. 2016 à 01:20, Kevin Ballard via swift-evolution >>>>>>>>>> <swift-evolution@swift.org> a écrit :

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

// 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(,
combine: +).dropFirst()

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

-Kevin Ballard

On Mon, Dec 28, 2015, at 03:59 PM, Kevin Ballard wrote:
>
> ## 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] }
>

_______________________________________________
swift-evolution mailing list swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_________________________________________________
swift-evolution mailing list swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Thorsten Seitz) #3

I agree.

-Thorsten

···

Am 22.01.2016 um 20:10 schrieb Kevin Ballard <kevin@sb.org>:

I think it's more important here to be consistent with the existing methods (e.g. use `dropWhile()` because we have `dropFirst()`) and any renaming can be discussed as a separate proposal.

-Kevin Ballard

On Fri, Jan 22, 2016, at 04:17 AM, Thorsten Seitz wrote:

Wouldn't `droppingFirst()` and `droppingWhile()` satisfy the naming conventions?
The downside is that these are a bit long.
My hesitation with "skip" is that I'm used to "skip" in the context of streams, not collections, i.e. where I'm forwarding a read position (or cursor) while ignoring the elements passed and not returning the rest.

-Thorsten

Am 22. Januar 2016 um 08:56 schrieb Kevin Ballard via swift-evolution <swift-evolution@swift.org>:

I’m tempted to say we should rename dropFirst() / dropWhile() to skipFirst() / skipWhile(), i.e. use Rust’s name, because “skip” doesn’t sound like a mutating verb but I do see why people say “drop” does. But yeah, that would be a different proposal entirely.

-Kevin Ballard

On Jan 21, 2016, at 5:02 PM, Andrew Bennett <cacoyi@gmail.com <mailto:cacoyi@gmail.com>> wrote:

Great point Kevin, you've convinced me. I'm also happy with `dropWhile` for this reason. My issues with "drop" should be resolved in a separate proposal.

On Fri, Jan 22, 2016 at 11:17 AM, Kevin Ballard via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

I'm rather opposed to the idea of taking the methods that take indexes and overloading them to take predicates instead. They're extremely different functionality. An index is a value that, once generated, is constant-time to use, and therefore the functions that take them are typically O(1). For example, CollectionType.suffixFrom() is documented explicitly as being O(1).

But functions taking a predicate must be O(N), because they have to evaluate the predicate on every element in turn until it returns true (or false, depending on the method in question).

So if we overload suffixFrom() to take a predicate, then we have one function with one overload that's always O(1), and one overload that's always O(N), and that is a great way to confuse people and hide performance issues.

This is also why I'm particularly fond of the takeWhile / dropWhile terminology. Besides the rather extensive precedent, the inclusion of the word "while" makes it clear that it's iterating over the sequence/collection, which means it's intuitively O(N).

-Kevin Ballard

On Thu, Jan 21, 2016, at 02:57 PM, David Smith wrote:

To be honest these all seem equally "weird" looking to me, so my hope is that it's just a matter of familiarity :blush: My personal inclination is still that overloading suffixFrom with a predicate-taking variant is the way to go. That way it occupies the same mental slot as the existing suffixFrom method, and all you have to decide when using it is "do I want to specify where to suffix from, or how to find where to suffix from?". e.g. it basically becomes sugar that turns

let idx = foo.indexOf { … }
let suffix = foo.suffixFrom(idx)

into

let suffix = foo.suffixFrom { … }

with the bonus feature that it works on single-pass sequences.

David

On Jan 13, 2016, at 11:52 PM, Kevin Ballard via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

"suffixAfter" sounds like the equivalent of dropFirst(_:), i.e. it sounds like it should take a count of elements to skip. Similarly, actually trying an expression that takes a predicate looks weird:

    seq.suffixAfter({ isspace($0) })

Even knowing what it's supposed to do, it's hard for me to read that expression in any sensible fashion.

Also, I'm not sure the "noun phrase" convention really makes sense for SequenceType methods. They're not technically mutating methods, but single-pass collections are in fact destructively mutated by Array-returning sequence methods (and the methods that return SubSequence also destructively mutate upon any access to the returned subsequence). Which is to say, despite not being marked as "mutating", they do in fact behave like mutating methods for single-pass sequences. Which suggests that verb phrases are perfectly fine.

-Kevin Ballard

On Wed, Jan 13, 2016, at 08:36 PM, David Smith via swift-evolution wrote:

Rob Rix pointed out that "suffixAfter" would meet all my original criteria. Not sure if keeping the original "match the stuff to drop rather than the stuff to keep" semantics are critical, but this gives us an option for either way :blush:

    David

On Jan 13, 2016, at 6:40 PM, David Smith via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Naming conventions would suggest that something returning a new collection should be named with a noun phrase describing what it returns. Unfortunately, most of the ones I can think of off the top of my head are fairly clunky. "suffixFromFirstNonMatchingElement" describes what it does, but I haven't thought of a non-painful way to say that yet. "suffixExcluding" is almost right, but it incorrectly implies (to my eye at least) that the returned collection excludes all elements matching the predicate, rather than just matching prefixes. Hm, what about flipping the predicate and getting a "suffixFrom" overload that takes a predicate for the first matching element to be included, rather than the last matching element to be excluded?

David

On Jan 13, 2016, at 5:54 PM, Dany St-Amant via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

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

Le 11 janv. 2016 à 01:20, Kevin Ballard via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> a écrit :

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

// 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})

-Kevin Ballard

On Mon, Dec 28, 2015, at 03:59 PM, Kevin Ballard wrote:
>
> ## 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]
> }
>

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution