As teased in the previous article, suppose you want a new kind of lazy evaluation. You want to be able to generate a lazy sequence that represents the first n values of a container.
Here’s how you could add it to LazyRandomAccess:
extension LazyRandomAccessCollection {
func first_n
(n: LazyRandomAccessCollection.IndexType.DistanceType)
-> LazySequence<
PermutationGenerator<
LazyRandomAccessCollection,
Range<LazyRandomAccessCollection.IndexType>
>
> {
let start = self.startIndex
let end = min(self.endIndex, start.advancedBy(n))
let range = start..<end
let perm = PermutationGenerator(elements: self, indices: range)
return lazy(perm)
}
}
This uses PermutationGenerator, which is a lazy view class that returns a (sub-)sequence of values from a collection in the order given by another collection of indices into that collection. In first_n’s case, the indices are a range of the first n indices (or the full collection if there are fewer than n elements).
The return type of first_n is a bit crackers so I’ve broken it up over multiple lines. It returns a lazy sequence of a permutation generator of a lazy random access collection, permuted by a range of lazy random access collection indices. Phew.1 This is why the lazy function and Swift’s type inference is more than just nice to have, it’s essential. The actual types you are using in a simple function can quickly get to a point where there’s no practical way you could declare them by hand.
The practice of returning another lazy object that wraps the results is copied from the lazy map and filter members, which do the same. Why wrap PermutationGenerator in another LazySequence instead of returning it directly? Chaining mostly I think.2 Without doing that, you’d have to re-lazy the result if you wanted to run more lazy filters on it:
let r = 1...10 // with lazy wrapper let l = lazy(r).first_n(5).filter(isOdd) // without lazy wrapper let l = lazy(lazy(r).first_n(5)).filter(isOdd)
That works for a collection,3 but what about a sequence? How can we generate a new sequence that only returns the first n values?
Instead of declaring that in one shot, we’ll follow the pattern of map and filter and first declare a view:
struct FirstNSequenceView<Base: Sequence> : Sequence {
private let _n: Int
private let _base: Base
init(_ base: Base, _ n: Int) {
self._base = base
self._n = n
}
func generate()
-> GeneratorOf<Base.GeneratorType.Element> {
var i: Int = 0
var g = _base.generate()
return GeneratorOf {
++i <= self._n ? g.next() : nil
}
}
}
This uses GeneratorOf, which takes for its constructor a closure that serves up values for each call to next(). This helps avoid having to manually write a companion generator class when you implement your own sequence (IndexingGenerator is a similar helper that can be used to conform to Sequence when you implement your own Collection). In this case, generate() creates a closure that captures a counter that will count up, returning elements from the sequence until it hits n. It then returns a GeneratorOf that will call that closure each time next() is called on it. Since each time generate() is called, a new closure with a fresh i will be created, this means FirstNSequenceView conforms to the requirement of Sequence that it can be walked multiple times with multiple independent generators.
Now that we have this view, it’s easy to declare first_n for all the lazy views:
extension LazySequence {
func first_n(n: Int) -> LazySequence<FirstNSequenceView<LazySequence>> {
return lazy(FirstNSequenceView(self,n))
}
}
extension LazyForwardCollection {
func first_n(n: Int) -> LazySequence<FirstNSequenceView<LazyForwardCollection>> {
return lazy(FirstNSequenceView(self,n))
}
}
extension LazyBidirectionalCollection {
func first_n(n: Int) -> LazySequence<FirstNSequenceView<LazyBidirectionalCollection>> {
return lazy(FirstNSequenceView(self,n))
}
}
extension LazyRandomAccessCollection {
func first_n(n: Int) -> LazySequence<FirstNSequenceView<LazyRandomAccessCollection>> {
return lazy(FirstNSequenceView(self,n))
}
}
It’s a bit of a hassle having to implement each one separately, but that’s the price you pay for structs that aren’t in a hierarchy. All the more reason to factor the hard part out into a seperate view object.
Does first_n belong as a lazy view member? Unlike map and filter, it doesn’t take a closure so the laziness is less likely to bite you. Maybe take_while, a filter that returned members of an array until a supplied predicate returned false, would have been a better example. But first_n could take a lazy sequence that itself depended on a closure, so the laziness of first_n could still come as a surprise. Also, the chaining is nice. Does this mean other lazy sequences like enumerate should migrate into being lazy class members? I dunno, maybe.
Without the chaining, you have to wrap the results in a function call. But the function call goes on the left, while chained calls go on the right, which results in a confusing ping-pong effect:
let l = lazy(first_n(lazy(r).filter(isOdd),5)).map(...)
The ordering of this is not obvious at first glance, but it’s filter, then first_n, then map. But then where does it end? Should everything get piled into the lazy classes just to benefit from chaining? Nah. The better solution is to implement a pipe forward operator, of which more some other time.
-
I have a nagging feeling this could be simplified. The Swift standard lazy functions don’t look quite this bad, they use a type of S instead of a type of themselves for the inner parts of the return values of
mapandfilter. But then the compiler doesn’t completely faithfully represent the generic types in the declarations you see in Xcode (which is why there is a lot ofT == Tin what we see of the Swift standard library). Let me know if can figure out a better way. ↩ - Also, if someone option-clicks the results, it’s obvious at a glance that the results are lazy. ↩
- In fact, while a variant of the permutation version would work for forward and bidirectional collections as well, it’s not a good idea, because advance will take O(n) which is unnecessary, as the next version will show. ↩
Airspeed Velocity 