Proposal: Add SequenceType.first


(Lily Ballard) #1

It's sometimes useful to get the first element of a sequence. To that
end I'd like to propose

extension SequenceType {

/// Returns the first element of `self`, or `nil` if `self` is empty.

/// - Complexity: O(1)

var first: Self.Generator.Element? {

var gen = generate()

return gen.next()

}

}

I think it makes sense to add this property to the definition of
SequenceType as well, so various sequences can override it to avoid
constructing a generator.

With this added to SequenceType, we can remove it from CollectionType,
as the behavior will be the same.

-Kevin Ballard


Does this type satisfy the requirements of Sequence and IteratorProtocol?
(Daniel Duan) #2

Users who don’t get the single-pass nature of SequenceType may expect a .last as well.

···

On Dec 30, 2015, at 3:57 PM, Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:

It's sometimes useful to get the first element of a sequence. To that end I'd like to propose

extension SequenceType {
    /// Returns the first element of `self`, or `nil` if `self` is empty.
    /// - Complexity: O(1)
    var first: Self.Generator.Element? {
        var gen = generate()
        return gen.next()
    }
}

I think it makes sense to add this property to the definition of SequenceType as well, so various sequences can override it to avoid constructing a generator.

With this added to SequenceType, we can remove it from CollectionType, as the behavior will be the same.

-Kevin Ballard

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


(Dave Abrahams) #3

Property accesses should not mutate the receiver, and because of how Sequences work, inspecting first may consume the first element. I suggest you consider adding a BufferedSequence<Base: SequenceType> that has a stable first property (at least until it is iterated)

Another related adapter I’d like to add is a model of CollectionType that is backed by a sequence and lazily populated in fixed-sized chunks.

-Dave

···

On Dec 30, 2015, at 3:57 PM, Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:

It's sometimes useful to get the first element of a sequence. To that end I'd like to propose

extension SequenceType {
    /// Returns the first element of `self`, or `nil` if `self` is empty.
    /// - Complexity: O(1)
    var first: Self.Generator.Element? {
        var gen = generate()
        return gen.next()
    }
}

I think it makes sense to add this property to the definition of SequenceType as well, so various sequences can override it to avoid constructing a generator.

With this added to SequenceType, we can remove it from CollectionType, as the behavior will be the same.


#4

Hello,

My two cents: I feel uncomfortable with SequenceType.first since SequenceType clearly states that it may be destructed on iteration.

Compare :

seq.generate().next() // clear that it may give another result if called twice
seq.first // unclear that it may give another result if called twice

Gwendal

···

Le 31 déc. 2015 à 00:57, Kevin Ballard via swift-evolution <swift-evolution@swift.org> a écrit :

It's sometimes useful to get the first element of a sequence. To that end I'd like to propose

extension SequenceType {
    /// Returns the first element of `self`, or `nil` if `self` is empty.
    /// - Complexity: O(1)
    var first: Self.Generator.Element? {
        var gen = generate()
        return gen.next()
    }
}

I think it makes sense to add this property to the definition of SequenceType as well, so various sequences can override it to avoid constructing a generator.

With this added to SequenceType, we can remove it from CollectionType, as the behavior will be the same.

-Kevin Ballard

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


(Lily Ballard) #5

We already don't have a .last on CollectionType and nobody's been
complaining about that. Besides, sequences don't necessarily even
terminate.

-Kevin Ballard

···

On Wed, Dec 30, 2015, at 04:01 PM, Daniel Duan wrote:

Users who don’t get the single-pass nature of SequenceType may expect
a .last as well.

On Dec 30, 2015, at 3:57 PM, Kevin Ballard via swift-evolution <swift- >> evolution@swift.org> wrote:

It's sometimes useful to get the first element of a sequence. To that
end I'd like to propose

extensionSequenceType { /// Returns the first element of
`self`, or `nil` if `self` is empty. /// - Complexity: O(1) var
first: Self.Generator.Element? { var gen = generate() return
gen.next() } }

I think it makes sense to add this property to the definition of
SequenceType as well, so various sequences can override it to avoid
constructing a generator.

With this added to SequenceType, we can remove it from
CollectionType, as the behavior will be the same.

-Kevin Ballard

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


(Lily Ballard) #6

It's sometimes useful to get the first element of a sequence. To that
end I'd like to propose

