Proposal: Add types BufferedSequence, BufferedGenerator


(Lily Ballard) #1

BufferedSequence is a sequence adaptor that wraps any underlying sequence and provides a stable `first` property. BufferedGenerator is a generator adaptor that wraps any underlying generator and provides arbitrary lookahead with a `peek(n: Int)` method.

The method name "peek()" has precedent in various languages (e.g. Rust
with std::iter::Peekable, C++ with std::basic_istream::peek, Ruby with
Enumerator#peek, etc). I considered the name "lookahead()" but I decided
it made more sense to use that name for the property that describes how
much lookahead there is.

The proposed API looks like this:

/// A sequence adaptor that adds a nondestructive `first`
property to any

/// underlying sequence.

/// - Note: If the underlying sequence is not destructively
"consumed" by

/// iteration, then neither is `BufferedSequence`.

public class BufferedSequence<Base : SequenceType> : SequenceType {

public init(_ base: Base)

/// Returns ` BufferedGenerator` with a lookahead size of `1`.

public func generate() ->
BufferedSequence.BufferedGenerator<Base.Generator>

/// Returns the first element of the underlying sequence,
**nondestructively**.

public var first: Base.Generator.Element? { get }

}

/// A generator adaptor that adds a nondestructive `peek()`
method to any

/// underlying generator.

public struct BufferedGenerator<Base : GeneratorType> : GeneratorType {

/// Construct an instance that buffers access to an underlying
generator.

/// - Parameter base: The underlying generator.

/// - Parameter lookahead: The amount of lookahead to allow.
Default is `1`.

/// Values less than `1` will be treated the same as `1`.

public init(_ base: Base, lookahead: Int = default)

/// The amount of lookahead that this generator offers.

/// - Invariant: `lookahead >= 1`.

public let lookahead: Int

/// Advance to the next element and return it, or `nil` if no next
element exists.

///

/// - Requires: Neither `next()` nor `peek()` have been applied
to a copy of

/// `self` since the copy was made, and no preceding call to
`self.next()` has

/// returned `nil`.

public mutating func next() -> Base.Element?

/// Returns the value that will be returned from subsequent calls
to `next()`.

/// - Parameter n: The number of elements to look ahead. Default is
`0`. A value

/// of `0` means to look at the next element.

/// - Precondition: `n >= 0 && n < lookahead`.

/// - Requires: Neither `next()` nor `peek()` have been applied
to a copy of

/// `self` since the copy was made, and no preceding call to
`self.next()` has

/// returned `nil`.

/// - Note: It is safe to peek at values past the end of the
underlying generator

/// (`peek()` will return `nil` in such cases). It is also safe to
call `peek()`

/// repeatedly, even after it's returned `nil`, and similarly it is
safe to call

/// `next()` after `peek()` has returned `nil`.

public mutating func peek(n: Int = default) -> Base.Element?

}

BufferedSequence is a class because the generate() function needs to
mutate it. After the `first` property has been accessed, it needs to
cache the generator it used for that so it can return it from the next
call to generate(), but it also needs to nil out that cache at that time
so it doesn't try and return the same generator instance a second time
on a subsequent call to generate() (this way BufferedSequence can be
written to support non-destructive iteration if the underlying sequence
is non-destructive).

I've already started sketching out an implementation as well. I believe
it should be possible to optimize BufferedGenerator for a lookahead of 1
to avoid the heap allocation of an array.

-Kevin Ballard


(Howard Lovatt) #2

+1

···

Sent from my iPad

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

BufferedSequence is a sequence adaptor that wraps any underlying sequence and provides a stable `first` property. BufferedGenerator is a generator adaptor that wraps any underlying generator and provides arbitrary lookahead with a `peek(n: Int)` method.

The method name "peek()" has precedent in various languages (e.g. Rust with std::iter::Peekable, C++ with std::basic_istream::peek, Ruby with Enumerator#peek, etc). I considered the name "lookahead()" but I decided it made more sense to use that name for the property that describes how much lookahead there is.

The proposed API looks like this:

/// A sequence adaptor that adds a nondestructive `first` property to any
/// underlying sequence.
/// - Note: If the underlying sequence is not destructively "consumed" by
/// iteration, then neither is `BufferedSequence`.
public class BufferedSequence<Base : SequenceType> : SequenceType {
    public init(_ base: Base)

    /// Returns ` BufferedGenerator` with a lookahead size of `1`.
    public func generate() -> BufferedSequence.BufferedGenerator<Base.Generator>

    /// Returns the first element of the underlying sequence, **nondestructively**.
    public var first: Base.Generator.Element? { get }
}

/// A generator adaptor that adds a nondestructive `peek()` method to any
/// underlying generator.
public struct BufferedGenerator<Base : GeneratorType> : GeneratorType {
    /// Construct an instance that buffers access to an underlying generator.
    /// - Parameter base: The underlying generator.
    /// - Parameter lookahead: The amount of lookahead to allow. Default is `1`.
    /// Values less than `1` will be treated the same as `1`.
    public init(_ base: Base, lookahead: Int = default)

    /// The amount of lookahead that this generator offers.
    /// - Invariant: `lookahead >= 1`.
    public let lookahead: Int

    /// Advance to the next element and return it, or `nil` if no next element exists.
    ///
    /// - Requires: Neither `next()` nor `peek()` have been applied to a copy of
    /// `self` since the copy was made, and no preceding call to `self.next()` has
    /// returned `nil`.
    public mutating func next() -> Base.Element?

    /// Returns the value that will be returned from subsequent calls to `next()`.
    /// - Parameter n: The number of elements to look ahead. Default is `0`. A value
    /// of `0` means to look at the next element.
    /// - Precondition: `n >= 0 && n < lookahead`.
    /// - Requires: Neither `next()` nor `peek()` have been applied to a copy of
    /// `self` since the copy was made, and no preceding call to `self.next()` has
    /// returned `nil`.
    /// - Note: It is safe to peek at values past the end of the underlying generator
    /// (`peek()` will return `nil` in such cases). It is also safe to call `peek()`
    /// repeatedly, even after it's returned `nil`, and similarly it is safe to call
    /// `next()` after `peek()` has returned `nil`.
    public mutating func peek(n: Int = default) -> Base.Element?
}

BufferedSequence is a class because the generate() function needs to mutate it. After the `first` property has been accessed, it needs to cache the generator it used for that so it can return it from the next call to generate(), but it also needs to nil out that cache at that time so it doesn't try and return the same generator instance a second time on a subsequent call to generate() (this way BufferedSequence can be written to support non-destructive iteration if the underlying sequence is non-destructive).

I've already started sketching out an implementation as well. I believe it should be possible to optimize BufferedGenerator for a lookahead of 1 to avoid the heap allocation of an array.

-Kevin Ballard

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


(Lily Ballard) #3

Incidentally I forgot to mention that I’d also want to add:

extension SequenceType {
    /// Returns a `BufferedSequence` that wraps `self`.
    /// - SeeAlso: `BufferedSequence<Base>`.
    public var buffered: BufferedSequence<Self> { get }
}

extension BufferedSequence {
    /// Identical to `self`.
    public var buffered: BufferedSequence<Base> { get }
}

extension GeneratorType {
    /// Returns a `BufferedGenerator` that wraps `self`.
    /// - Parameter lookahead: The amount of lookahead to allow. Default is `1`.
    /// - Note: The new generator should be considered a copy of `self` for the
    /// purposes of evaluating requirements (e.g. for `next()`).
    /// - SeeAlso: `BufferedGenerator<Base>`.
    public func buffered(lookahead: Int = default) -> BufferedGenerator<Self>
}

extension BufferedGenerator {
    /// Returns a new `BufferedGenerator` that wraps `self.base`.
    /// If `lookahead < self.lookahead`, the new generator may have a lookahead
    /// that's larger than `lookahead` if necessary to avoid losing elements.
    /// - Parameter lookahead: The amount of lookahead to allow. Default is `1`.
    /// - Invariant: The sequence of elements returned from calling `next()` on
    /// the new generator is identical to the sequence of elements that would
    /// have been returned from calling `next()` on `self` regardless of any
    /// changes to the lookahead amount.
    /// - Note: The new generator should be considered a copy of `self` for the
    /// purposes of evaluating requirements (e.g. for `next()`).
    public func buffered(lookahead: Int = default) -> BufferedGenerator<Base>
}

As well as exposing the base sequence/generator on both types through a property named `base`.

-Kevin Ballard

···

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

BufferedSequence is a sequence adaptor that wraps any underlying sequence and provides a stable `first` property. BufferedGenerator is a generator adaptor that wraps any underlying generator and provides arbitrary lookahead with a `peek(n: Int)` method.

The method name "peek()" has precedent in various languages (e.g. Rust with std::iter::Peekable, C++ with std::basic_istream::peek, Ruby with Enumerator#peek, etc). I considered the name "lookahead()" but I decided it made more sense to use that name for the property that describes how much lookahead there is.

The proposed API looks like this:

/// A sequence adaptor that adds a nondestructive `first` property to any
/// underlying sequence.
/// - Note: If the underlying sequence is not destructively "consumed" by
/// iteration, then neither is `BufferedSequence`.
public class BufferedSequence<Base : SequenceType> : SequenceType {
    public init(_ base: Base)

    /// Returns ` BufferedGenerator` with a lookahead size of `1`.
    public func generate() -> BufferedSequence.BufferedGenerator<Base.Generator>

    /// Returns the first element of the underlying sequence, **nondestructively**.
    public var first: Base.Generator.Element? { get }
}

/// A generator adaptor that adds a nondestructive `peek()` method to any
/// underlying generator.
public struct BufferedGenerator<Base : GeneratorType> : GeneratorType {
    /// Construct an instance that buffers access to an underlying generator.
    /// - Parameter base: The underlying generator.
    /// - Parameter lookahead: The amount of lookahead to allow. Default is `1`.
    /// Values less than `1` will be treated the same as `1`.
    public init(_ base: Base, lookahead: Int = default)

    /// The amount of lookahead that this generator offers.
    /// - Invariant: `lookahead >= 1`.
    public let lookahead: Int

    /// Advance to the next element and return it, or `nil` if no next element exists.
    ///
    /// - Requires: Neither `next()` nor `peek()` have been applied to a copy of
    /// `self` since the copy was made, and no preceding call to `self.next()` has
    /// returned `nil`.
    public mutating func next() -> Base.Element?

    /// Returns the value that will be returned from subsequent calls to `next()`.
    /// - Parameter n: The number of elements to look ahead. Default is `0`. A value
    /// of `0` means to look at the next element.
    /// - Precondition: `n >= 0 && n < lookahead`.
    /// - Requires: Neither `next()` nor `peek()` have been applied to a copy of
    /// `self` since the copy was made, and no preceding call to `self.next()` has
    /// returned `nil`.
    /// - Note: It is safe to peek at values past the end of the underlying generator
    /// (`peek()` will return `nil` in such cases). It is also safe to call `peek()`
    /// repeatedly, even after it's returned `nil`, and similarly it is safe to call
    /// `next()` after `peek()` has returned `nil`.
    public mutating func peek(n: Int = default) -> Base.Element?
}

BufferedSequence is a class because the generate() function needs to mutate it. After the `first` property has been accessed, it needs to cache the generator it used for that so it can return it from the next call to generate(), but it also needs to nil out that cache at that time so it doesn't try and return the same generator instance a second time on a subsequent call to generate() (this way BufferedSequence can be written to support non-destructive iteration if the underlying sequence is non-destructive).

I've already started sketching out an implementation as well. I believe it should be possible to optimize BufferedGenerator for a lookahead of 1 to avoid the heap allocation of an array.

-Kevin Ballard


(Félix Cloutier) #4

Not a fan of anything that reminds me of Java streams.

Is the case where making an array from the sequence isn't possible significant enough for a new standard API?

Félix

···

Le 31 déc. 2015 à 20:50:40, Howard Lovatt via swift-evolution <swift-evolution@swift.org> a écrit :

+1

Sent from my iPad

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

BufferedSequence is a sequence adaptor that wraps any underlying sequence and provides a stable `first` property. BufferedGenerator is a generator adaptor that wraps any underlying generator and provides arbitrary lookahead with a `peek(n: Int)` method.

The method name "peek()" has precedent in various languages (e.g. Rust with std::iter::Peekable, C++ with std::basic_istream::peek, Ruby with Enumerator#peek, etc). I considered the name "lookahead()" but I decided it made more sense to use that name for the property that describes how much lookahead there is.

The proposed API looks like this:

/// A sequence adaptor that adds a nondestructive `first` property to any
/// underlying sequence.
/// - Note: If the underlying sequence is not destructively "consumed" by
/// iteration, then neither is `BufferedSequence`.
public class BufferedSequence<Base : SequenceType> : SequenceType {
    public init(_ base: Base)

    /// Returns ` BufferedGenerator` with a lookahead size of `1`.
    public func generate() -> BufferedSequence.BufferedGenerator<Base.Generator>

    /// Returns the first element of the underlying sequence, **nondestructively**.
    public var first: Base.Generator.Element? { get }
}

/// A generator adaptor that adds a nondestructive `peek()` method to any
/// underlying generator.
public struct BufferedGenerator<Base : GeneratorType> : GeneratorType {
    /// Construct an instance that buffers access to an underlying generator.
    /// - Parameter base: The underlying generator.
    /// - Parameter lookahead: The amount of lookahead to allow. Default is `1`.
    /// Values less than `1` will be treated the same as `1`.
    public init(_ base: Base, lookahead: Int = default)

    /// The amount of lookahead that this generator offers.
    /// - Invariant: `lookahead >= 1`.
    public let lookahead: Int

    /// Advance to the next element and return it, or `nil` if no next element exists.
    ///
    /// - Requires: Neither `next()` nor `peek()` have been applied to a copy of
    /// `self` since the copy was made, and no preceding call to `self.next()` has
    /// returned `nil`.
    public mutating func next() -> Base.Element?

    /// Returns the value that will be returned from subsequent calls to `next()`.
    /// - Parameter n: The number of elements to look ahead. Default is `0`. A value
    /// of `0` means to look at the next element.
    /// - Precondition: `n >= 0 && n < lookahead`.
    /// - Requires: Neither `next()` nor `peek()` have been applied to a copy of
    /// `self` since the copy was made, and no preceding call to `self.next()` has
    /// returned `nil`.
    /// - Note: It is safe to peek at values past the end of the underlying generator
    /// (`peek()` will return `nil` in such cases). It is also safe to call `peek()`
    /// repeatedly, even after it's returned `nil`, and similarly it is safe to call
    /// `next()` after `peek()` has returned `nil`.
    public mutating func peek(n: Int = default) -> Base.Element?
}

BufferedSequence is a class because the generate() function needs to mutate it. After the `first` property has been accessed, it needs to cache the generator it used for that so it can return it from the next call to generate(), but it also needs to nil out that cache at that time so it doesn't try and return the same generator instance a second time on a subsequent call to generate() (this way BufferedSequence can be written to support non-destructive iteration if the underlying sequence is non-destructive).

I've already started sketching out an implementation as well. I believe it should be possible to optimize BufferedGenerator for a lookahead of 1 to avoid the heap allocation of an array.

-Kevin Ballard

_______________________________________________
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
https://lists.swift.org/mailman/listinfo/swift-evolution


(Lily Ballard) #5

Not a fan of anything that reminds me of Java streams.

I don't know anything at all about Java streams, but this is based on
the very common concept of being able to "peek" at the next element
of an enumerable value, just extended a bit to support lookahead of
more than 1.

Is the case where making an array from the sequence isn't possible
significant enough for a new standard API?

Why would you make an array from the sequence? That's flagrantly
wasteful if all you're doing is processing a sequence and simply need
some lookahead. And in the case of an infinite sequence it's downright
impossible.

-Kevin Ballard

···

On Fri, Jan 1, 2016, at 12:35 PM, Félix Cloutier wrote:

Félix

Le 31 déc. 2015 à 20:50:40, Howard Lovatt via swift-evolution <swift- >> evolution@swift.org> a écrit :

+1

Sent from my iPad

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

BufferedSequence is a sequence adaptor that wraps any underlying
sequence and provides a stable `first` property. BufferedGenerator
is a generator adaptor that wraps any underlying generator and
provides arbitrary lookahead with a `peek(n: Int)` method.

The method name "peek()" has precedent in various languages (e.g.
Rust with std::iter::Peekable, C++ with std::basic_istream::peek,
Ruby with Enumerator#peek, etc). I considered the name "lookahead()"
but I decided it made more sense to use that name for the property
that describes how much lookahead there is.

The proposed API looks like this:

/// A sequence adaptor that adds a nondestructive `first` property
to any /// underlying sequence. /// - Note: If the underlying
sequence is not destructively "consumed" by /// iteration, then
neither is `BufferedSequence`. public class BufferedSequence<Base :
> : SequenceType { public init(_ base: Base)

/// Returns ` BufferedGenerator` with a lookahead size of `1`.
public func generate() ->
BufferedSequence.BufferedGenerator<Base.Generator>

/// Returns the first element of the underlying sequence,
**nondestructively**. public var first: Base.Generator.Element? {
get } }

/// A generator adaptor that adds a nondestructive `peek()` method
to any /// underlying generator. public struct
BufferedGenerator<Base : GeneratorType> : GeneratorType { ///
Construct an instance that buffers access to an underlying
generator. /// - Parameter base: The underlying generator. /// -
Parameter lookahead: The amount of lookahead to allow. Default is
`1`. /// Values less than `1` will be treated the same as `1`.
public init(_ base: Base, lookahead: Int = default)

/// The amount of lookahead that this generator offers. /// -
Invariant: `lookahead >= 1`. public let lookahead: Int

/// Advance to the next element and return it, or `nil` if no next
element exists. /// /// - Requires: Neither `next()` nor `peek()`
have been applied to a copy of /// `self` since the copy was made,
and no preceding call to `self.next()` has /// returned `nil`.
public mutating func next() -> Base.Element?

/// Returns the value that will be returned from subsequent calls to
`next()`. /// - Parameter n: The number of elements to look ahead.
Default is `0`. A value /// of `0` means to look at the next
element. /// - Precondition: `n >= 0 && n < lookahead`. /// -
Requires: Neither `next()` nor `peek()` have been applied to a copy
of /// `self` since the copy was made, and no preceding call to
`self.next()` has /// returned `nil`. /// - Note: It is safe to
peek at values past the end of the underlying generator ///
(`peek()` will return `nil` in such cases). It is also safe to call
`peek()` /// repeatedly, even after it's returned `nil`, and
similarly it is safe to call /// `next()` after `peek()` has
returned `nil`. public mutating func peek(n: Int = default) ->
Base.Element? }

BufferedSequence is a class because the generate() function needs to
mutate it. After the `first` property has been accessed, it needs to
cache the generator it used for that so it can return it from the
next call to generate(), but it also needs to nil out that cache at
that time so it doesn't try and return the same generator instance a
second time on a subsequent call to generate() (this way
BufferedSequence can be written to support non-destructive iteration
if the underlying sequence is non-destructive).

I've already started sketching out an implementation as well. I
believe it should be possible to optimize BufferedGenerator for a
lookahead of 1 to avoid the heap allocation of an array.

-Kevin Ballard

_______________________________________________
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