[SR-5754] Some Sequence Operations Are Missing a Lazy Implementation

[swift-ci]

Previous ID	SR-5754
Radar	rdar://problem/34118043
Original Reporter	dennisvennink (JIRA User)
Type	Improvement
Status	In Progress
Resolution

Additional Detail from JIRA

| | | |------------------|-----------------| |Votes | 1 | |Component/s | Standard Library | |Labels | Improvement, swift-evolution-proposal-needed | |Assignee | dennisvennink (JIRA) | |Priority | Medium | md5: e849cf83ebd7f75ce734f35ceabb20c9

Issue Description:

public struct LazyCycleIterator <Base: Sequence>: IteratorProtocol {
  public typealias Element = Base.Element

  private var sequence: Base
  private var iterator: Base.Iterator

  internal init (_ sequence: Base) {
    self.sequence = sequence
    self.iterator = self.sequence.makeIterator()
  }

  public mutating func next () -> Element? {
    var next = self.iterator.next()

    if next == nil {
      self.iterator = self.sequence.makeIterator()
      next = self.iterator.next()
    }

    return next
  }
}

public struct LazyCycleSequence <Base: Sequence>: LazySequenceProtocol {
  public typealias Iterator = LazyCycleIterator<Base>
  public typealias Element = Iterator.Element

  private let base: Base

  internal init (_ base: Base) {
    self.base = base
  }

  public func makeIterator () -> Iterator {
    return Iterator(self.base)
  }
}

public extension Sequence {
  func cycle () -> LazyCycleSequence<Self> {
    return LazyCycleSequence(self)
  }
}

print(type(of: [1, 2, 3].cycle().prefix(5)))

prefix(_ maxLength:) returns an AnySequence when operating on an object that conforms to LazySequenceProtocol making subsequent operations eager. I know we can add another call to lazy after prefix to get back into lazy land, but that kind of defeats the entire purpose of the lazy property; once we're lazy we should stay lazy.

Thoughts?

[belkadan]

cc @airspeedswift, @moiseev

[ee21ea02-9d7a-4385-8c3c-ad21e8e490a8]

This, unfortunately, is not the only case where one can accidentally lose laziness. Something can probably be done to address these problems when we get conditional conformances (at the very least .lazy will be touched once the conditional conformances exist, so it makes sense to perform this work at the same time).

Thanks dennisvennink (JIRA User) for pointing this out.

[swift-ci]

Comment by Dennis Vennink (JIRA)

CC: @airspeedswift, @moiseev

What's the status of this bug? (Since conditional conformances have landed?)

[ee21ea02-9d7a-4385-8c3c-ad21e8e490a8]

Should have been fixed, actually.
Just tried it in Xcode Version 9.4.1 and [1,2,3].lazy.prefix(2) returns a Slice<LazyCollection<Array<Int>>>, so the operations chained after that should all be lazy.

Please verify.

[swift-ci]

Comment by Dennis Vennink (JIRA)

While [1,2,3].lazy.prefix(2) does indeed return a Slice<LazyCollection<Array<Int>>> here in 10.0 beta (10L176w), the reported bug, in which prefix(_: ) doesn't have an overload for types conforming to LazySequenceProtocol s, is not fixed.

Come to think of it, it's probably not implemented yet, which makes this more of a feature request.

Another example:

print(type(of: sequence(first: 0, next: { $0 + 1 }).lazy.prefix(10)))
// AnySequence<Int>

(As an aside, the Standard Library already defines a lazily implemented internal type called _PrefixSequence.)

[swift-ci]

Comment by Dennis Vennink (JIRA)

Incorrectly submitted as a bug.

[ee21ea02-9d7a-4385-8c3c-ad21e8e490a8]

What is the type you suggest the prefix(_: ) should return when applied to a LazySequenceProtocol?

[swift-ci]

Comment by Dennis Vennink (JIRA)

The least obtrusive and elegant solution would be a new type called LazyPrefixSequence that conforms to LazySequenceProtocol. This would probably also require a LazyPrefixCollection conforming to LazyCollectionProtocol.

(I could write an Evolution proposal, if it requires one.)

[ee21ea02-9d7a-4385-8c3c-ad21e8e490a8]

This is opening a can of worms, unfortunately. If we take this approach, it would have to be replicated for other methods like dropFirst(_ : ) and suffix(_: ).

[ee21ea02-9d7a-4385-8c3c-ad21e8e490a8]

/cc @airspeedswift

[mattneub]

I'm encountering this in relation to an UnfoldSequence, as

if let i = (sequence.lazy.compactMap{$0}.first)

If I say that, I lose laziness. I can work around the issue by saying

if let i = (sequence.lazy.compactMap{$0}.first{_ in true})

because first(where:) preserves laziness while first does not. That seems a little nutty.

(I believe I'm right in adding this as a comment here, but if should be filed as an actual separate bug, please tell me and I'll do that.)