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.
- Which, frankly, was a bit smug of me. ↩
-
Which, in this authors opinion, means they should kill the
Array
membersmap
andfilter
, since they’re now duplicative. They could still be special-cased for performance purposes. ↩ - 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. ↩
> 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).
[…] teased in the previous article, suppose you want a new kind of lazy evaluation. You want to be able to generate a lazy sequence […]
[…] they were changed to return eagerly-evaluated results, filter and map have returned arrays, no matter what. This is a […]
[…] For more on Swift’s lazy types, see this article ↩ […]
[…] this article is out of date as of Swift 1.0 beta 4. Read this updated version […]