Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

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

Open
swift-ci opened this issue Aug 23, 2017 · 11 comments
Open

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

swift-ci opened this issue Aug 23, 2017 · 11 comments
Labels
improvement standard library Area: Standard library umbrella swift evolution proposal needed Flag → feature: A feature that warrants a Swift evolution proposal

Comments

@swift-ci
Copy link
Collaborator

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
Copy link
Contributor

cc @airspeedswift, @moiseev

@moiseev
Copy link
Mannequin

moiseev mannequin commented Aug 28, 2017

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
Copy link
Collaborator Author

Comment by Dennis Vennink (JIRA)

CC: @airspeedswift, @moiseev

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

@moiseev
Copy link
Mannequin

moiseev mannequin commented Jul 3, 2018

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
Copy link
Collaborator Author

swift-ci commented Jul 4, 2018

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
Copy link
Collaborator Author

swift-ci commented Jul 4, 2018

Comment by Dennis Vennink (JIRA)

Incorrectly submitted as a bug.

@moiseev
Copy link
Mannequin

moiseev mannequin commented Jul 6, 2018

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

@swift-ci
Copy link
Collaborator Author

swift-ci commented Jul 6, 2018

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

@moiseev
Copy link
Mannequin

moiseev mannequin commented Jul 7, 2018

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(_: ).

@moiseev
Copy link
Mannequin

moiseev mannequin commented Jul 7, 2018

/cc @airspeedswift

@mattneub
Copy link

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

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
improvement standard library Area: Standard library umbrella swift evolution proposal needed Flag → feature: A feature that warrants a Swift evolution proposal
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@belkadan @mattneub @swift-ci