extensionSequenceType { /// Returns the first element of
`self`, or `nil` if `self` is empty. /// - Complexity: O(1) var
first: Self.Generator.Element? { var gen = generate() return
gen.next() } }

I think it makes sense to add this property to the definition of
SequenceType as well, so various sequences can override it to avoid
constructing a generator.

With this added to SequenceType, we can remove it from
CollectionType, as the behavior will be the same.

Property accesses should not mutate the receiver, and because of how
Sequences work, inspecting first may consume the first element.

Fair enough. Swift does support `mutating get`, but it looks like the
stdlib doesn't actually use this anywhere (at least, in the public API).

Still, it's a shame that there's no way to do this generically for
sequences. It's something I need upon occasion. I wish I could actually
say something like `seq.generate().next()`, but you can't call mutating
functions on temporaries.

I'd be tempted to say we should have a `func first()` method, except
then CollectionTypes would have both a property and a method named
`first` and that would just be confusing.

I suggest you consider adding a BufferedSequence<Base: SequenceType>
that has a stable first property (at least until it is iterated)

Good idea, though I'd probably call it PeekSequence because it would
only buffer a single element (and BufferedSequence sounds like it's got
an arbitrary-sized buffer). Perhaps more useful would be the associated
PeekGenerator, because peek() is a useful thing to have when writing
custom generator-using code.

I'll write up a more detailed email with a proposed design in a minute.

Another related adapter I’d like to add is a model of
CollectionType that is backed by a sequence and lazily populated in
fixed-sized chunks.

Also a good idea. Although really it could just be backed by a
ContiguousArray, those things already grow in chunks. I'll write up a
design for that too.

-Kevin Ballard

···

On Thu, Dec 31, 2015, at 12:36 AM, Dave Abrahams wrote:

On Dec 30, 2015, at 3:57 PM, Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:


#7

Generator should always generates value from start of sequence. I don't see
any problems with this implementation.

Dave Abrahams via swift-evolution <swift-evolution@swift.org> 於
2015年12月31日星期四 寫道:

···

On Dec 30, 2015, at 3:57 PM, Kevin Ballard via swift-evolution < > swift-evolution@swift.org > <javascript:_e(%7B%7D,'cvml','swift-evolution@swift.org');>> wrote:

It's sometimes useful to get the first element of a sequence. To that end
I'd like to propose

extension SequenceType {
    /// Returns the first element of `self`, or `nil` if `self` is empty.
    /// - Complexity: O(1)
    var first: Self.Generator.Element? {
        var gen = generate()
        return gen.next()
    }
}

I think it makes sense to add this property to the definition of
SequenceType as well, so various sequences can override it to avoid
constructing a generator.

With this added to SequenceType, we can remove it from CollectionType, as
the behavior will be the same.

Property accesses should not mutate the receiver, and because of how
Sequences work, inspecting first may consume the first element. I suggest
you consider adding a BufferedSequence<Base: SequenceType> that has a
stable first property (at least until it is iterated)

Another related adapter I’d like to add is a model of CollectionType that
is backed by a sequence and lazily populated in fixed-sized chunks.

-Dave


(Daniel Duan) #8

Here it is https://github.com/apple/swift/blob/master/stdlib/public/core/CollectionAlgorithms.swift.gyb#L26

···

On Dec 30, 2015, at 4:27 PM, Kevin Ballard <kevin@sb.org> wrote:

We already don't have a .last on CollectionType and nobody's been complaining about that. Besides, sequences don't necessarily even terminate.

-Kevin Ballard

On Wed, Dec 30, 2015, at 04:01 PM, Daniel Duan wrote:

Users who don’t get the single-pass nature of SequenceType may expect a .last as well.

On Dec 30, 2015, at 3:57 PM, Kevin Ballard via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

It's sometimes useful to get the first element of a sequence. To that end I'd like to propose

extensionSequenceType {
/// Returns the first element of `self`, or `nil` if `self` is empty.
/// - Complexity: O(1)
var first: Self.Generator.Element? {
var gen = generate()
return gen.next()
    }
}

I think it makes sense to add this property to the definition of SequenceType as well, so various sequences can override it to avoid constructing a generator.

With this added to SequenceType, we can remove it from CollectionType, as the behavior will be the same.

-Kevin Ballard

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


(Dave Abrahams) #9

It's sometimes useful to get the first element of a sequence. To that end I'd like to propose

