Swift Evolution Proposal SE-0094 has been implemented in Swift 3, giving us an easy way to create lazy lists based on a starting value and a generator. One particularly cool thing about lazy lists is that you can have an "infinite list" — one that will keep giving you elements for any index. These are fun to play with, and can be useful to write generalized code for transforming sequences.

The Basics

A classic example of how to use an infinite list is to add numerical context to items in a list. In fact, the Swift standard library provides such a function for Sequence, called enumerated, which returns a list of tuples combining the natural numbers and the elements of the Sequence itself. We can implement our own enumerated easily using these new Swift functions.

extension Sequence {
    func enumerated_() -> AnySequence<(Int, Self.Iterator.Element)> {
        return AnySequence(zip(sequence(first: 0, next: { $0 + 1 }), self))
    }
}

for (n, c) in "Swift".characters.enumerated_() {
    print("\(n): '\(c)'")
}

this prints:

0: 'S'
1: 'w'
2: 'i'
3: 'f'
4: 't'

We even got a chance to use a sweet type eraser, AnySequence.

You could accomplish the same thing by looping and incrementing a counter, but this idea of an infinite list as an object is a really nice way of thinking about it.

A Lazy Drunk

You can also use lazy sequences to work with lists whose size is unknown, and could potentially be infinite. Suppose you wanted to model how a drunk NPC walks. You might model the NPC's path (in a 2D plane) as a Markov chain, one in which the next state is equally likely to be one step in any direction from the current state. A lazy sequence would let you generate a path of any size you want, or let you easily search or wait for specific events, such as the NPC reaching a certain point on the map.

protocol MarkovChain {
    associatedtype State
    var state: State { get }
    func next() -> Self
}

struct Tile {
    let x: Int
    let y: Int
}

struct DrunkardNPC: MarkovChain {
    typealias State = Tile
    let state: Tile

    func next() -> DrunkardNPC {
        let nextTile: Tile

        switch(arc4random_uniform(4)) {
            case 0: //Left
                nextTile = Tile(x: state.x - 1, y: state.y)
                break
            case 1: //Right
                nextTile = Tile(x: state.x + 1, y: state.y)
                break
            case 2: //Down
                nextTile = Tile(x: state.x, y: state.y - 1)
                break
            case 3: //Up
                nextTile = Tile(x: state.x, y: state.y + 1)
                break
            default: //arc4random_uniform is broken, don't do anything
                nextTile = state
                break
        }

        return DrunkardNPC(state: nextTile)
    }
}

Now, we can generate a list of tiles that represent a random path 20 tiles long like so:

let bar = Tile(x: 0, y: 0)
let drunkard = DrunkardNPC(state: bar)
let drunkardsPath = sequence(first: drunkard, next: { $0.next() })

for tile in drunkardsPath.prefix(20) {
    print(tile)
}

How about if we don't know how long of a path we want? Say our drunkard stumbles out of the bar every day at noon for some fresh air. If he walks too far away from the bar (say, 6 tiles), or for too long (say, 15 steps), he will sober up and immediately return.

We can add a distance(from:) method on Tile:

func distance(from: Tile) -> Int {
    return abs(x - from.x) + abs(y - from.y)
}

and generate a path he walks while drunk, satisfying the above requirements, like this:

extension Sequence {
    func takeWhile(_ p: (Self.Iterator.Element) -> Bool) -> [Self.Iterator.Element] {
        var taken: [Self.Iterator.Element] = []

        for x in self {
            guard p(x) else { break }
            taken.append(x)
        }

        return taken
    }
}

let refreshingWalk = drunkardsPath.enumerated().takeWhile({ (step, drunkard) in
    step < 15 && drunkard.state.distance(from: bar) < 6
})

for (n, tile) in refreshingWalk {
    print("\(n) - \(tile)")
}

---

Exercise for the reader: Notice that this doesn't include the "final" tile 6 away or #100, since on that tile our NPC is now sober. What if you wanted to see what the final step was, to continue the path with a sober step-generator?

---

With this, we can perform operations on our probability-based lists, or even on many of these lists at one. For example, we could easily generate a number of simulations, and get the average length of the NPC's path while drunk.

let randomRefreshingWalk = {
    drunkardsPath.enumerated().takeWhile({ (step, drunkard) in
        step < 15 && drunkard.state.distance(from: bar) < 6
    })
}

let numTrials = 20
let trials = (0..<numTrials).map({ _ in randomRefreshingWalk() })

let averageLength = Double(
    trials.map({ $0.count })
    .reduce(0, combine: +)
)
/ Double(numTrials)

print("Average path length: \(averageLength)")

Here, we extract the creation of a drunken path into its own inline function, so that each time we need a new random walk, we can simply call it.

Swift is Only Sometimes Lazy

One thing to watch out for is that not all functions and data structures in Swift are lazy. In fact, most aren't, so you need to be careful when using infinite lists, or you could end up with a non-terminating program.

Infinite lists are a great tool for modeling both mathematical and practical data, and can even help show how the two intersect. In addition to that, they're just plain cool! If you enjoyed this mini-exploration, I highly recommend checking out a lazy-by-default language, such as Haskell. It allows for lots of elegant ways to combine functions, and gives a perspective on coding that is very different from the "avoid infinite loops!" rule of imperative programming.