How are swift lazy collections implemented

An attempt at being lazy.

There are lots of articles about lazy collections in swift but none of them explain how lazy collections really work, how are they implemented, and how hard would it be to roll our own lazy collection, In this article I will try to answer the above questions and implement a custom lazy collection.

Lets start by analyzing the built-in lazy collection implementation, when you call lazy, swift compiler will select the correct overload lazy method (there are 4 overloads total), in case of an array the lazy overload that the compiler selects will return a LazyRandomAccessCollection, This lazy collection holds the original array, The LazyRandomAccessCollection also knows how to create the correct generator, the interesting part starts when we call filter on this collection.

var lazyArray = lazy([1,2,3,4])
var lazyFilter = lazyArray.filter{$0 > 2}

Calling filter returns a LazySequence<FilterSequenceView<S>>, FilterSequenceView is a struct that holds the array and the closure passed to filter function, we can confirm that by doing some reflection.

lazyFilter //{[…], (Function)}
reflect(lazyFilter)[0].1[0].1.value //[1,2,3,4]
reflect(lazyFilter)[0].1[0].1.value //(Function)

Reflecting on the lazy filter (by using magic numbers) will return the original array and a Function, the Function is the closure passed to filter.

The interesting bit about filter comes when we concatenate them, these multiple filter closure that are concatenated will be called serially on each element passed.

var lazyArray = lazy([1,2,3,4])
var lazyFilter = lazyArray.filter{$0 > 2}.filter{$0 < 5}.filter{$0 < 4}

When we call Generator’s next function on lazyFilter each element in the lazyArray will pass through each filter starting by the first one, if the element passes all the filters then it will be used as the next item.

So to recap, the following are the main facts about lazy collections.

1. The lazy collection will hold the original collection passed
2. When calling filter on the lazy collection, a filter view will be created to hold the collection and the filter closure.
3. The original array elements are passed through the filter closure saved in the lazy view each time next function is called.
4. In case of multiple filter closure, the items will be passed to all the filter starting by the first one on the left.

A lazy collection implementation

Since the implementation is quite long I am gonna discuss the main parts here and post the whole thing as a gist.

The implementation is not 100% api equivalent to the swift built-in ones and I don’t intent it to be, The main idea of it is to try to explain and investigate how lazy collection work (or how I think they do).

Firstly we create a MyLazyArray and pass it an array, This lazy array will act as a wrapper to the passed array, MyLazyArray defines the filter method, calling filter creates a MyFilterArrayView object, This fitlter view as it name implies is the lazy sequence implementation for the array.

MyFilterArrayView holds the array and the closure passed to filter function. It implements both SequenceType and GeneratorType protocols, and it also declares the filter function, calling this filter function will create a new MyFilterArrayView, this newly created view will have the original array, the closure passed to filter and a reference to the MyFilterArrayView that created it, the later reference will be used to recursively call the previous closure passed to filter function.

MyFilterArrayView.next is defined as follows.

func next() -> Int? {
   for i in _currentIndex..<_array!.count {
       _currentIndex++
       if let filtered = filterItem(_array![i]) {
           return filtered
       }
   }
   return nil
}

It iterates over all the elements in the original array and calls filterItem for each of these elements, filterItem is defined bellow.

func filterItem(item: Int) -> Int? {
   if let lazyFilter = _lazyFilter {
       if lazyFilter.filterItem(item) == nil {
           return nil
       }
   }
   return _closure(item) ? item : nil
} 

filterItem first calls the same method on the referenced lazy view object (remember from above we discussed how each newly created lazy view hold the reference of its creator), if an item is returned then it pass on, else the filter operation stops.

The above deep first filter closure execution is crucial since an item has to pass through all filter closure tests in order to be considered as a viable output from a next function call.

Conclusion

I agree that this is not the best explanation for lazy functionality, But then again lazy is not the easiest concept to grasp, However I hope that I provided some insight on how lazy collections are implemented. The complete code for the article can be found as a Gist I would strongly advice to check it out for better understanding.

If you like this post heart it bellow ❤
@ifnottrue