Should LazySequence be a protocol?

Question

Created Jun ’15

Replies 0

Boosts 0

Participants 1

So I'm currently noodling around with the standard library, extending every protocol I can find, all that good stuff. Four structs caught my eye:

LazySequence
LazyForwardCollection
LazyBidirectionalCollection
LazyRandomAccessCollection

They're the sequences and collections that have lazy implementations of map() and filter(). To get them from eager/static sequences you just call lazy() on the sequence.

So say I wanted to write a function that operates lazily on these sequences - something like scan()/accumulate(), or interpose(), or whatever. Something like:

extension SequenceType {
  func scan<T>(initial: T, combine: (T, Generator.Element) -> T) -> LazyScanSeq<Self, T> {
    return LazyScanSeq(seq: self, combine: combine, initial: initial)
  }
}

I can have my own struct LazyScanSeq, like FilterCollectionView, etc. I can have it lazily evaluate its sequence. And it's available on all sequences, so it works fine. Unless I want to have an eager version, like this:

extension SequenceType {
  func scan<T>(var initial: T, @noescape combine: (T, Generator.Element) -> T) -> [T] {
    return self.map {
      initial = combine(initial, $0)
      return initial
    }
  }
}
[1, 2, 3].scan(0, combine: +) // [1, 3, 6]

Both functions can't exist under the same extension. One has to be the default, and then I can override specific instances with the other. Clearly the default in Swift is eager evaluation, so that one gets to be the SequenceType extension. But then what do I do with the lazy method? Extend LazySequence, then extend LazyForwardCollection, etc.? That's a lot of repetition. What I tried to do first was this:

public protocol LazySequenceType      : SequenceType {}
extension LazySequence                : LazySequenceType {}
extension LazyForwardCollection       : LazySequenceType {}
extension LazyBidirectionalCollection : LazySequenceType {}
extension LazyRandomAccessCollection  : LazySequenceType {}
extension FilterSequenceView          : LazySequenceType {}
extension FilterCollectionView        : LazySequenceType {}
extension MapSequenceView             : LazySequenceType {}
extension MapCollectionView           : LazySequenceType {}
extension Zip2                        : LazySequenceType {}
extension EnumerateSequence           : LazySequenceType {}

Which kind of worked. I could define my eager methods on SequenceType, and then override them in LazySequenceType. And the custom structs that my lazy methods would return (LazyScanSeq) could be LazySequenceType as well.

But filter() and map() still operate eagerly on all of my custom LazySequenceTypes. I could do something like this:

public extension LazySequenceType {
  func map<T>(transform: (Self.Generator.Element) -> T) -> LazySequence<MapSequenceView<Self, T>> {
    return lazy(self).map(transform)
  }
}

But now that overrides all of the previous functions that operate specifically on Collections, etc. I could extend the struct LazySequence, and have all of my functions return LazySequences, but that doesn't make much sense to me - the structs I'm returning are structs in the same way that FilterSequenceView is: it seems clear that they shouldn't have a wrapper. I'd then probably still have to have some overarching protocol, so that I could get my scan() method on LazyForwardCollection and so on.

Maybe I'm missing something obvious here - but it seems like LazySequence is the perfect kind of target for Protocol-Oriented design. Also, lazy list processing is awesome (and useful - think about how much love there is for itertools in Python). And with recursive enums just around the corner, it's only really going to get more useful. A LazySequence protocol would make it easy to add these methods, while avoiding unexpected behaviour for eager sequences.

Thoughts?

Boost