extensionSequenceType {
/// Returns the first element of `self`, or `nil` if `self` is empty.
/// - Complexity: O(1)
var first: Self.Generator.Element? {
var gen = generate()
return gen.next()
    }
}

I think it makes sense to add this property to the definition of SequenceType as well, so various sequences can override it to avoid constructing a generator.

With this added to SequenceType, we can remove it from CollectionType, as the behavior will be the same.

Property accesses should not mutate the receiver, and because of how Sequences work, inspecting first may consume the first element.

Fair enough. Swift does support `mutating get`, but it looks like the stdlib doesn't actually use this anywhere (at least, in the public API).

Still, it's a shame that there's no way to do this generically for sequences. It's something I need upon occasion. I wish I could actually say something like `seq.generate().next()`, but you can't call mutating functions on temporaries.

I'd be tempted to say we should have a `func first()` method, except then CollectionTypes would have both a property and a method named `first` and that would just be confusing.

I suggest you consider adding a BufferedSequence<Base: SequenceType> that has a stable first property (at least until it is iterated)

Good idea, though I'd probably call it PeekSequence because it would only buffer a single element (and BufferedSequence sounds like it's got an arbitrary-sized buffer). Perhaps more useful would be the associated PeekGenerator, because peek() is a useful thing to have when writing custom generator-using code.

The size of the buffer is an implementation detail, and I don’t find “peek” descriptive.

I'll write up a more detailed email with a proposed design in a minute.

Another related adapter I’d like to add is a model of CollectionType that is backed by a sequence and lazily populated in fixed-sized chunks.

Also a good idea. Although really it could just be backed by a ContiguousArray, those things already grow in chunks. I'll write up a design for that too.

Not unless you want to keep the buffers alive longer than necessary. Imagine you’re parsing a long stream with some amount of lookahead. You can scan this collection by slicing it and the buffer segments that are no longer in use will be automatically collected.

-Kevin Ballard

-Dave

···

On Dec 31, 2015, at 1:58 PM, Kevin Ballard <kevin@sb.org> wrote:
On Thu, Dec 31, 2015, at 12:36 AM, Dave Abrahams wrote:

On Dec 30, 2015, at 3:57 PM, Kevin Ballard via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:


#10

Consider this,

struct RandomGenerator : GeneratorType, SequenceType {

    mutating func next() -> UInt32? {

        return arc4random()

    }

}

what's the expected result of follows??

let random = RandomGenerator()

let resultA = random.first

let resultB = random.first

let resultC = Array(random.prefix(4))

let resultD = Array(random.prefix(4))

all should agree that resultC and resultD will get different array. what's
about with resultA and resultB?

Gwendal Roué <gwendal.roue@gmail.com> 於 2016年1月2日 下午8:13 寫道:

Hello,

My two cents: I feel uncomfortable with SequenceType.first since
SequenceType clearly states that it may be destructed on iteration.

Compare :

seq.generate().next() // clear that it may give another result if called
twice
seq.first // unclear that it may give another result if called
twice

Gwendal


(Lily Ballard) #11

Here it is https://github.com/apple/swift/blob/master/stdlib/public/core/CollectionAlgorithms.swift.gyb#L26

We already don't have a .last on CollectionType and nobody's been
complaining about that. Besides, sequences don't necessarily even
terminate.

-Kevin Ballard

Users who don’t get the single-pass nature of SequenceType may
expect a .last as well.

Ah you're right, I was just looking at the unconstrained protocol. In
any case, we could theoretically provide a .last, but I don't think
that's useful enough on sequences to warrant inclusion. I know I've
wanted .first many times and I've never wanted .last.

Another motivation for adding this that I forgot to mention is that
today the code `someCol.lazy.filter(pred).first` actually isn't lazy at
all, it filters the entire collection and builds a new array (because
SequenceType doesn't have .first so it resolves the .filter() to the
eager version instead of the lazy version). Adding .first to
SequenceType makes that expression actually do what the user intended
(although my other proposal for SequenceType.find() provides a much
better way to accomplish the same task).

I like this addition and I think that we should take care to document
whether or not this mutates the sequence. I actually expect it to but
maybe I am mistaken.

(moving this back to the list)

I considered documenting that, but none of the existing "destructive"
methods on SequenceType document that. I think the assumption is that
anything that has to inspect the contents of the sequence is obviously
consuming the sequence to do that. In fact, the one method that doesn't
consume anything (not counting generate() since any use of the generator
is destructive), underestimateCount(), is explicitly documented as being
non-destructive.

