Wrap sequences in Swift

Hello. Today we want to share the translation prepared on the eve of the launch of the course “iOS Developer. Advanced Course . ” Go!

One of the main advantages of Swift's protocol-based design is that it allows us to write generic code that is compatible with a wide range of types, and not specifically implemented for everyone. Especially if such a common code is intended for one of the protocols, which can be found in the standard library, which will allow using it with both built-in types and user-defined ones.

An example of such a protocol is Sequence, which is accepted by all types of standard libraries that can be iterated, such as Array, Dictionary, Set, and many others. This week, let's look at how we can wrap Sequence in universal containers, which will allow us to encapsulate various algorithms at the core of easy-to-use APIs.

The art of being lazy

It's pretty easy to get confused by thinking that all sequences are similar to Array, since all elements are instantly loaded into memory when the sequence is created. Since the only requirement of the Sequence protocol is that receivers must be able to iterate, we cannot make any assumptions about how elements of an unknown sequence are loaded or stored.

For example, as we covered in Swift Sequences: The Art of Being Lazy , sequences can sometimes load their elements lazily - either for performance reasons or because it is not guaranteed that the entire sequence can fit in memory. Here are some examples of such sequences:

//   ,          ,           . let records = database.records(matching: searchQuery) //     ,       ,      . let folders = folder.subfolders //   ,     ,            . let nodes = node.children
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Since all of the above sequences are lazy for some reason, we would not like to force them into an array, for example, by calling Array (folder.subfolders). But we still may want to modify and work with them in different ways, so let's look at how we can do this by creating a type of sequence wrapper.

Foundation creation

Let's start by creating a basic type that we can use to create all kinds of convenient APIs on top of any sequence. We will call it WrappedSequence, and it will be a universal type containing both the type of the sequence that we wrap and the type of element that we want our new sequence to create.

