Lazy by name, lazy by nature

When last we discussed lazy collections and sequences, I opened the article with an “ah-hah-hah, this doesn’t do what you might assume” number.1 What map and filter returned were objects that would evaluate and return results lazily on demand, so when you called them, no mapping or filtering took place right away. Instead it happened later, when you accessed the elements of a MapFilterView and its kin.

Well, turns out Apple decided that cleverly not doing what people might expect isn’t necessarily the best move, so as of beta 4, map and filter return an Array. They still take in collections and sequences of any kind, but an array is what they spit out.2

This is probably for the best. If you didn’t realize map computed lazily, you could be surprised when the results changed each time you iterated over a map using a closure like this:

let r = 1...4
var i = 0
let m = map(r) { $0 * ++i }

for e in m {
    // loops over 1, 4, 9, 16
for e in m {
    // loops over 5, 12, 21, 32

Even the Swift dev team weren’t immune to the unexpected consequences of lazyness. There were some bugs in using FilterCollectionView to populate an Array, as it took two passes, one to determine the array size needed and another to populate the array. A predicate that returned fewer results on the first pass than the second would result in buffer overrun.

Explicitly lazy

Now, with beta 4, there’s no excuses for getting surprised by lazy evaluation. If you still want to be lazy, you first need to pass your sequence or collection into a call to lazy(), which will give you back a lazy view class. What you get back depends on what you pass in – if you pass in a sequence, you’ll get back a LazySequence. If you pass in a collection, you’ll get back one of the lazy collection structs – either LazyForwardCollection, LazyBidirectionalCollection, or LazyRandomAccessCollection.

These views get progressively more features depending on the capabilities of their base. LazySequence has lazy map and filter methods that work like the old lazy map and filter functions, by returning another LazySequence object.

It also has an array property for crystalizing the lazy results into an array. Should you decide at a later point you want to iterate over the collection more than once, you should use this. If you don’t, duplicate iterations will wastefully re-run the mapping or filtering function over and over.

This also means that you can now safely write this:

var i = 0
let lf = lazy(1...5).filter { _ in
    ++i % 2 == 0
let a1 = lf.array
// a1 is [2, 4]
let a2 = lf.array
// a2 is [1, 3, 5]
let a3 = lf.array
// a3 is [2, 4]

LazyForwardCollection only adds subscript, since forward-indexable collections can’t do much more than sequences.

Note, filter still returns a sequence, even when called on the lazy collections, to avoid the heartache described above where other collection constructors assumed they could rely a collection’s length being consistent. The results of map can be a collection, because it returns a value for every element in the base no matter what. That collection inherits the index properties of the base.

LazyBidirectionalCollection and LazyRandomAccessCollection add the ability to reverse lazily. So if you wanted to filter just the first few items starting at the back of a collection, you could call lazy(col).reverse().filter { ... }.

The collection returned by reverse can be used wherever you use a regular collection. If you’re a C++ programmer and you liked the benefits of rbegin/rend, this might be what you’re looking for:

let s = "The cat in the hat"
let rs = lazy(s).reverse()
if let idx = find(rs, "h") {
    // idx points to the h of hat
    // not the h of The

The lazy factory

How you get the best lazy view class is pretty cool. lazy is actually 4 overloaded generic functions:

func lazy<S: SequenceType>(s: S) -> LazySequence<S>
func lazy<S: CollectionType where S.Index: ForwardIndexType>(s: S) -> LazyForwardCollection<S>
func lazy<S: CollectionType where S.Index: BidirectionalIndexType>(s: S) -> LazyBidirectionalCollection<S>
func lazy<S: CollectionType where S.Index: RandomAccessIndexType>(s: S) -> LazyRandomAccessCollection<S>

When you call lazy, the Swift compiler picks the most specific overload possible, preferring more specialized inherited protocols over base ones. So CollectionType beats SequenceType, because CollectionType inherits from SequenceType. CollectionType where S.Index: RandomAccessIndexType beats CollectionType where S.Index: BidirectionalIndexType because RandomAccessIndexType inherits from BidirectionalIndexType.3 What is returned is an instance of another generic class, that implements a lazy view on any specific collection or sequence.

I don’t know if there’s an official term for this, but I call it a generic factory. It’s similar to the abstract factory design pattern, in that you call a function to get back one of a range of possible concrete types. But in this case, the type determination happens at compile time, and what you get back is not an implementation of an abstract interface, but the actual appropriate concrete type.

This all feels transparent to the caller because of Swift’s type inference capabilities. You call lazy, passing in your base object, assign the result to a variable, and then merrily start using it. But you aren’t constrained to an interface exposing only the common features of the possible concrete classes, like you would be with an interface and absract factory set-up. If you passed in collection that’s capable of it, you get a reverse method.

Other than help pick the best container type, lazy doesn’t do much. There’s nothing stopping you from declaring the lazy views directly:

let r = 1...500
let l = LazyBidirectionalCollection(r)
let evens = l.filter { $0%2 == 0 }

But if you were implementing your own set of classes generated by this generic factory pattern, you could also put common set-up code in your generic factory method (or even have a generic factory class if needed).

Stride aside

By the way, the new stride function in beta 4 follows a similar pattern of returning different types at compile time from an overloaded function. But in its case, the overloading isn’t done by what you pass in. It isn’t done by types at all.

func stride<T: Strideable>(from start: T, to end: T, by stride: T.Stride) -> StrideTo<T>
func stride<T: Strideable>(from start: T, through end: T, by stride: T.Stride) -> StrideThrough<T>

These two functions differ only by the name of their middle parameter. I don’t know about you, but that this was possible was an eye opener. Score one for the Objective-C named arguments enthusiasts.

Extending lazy

So what if you have your own idea for a lazily evaluated filter to apply to sequences or collections? Well, you could extend the lazy classes to support it. We’ll look at that in the next article. Follow @airspeedswift to catch it.

  1. Which, frankly, was a bit smug of me. 
  2. Which, in this authors opinion, means they should kill the Array members map and filter, since they’re now duplicative. They could still be special-cased for performance purposes. 
  3. This behaviour can also be used to pick an optimized version of a collection algorithm that takes advantage of random access e.g. to find a subsequence inside a collection. 

6 thoughts on “Lazy by name, lazy by nature

  1. > When you call lazy, the Swift compiler picks the most specific overload possible, preferring more specialized inherited classes over base classes.

    It has to be kept in mind, though, that lazy() is a function, not a method, so due to the restrictions of overloading, the choice only accounts for the statically declared type, not for the runtime type. Admittedly, for most uses of lazy this will probably not matter.
    Nevertheless I would love to see multiple dispatch instead of static overloading 🙂

    • Good point. I would guess this is one of the reasons the lazy classes are independent of each other instead of being a hierarchy. The pain in this being you have to re-implement the members for each one even when they don’t differ (mixins could fix this).

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s