Also, I couldn't think of a non-awkward way to say "this property
partially consumes the sequence if it's a sequence that is destructively
"consumed" by iteration". Especially because "partially consumed" isn't
actually a property of sequences; it's explicitly documented that
calling generate() a second time after any iteration is allowed to
return a completely arbitrary sequence of elements from the second
generator (for example, a generator that returns lines read from some
stream might buffer more data internally and therefore constructing a
second generator would possibly skip data that was never returned from
the first generator).

-Kevin Ballard

···

On Wed, Dec 30, 2015, at 04:39 PM, Daniel Duan wrote:

On Dec 30, 2015, at 4:27 PM, Kevin Ballard <kevin@sb.org> wrote:
On Wed, Dec 30, 2015, at 04:01 PM, Daniel Duan wrote:

On Wed, Dec 30, 2015, at 04:40 PM, gs. wrote:


(Lily Ballard) #12

Good idea, though I'd probably call it PeekSequence because it would
only buffer a single element (and BufferedSequence sounds like it's
got an arbitrary-sized buffer). Perhaps more useful would be the
associated PeekGenerator, because peek() is a useful thing to have
when writing custom generator-using code.

The size of the buffer is an implementation detail, and I don’t find
“peek” descriptive.

There's precedent for the name "peek". More importantly, that's the name
you'd use for the generator method; the sequence would still have the
"first" property.

My concern with making the size of the buffer be an implementation
detail is I'd rather not add array allocation if I only need a single
element of lookahead. I suppose it could have an `enum {
OneElement(Element), Buffer([Element]) }` as the storage, but that still
does end up being a little bit of extra work on every call to next().

I'll write up a more detailed email with a proposed design in a
minute.

Another related adapter I’d like to add is a model of CollectionType
that is backed by a sequence and lazily populated in fixed-sized
chunks.

Also a good idea. Although really it could just be backed by a
ContiguousArray, those things already grow in chunks. I'll write up a
design for that too.

Not unless you want to keep the buffers alive longer than necessary.
Imagine you’re parsing a long stream with some amount of lookahead.
You can scan this collection by slicing it and the buffer segments
that are no longer in use will be automatically collected.

Ah, I didn't realize you wanted to collect chunks that haven't been used
lately. But I don't think that's possible; since it's backed by a
sequence, the chunks MUST be generated in order; there's no way to skip
ahead, and no way to generate an older chunk that you've thrown away.
But since it's a CollectionType, you need to preserve the ability to
access older values. So the only way to actually have this be a
CollectionType is to buffer the entire sequence up to the highest-
accessed index.

Of course, your use-case of processing a stream with some amount of
lookahead and throwing away the old data actually sounds like something
a "BufferedSequence" might provide. Or actually, a "BufferedGenerator",
because the only way to process a sequence is with a generator and so
all a "BufferedSequence" would really do is just give you a
"BufferedGenerator" from its generate() method.

-Kevin Ballard

···

On Thu, Dec 31, 2015, at 02:03 PM, Dave Abrahams wrote:

On Dec 31, 2015, at 1:58 PM, Kevin Ballard <kevin@sb.org> wrote:


(Lily Ballard) #13

I've submitted a proposal to the ML for BufferedSequence / BufferedGenerator as https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20151228/005010.html. I kept the name "peek" for the method because, as mentioned in that email, there's plenty of precedent for it.

-Kevin Ballard

P.S. The plain-text version of the email is hard to read because the
     FastMail web interface doesn't handle rich text very well. The rich
     text version should be much more readable.

···

On Thu, Dec 31, 2015, at 02:03 PM, Dave Abrahams wrote:

I suggest you consider adding a BufferedSequence<Base: SequenceType>
that has a stable first property (at least until it is iterated)

Good idea, though I'd probably call it PeekSequence because it would
only buffer a single element (and BufferedSequence sounds like it's
got an arbitrary-sized buffer). Perhaps more useful would be the
associated PeekGenerator, because peek() is a useful thing to have
when writing custom generator-using code.

The size of the buffer is an implementation detail, and I don’t find
“peek” descriptive.


(Daniel Duan) #14

+1. I doubt anyone would really complain, just had to point it out.

···

On Dec 30, 2015, at 5:00 PM, Kevin Ballard <kevin@sb.org> wrote:

On Wed, Dec 30, 2015, at 04:39 PM, Daniel Duan wrote:

Here it is https://github.com/apple/swift/blob/master/stdlib/public/core/CollectionAlgorithms.swift.gyb#L26

On Dec 30, 2015, at 4:27 PM, Kevin Ballard <kevin@sb.org <mailto:kevin@sb.org>> wrote:

We already don't have a .last on CollectionType and nobody's been complaining about that. Besides, sequences don't necessarily even terminate.

-Kevin Ballard

On Wed, Dec 30, 2015, at 04:01 PM, Daniel Duan wrote:

Users who don’t get the single-pass nature of SequenceType may expect a .last as well.

Ah you're right, I was just looking at the unconstrained protocol. In any case, we could theoretically provide a .last, but I don't think that's useful enough on sequences to warrant inclusion. I know I've wanted .first many times and I've never wanted .last.

Another motivation for adding this that I forgot to mention is that today the code `someCol.lazy.filter(pred).first` actually isn't lazy at all, it filters the entire collection and builds a new array (because SequenceType doesn't have .first so it resolves the .filter() to the eager version instead of the lazy version). Adding .first to SequenceType makes that expression actually do what the user intended (although my other proposal for SequenceType.find() provides a much better way to accomplish the same task).

On Wed, Dec 30, 2015, at 04:40 PM, gs. wrote:

I like this addition and I think that we should take care to document whether or not this mutates the sequence. I actually expect it to but maybe I am mistaken.

(moving this back to the list)

I considered documenting that, but none of the existing "destructive" methods on SequenceType document that. I think the assumption is that anything that has to inspect the contents of the sequence is obviously consuming the sequence to do that. In fact, the one method that doesn't consume anything (not counting generate() since any use of the generator is destructive), underestimateCount(), is explicitly documented as being non-destructive.

Also, I couldn't think of a non-awkward way to say "this property partially consumes the sequence if it's a sequence that is destructively "consumed" by iteration". Especially because "partially consumed" isn't actually a property of sequences; it's explicitly documented that calling generate() a second time after any iteration is allowed to return a completely arbitrary sequence of elements from the second generator (for example, a generator that returns lines read from some stream might buffer more data internally and therefore constructing a second generator would possibly skip data that was never returned from the first generator).

-Kevin Ballard


(Dave Abrahams) #15

-Dave

Here it is https://github.com/apple/swift/blob/master/stdlib/public/core/CollectionAlgorithms.swift.gyb#L26

We already don't have a .last on CollectionType and nobody's been complaining about that. Besides, sequences don't necessarily even terminate.

-Kevin Ballard

Users who don’t get the single-pass nature of SequenceType may expect a .last as well.

Ah you're right, I was just looking at the unconstrained protocol. In any case, we could theoretically provide a .last, but I don't think that's useful enough on sequences to warrant inclusion. I know I've wanted .first many times and I've never wanted .last.

Another motivation for adding this that I forgot to mention is that today the code `someCol.lazy.filter(pred).first` actually isn't lazy at all, it filters the entire collection and builds a new array (because SequenceType doesn't have .first so it resolves the .filter() to the eager version instead of the lazy version).

Oh, that’s nasty. I wonder if there’s something we can do with ambiguity to make the eager overload inaccessible in that context? Would you mind opening a bug for this?

···

On Dec 30, 2015, at 5:00 PM, Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:
On Wed, Dec 30, 2015, at 04:39 PM, Daniel Duan wrote:

On Dec 30, 2015, at 4:27 PM, Kevin Ballard <kevin@sb.org <mailto:kevin@sb.org>> wrote:
On Wed, Dec 30, 2015, at 04:01 PM, Daniel Duan wrote:

Adding .first to SequenceType makes that expression actually do what the user intended (although my other proposal for SequenceType.find() provides a much better way to accomplish the same task).

On Wed, Dec 30, 2015, at 04:40 PM, gs. wrote:

I like this addition and I think that we should take care to document whether or not this mutates the sequence. I actually expect it to but maybe I am mistaken.

(moving this back to the list)

I considered documenting that, but none of the existing "destructive" methods on SequenceType document that. I think the assumption is that anything that has to inspect the contents of the sequence is obviously consuming the sequence to do that. In fact, the one method that doesn't consume anything (not counting generate() since any use of the generator is destructive), underestimateCount(), is explicitly documented as being non-destructive.