The main feature of our wrapper will be its IteratorFunction, which will allow us to take control of the search for the base sequence - changing the Iterator used for each iteration:

 struct WrappedSequence<Wrapped: Sequence, Element>: Sequence { typealias IteratorFunction = (inout Wrapped.Iterator) -> Element? private let wrapped: Wrapped private let iterator: IteratorFunction init(wrapping wrapped: Wrapped, iterator: @escaping IteratorFunction) { self.wrapped = wrapped self.iterator = iterator } func makeIterator() -> AnyIterator<Element> { var wrappedIterator = wrapped.makeIterator() return AnyIterator { self.iterator(&wrappedIterator) } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

As you can see above, Sequence uses a factory pattern so that each sequence creates a new iterator instance for each iteration - using the makeIterator () method.

Above, we use the AnyIterator type of the standard library, which is an iterator of type erasure that can use any basic IteratorProtocol implementation to get Element values. In our case, we will create an element by calling our IteratorFunction, passing as an argument our own iterator of the wrapped sequence, and since this argument is marked as inout, we can change the base iterator in place inside our function.

Since WrappedSequence is also a sequence, we can use all the functions of the standard library related to it, such as iterating over it or transforming its values ​​using map:

 let folderNames = WrappedSequence(wrapping: folders) { iterator in return iterator.next()?.name } for name in folderNames { ... } let uppercasedNames = folderNames.map { $0.uppercased() }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Now let's get started with our new WrappedSequence!

Prefixes and Suffixes

When working with sequences very often there is a desire to insert a prefix or suffix in the sequence with which we work - but wouldn’t it be great if we could do this without changing the main sequence? This can lead to better performance and allows us to add prefixes and suffixes to any sequence, not just general types like Array.

Using WrappedSequence, we can do this quite easily. All we need to do is extend Sequence with a method that creates a wrapped sequence from an array of elements to insert as a prefix. Then, when we iterate over, we start iterating over all the prefix elements before continuing with the base sequence - like this:

 extension Sequence { func prefixed( with prefixElements: Element... ) -> WrappedSequence<Self, Element> { var prefixIndex = 0 return WrappedSequence(wrapping: self) { iterator in //        ,   ,   ,   : guard prefixIndex >= prefixElements.count else { let element = prefixElements[prefixIndex] prefixIndex += 1 return element } //           : return iterator.next() } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Above, we use a parameter with a variable number of arguments (adding ... to its type) to allow passing one or more elements to the same method.

In the same way, we can create a method that adds a given set of suffixes to the end of the sequence - first by performing our own iteration of the base sequence and then iterating over the suffixed elements:

 extension Sequence { func suffixed( with suffixElements: Element... ) -> WrappedSequence<Self, Element> { var suffixIndex = 0 return WrappedSequence(wrapping: self) { iterator in guard let next = iterator.next() else { //    ,     nil      : guard suffixIndex < suffixElements.count else { return nil } let element = suffixElements[suffixIndex] suffixIndex += 1 return element } return next } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

With the two methods mentioned above, we can now add prefixes and suffixes to any sequence that we want. Here are some examples of how our new APIs can be used:

 //      : let allFolders = rootFolder.subfolders.prefixed(with: rootFolder) //       : let messages = inbox.messages.suffixed(with: composer.message) //       ,      : let characters = code.prefixed(with: "{").suffixed(with: "}")
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Although all of the above examples can be implemented using specific types (such as Array and String), the advantage of using our WrappedSequence type is that everything can be done lazily - we do not perform any mutations or evaluate any sequences to add our prefixes or suffixes - which can be really useful in situations critical to performance, or when working with large data sets.

Segmentation

Next, let's look at how we can wrap sequences to create segmented versions of them. In certain iterations, it is not enough to know what the current element is - we may also need information about the next and previous elements.

When working with indexed sequences, we can often achieve this using the enumerated () API, which also uses a sequence wrapper to give us access to both the current element and its index:

 for (index, current) in list.items.enumerated() { let previous = (index > 0) ? list.items[index - 1] : nil let next = (index < list.items.count - 1) ? list.items[index + 1] : nil ... }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

However, the above technique is not only quite verbose in terms of invocation, it also relies on the use of arrays again - or at least some form of sequence that gives us random access to its elements - that many sequences, especially lazy ones, not welcome.

Instead, let's use our WrappedSequence once again - to create a sequence wrapper that lazily provides segmented views in its base sequence, tracking previous and current elements and updating them as the search continues:

 extension Sequence { typealias Segment = ( previous: Element?, current: Element, next: Element? ) var segmented: WrappedSequence<Self, Segment> { var previous: Element? var current: Element? var endReached = false return WrappedSequence(wrapping: self) { iterator in //        ,      ,   ,        ,     . guard !endReached, let element = current ?? iterator.next() else { return nil } let next = iterator.next() let segment = (previous, element, next) //     ,    ,      : previous = element current = next endReached = (next == nil) return segment } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Now we can use the above API to create a segmented version of any sequence whenever we need to either look forward or backward when doing an iteration. For example, here is how we can use segmentation so that we can easily determine when we have reached the end of the list:

 for segment in list.items.segmented { addTopBorder() addView(for: segment.current) if segment.next == nil { //   ,     addBottomBorder() } } ```swift        ,   .    ,               : ```swift for segment in path.nodes.segmented { let directions = ( enter: segment.previous?.direction(to: segment.current), exit: segment.next.map(segment.current.direction) ) let nodeView = NodeView(directions: directions) nodeView.center = segment.current.position.cgPoint view.addSubview(nodeView) }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Now we are starting to see the true power of wrapping sequences - in that they allow us to hide more and more complex algorithms in a really simple API. All the caller needs to segment the sequence is access the segmented property in any Sequence, and our base implementation will take care of the rest.

Recursion

Finally, let's look at how even recursive iterations can be modeled using sequence wrappers. Suppose we wanted to provide a simple way to recursively iterate over a hierarchy of values ​​in which each element in the hierarchy contains a sequence of child elements. It can be quite difficult to do it right, so it would be great if we could use one implementation to perform all such iterations in our code base.

Using WrappedSequence, we can achieve this by extending Sequence with a method that uses the same generic type constraint to ensure that each element can provide a nested sequence that has the same iterator type as our original. To be able to dynamically access each nested sequence, we will also ask the caller to specify KeyPath for the property that should be used for recursion, which will give us an implementation that looks like this:

 extension Sequence { func recursive<S: Sequence>( for keyPath: KeyPath<Element, S> ) -> WrappedSequence<Self, Element> where S.Iterator == Iterator { var parentIterators = [Iterator]() func moveUp() -> (iterator: Iterator, element: Element)? { guard !parentIterators.isEmpty else { return nil } var iterator = parentIterators.removeLast() guard let element = iterator.next() else { //          ,    ,      : return moveUp() } return (iterator, element) } return WrappedSequence(wrapping: self) { iterator in //       ,      ,      : let element = iterator.next() ?? { return moveUp().map { iterator = $0 return $1 } }() //       ,  ,         ,         . if let nested = element?[keyPath: keyPath].makeIterator() { let parent = iterator parentIterators.append(parent) iterator = nested } return element } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Using the above, we can now recursively iterate over any sequence, regardless of how it is built inside, and without having to load the entire hierarchy in advance. For example, here is how we could use this new API to recursively iterate through a folder hierarchy:

 let allFolders = folder.subfolders.recursive(for: \.subfolders) for folder in allFolders { try loadContent(from: folder) }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

We can also use it to iterate over all nodes of the tree or to recursively traverse a set of database records - for example, to list all user groups in an organization:

 let allNodes = tree.recursive(for: \.children) let allGroups = database.groups.recusive(for: \.subgroups)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

One thing we need to be careful about when it comes to recursive iterations is to not allow circular references - when a certain path returns us to an element that we have already encountered - which will lead us to an infinite loop.

One way to fix this is to keep track of all occurring elements (but this can be memory problematic), to ensure that there are no circular references in our data set, or to handle such cases each time from the call side (using break, continue or return to complete any cyclic iterations).

Conclusion

Sequence is one of the simplest protocols in the standard library - it requires only one method - but it is still one of the most powerful, especially when it comes to how much functionality we can create based on it. Just as the standard library contains wrapper sequences for things like enumerations, we can also create our own wrappers - which allow us to hide advanced functionality with really simple APIs.

Although abstractions always have a price, and it’s important to consider when it’s worth (and perhaps more importantly when not worth it) to introduce them, if we can build our abstractions directly on top of what the standard library provides - using the same conventions - then these abstractions are usually more likely to stand the test of time.