Also, I couldn't think of a non-awkward way to say "this property partially consumes the sequence if it's a sequence that is destructively "consumed" by iteration". Especially because "partially consumed" isn't actually a property of sequences; it's explicitly documented that calling generate() a second time after any iteration is allowed to return a completely arbitrary sequence of elements from the second generator (for example, a generator that returns lines read from some stream might buffer more data internally and therefore constructing a second generator would possibly skip data that was never returned from the first generator).

-Kevin Ballard

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


(Dave Abrahams) #16

I've submitted a proposal to the ML for BufferedSequence / BufferedGenerator as https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20151228/005010.html.

Thanks.

I kept the name "peek" for the method because, as mentioned in that email, there's plenty of precedent for it.

It’s a perfectly cromulent name for that purpose. I just don’t think it belongs in the type name.

-Kevin Ballard

P.S. The plain-text version of the email is hard to read because the FastMail web interface doesn't handle rich text very well. The rich text version should be much more readable.

I suggest you consider adding a BufferedSequence<Base: SequenceType> that has a stable first property (at least until it is iterated)

Good idea, though I'd probably call it PeekSequence because it would only buffer a single element (and BufferedSequence sounds like it's got an arbitrary-sized buffer). Perhaps more useful would be the associated PeekGenerator, because peek() is a useful thing to have when writing custom generator-using code.

The size of the buffer is an implementation detail, and I don’t find “peek” descriptive.

-Dave

···

On Dec 31, 2015, at 4:19 PM, Kevin Ballard <kevin@sb.org> wrote:
On Thu, Dec 31, 2015, at 02:03 PM, Dave Abrahams wrote:


(Brent Royal-Gordon) #17

May I suggest a simple solution?

  extension SequenceType {
    /// Returns one element from the beginning of the sequence, or `nil` if the sequence is empty.
    /// If `self` is a single-pass sequence, this may consume the element.
    func one() -> Generator.Element? {
      var generator = generate()
      return generator.next()
    }
  }

This should probably be a method in the protocol, and CollectionType should have an override which calls `first`.

The BufferedSequence stuff suggested elsewhere is probably useful too, and should be considered in addition to this, but I think this would cover the most common case.

···

--
Brent Royal-Gordon
Architechies


(Dave Abrahams) #18

Good idea, though I'd probably call it PeekSequence because it would only buffer a single element (and BufferedSequence sounds like it's got an arbitrary-sized buffer). Perhaps more useful would be the associated PeekGenerator, because peek() is a useful thing to have when writing custom generator-using code.

The size of the buffer is an implementation detail, and I don’t find “peek” descriptive.

There's precedent for the name "peek". More importantly, that's the name you'd use for the generator method; the sequence would still have the "first" property.

My concern with making the size of the buffer be an implementation detail is I'd rather not add array allocation if I only need a single element of lookahead. I suppose it could have an `enum { OneElement(Element), Buffer([Element]) }` as the storage, but that still does end up being a little bit of extra work on every call to next().

I'll write up a more detailed email with a proposed design in a minute.

Another related adapter I’d like to add is a model of CollectionType that is backed by a sequence and lazily populated in fixed-sized chunks.

Also a good idea. Although really it could just be backed by a ContiguousArray, those things already grow in chunks. I'll write up a design for that too.

Not unless you want to keep the buffers alive longer than necessary. Imagine you’re parsing a long stream with some amount of lookahead. You can scan this collection by slicing it and the buffer segments that are no longer in use will be automatically collected.

Ah, I didn't realize you wanted to collect chunks that haven't been used lately. But I don't think that's possible;

since it's backed by a sequence, the chunks MUST be generated in order; there's no way to skip ahead, and no way to generate an older chunk that you've thrown away.

Right…?

But since it's a CollectionType, you need to preserve the ability to access older values.

Not once you replace it with a slice of itself.

So the only way to actually have this be a CollectionType is to buffer the entire sequence up to the highest-accessed index.

Of course, your use-case of processing a stream with some amount of lookahead and throwing away the old data actually sounds like something a "BufferedSequence" might provide. Or actually, a "BufferedGenerator", because the only way to process a sequence is with a generator and so all a "BufferedSequence" would really do is just give you a "BufferedGenerator" from its generate() method.

I’m quite certain this is buildable. I’ve got my hands full at the moment or I’d create a prototype…

-Dave

···

On Dec 31, 2015, at 3:20 PM, Kevin Ballard <kevin@sb.org> wrote:
On Thu, Dec 31, 2015, at 02:03 PM, Dave Abrahams wrote:

On Dec 31, 2015, at 1:58 PM, Kevin Ballard <kevin@sb.org <mailto:kevin@sb.org>> wrote:


(Lily Ballard) #19

I submitted another proposal a few hours ago regarding @available(*, unavailable) that's designed to turn this into a compile-time error.

Although I wonder if a stopgap would be to provide a `first` property on LazySequenceType that's marked as unavailable. I haven't checked to see how that behaves but I hope it would trigger an error instead of resolving to the eager filter.

-Kevin Ballard

···

On Dec 31, 2015, 12:40 AM -0800, Dave Abrahams<dabrahams@apple.com>, wrote:

-Dave
> On Dec 30, 2015, at 5:00 PM, Kevin Ballard via swift-evolution<swift-evolution@swift.org(mailto:swift-evolution@swift.org)>wrote:
> On Wed, Dec 30, 2015, at 04:39 PM, Daniel Duan wrote:
> > Here it ishttps://github.com/apple/swift/blob/master/stdlib/public/core/CollectionAlgorithms.swift.gyb#L26
> > > On Dec 30, 2015, at 4:27 PM, Kevin Ballard<kevin@sb.org(mailto:kevin@sb.org)>wrote:
> > > We already don't have a .last on CollectionType and nobody's been complaining about that. Besides, sequences don't necessarily even terminate.
> > > -Kevin Ballard
> > > On Wed, Dec 30, 2015, at 04:01 PM, Daniel Duan wrote:
> > > > Users who don’t get the single-pass nature of SequenceType may expect a .last as well.
> Ah you're right, I was just looking at the unconstrained protocol. In any case, we could theoretically provide a .last, but I don't think that's useful enough on sequences to warrant inclusion. I know I've wanted .first many times and I've never wanted .last.
> Another motivation for adding this that I forgot to mention is that today the code `someCol.lazy.filter(pred).first` actually isn't lazy at all, it filters the entire collection and builds a new array (because SequenceType doesn't have .first so it resolves the .filter() to the eager version instead of the lazy version).

Oh, that’s nasty.I wonder if there’s something we can do with ambiguity to make the eager overload inaccessible in that context?Would you mind opening a bug for this?

> Adding .first to SequenceType makes that expression actually do what the user intended (although my other proposal for SequenceType.find() provides a much better way to accomplish the same task).
> On Wed, Dec 30, 2015, at 04:40 PM, gs. wrote:
> > I like this addition and I think that we should take care to document whether or not this mutates the sequence. I actually expect it to but maybe I am mistaken.
> (moving this back to the list)
> I considered documenting that, but none of the existing "destructive" methods on SequenceType document that. I think the assumption is that anything that has to inspect the contents of the sequence is obviously consuming the sequence to do that. In fact, the one method that doesn't consume anything (not counting generate() since any use of the generator is destructive), underestimateCount(), is explicitly documented as being non-destructive.
> Also, I couldn't think of a non-awkward way to say "this property partially consumes the sequence if it's a sequence that is destructively "consumed" by iteration". Especially because "partially consumed" isn't actually a property of sequences; it's explicitly documented that calling generate() a second time after any iteration is allowed to return a completely arbitrary sequence of elements from the second generator (for example, a generator that returns lines read from some stream might buffer more data internally and therefore constructing a second generator would possibly skip data that was never returned from the first generator).
> -Kevin Ballard_______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org(mailto:swift-evolution@swift.org)
> https://lists.swift.org/mailman/listinfo/swift-evolution


(Lily Ballard) #20

Incidentally, I misspoke; the problem is with
`someSeq.lazy.filter(pred).first`. `LazyCollection.filter` returns a
`CollectionType`, so `someCol.lazy.filter(pred).first` works fine there.

-Kevin Ballard

···

On Thu, Dec 31, 2015, at 12:40 AM, Dave Abrahams wrote:

Another motivation for adding this that I forgot to mention is that
today the code `someCol.lazy.filter(pred).first` actually isn't lazy
at all, it filters the entire collection and builds a new array
(because SequenceType doesn't have .first so it resolves the
.filter() to the eager version instead of the lazy version).

Oh, that’s nasty. I wonder if there’s something we can do with
ambiguity to make the eager overload inaccessible in that context?
Would you mind opening a bug for this?