objc.io

00:06 Today we're going to experiment with reactive data structures. In a previous episode, we created SortedArrayController, a results controller that can drive a table view and handles stuff like sorting and filtering. We want to write an alternative to this results controller — this time using reactive components.

00:52 We'll use a small part of ReactiveSwift and build data structures on top of that. We mainly need a MutableProperty for this, which can be found in most reactive frameworks.

01:32 It's going to take some work to get to a results controller, so bear with us as we lay the groundwork. We'll start by creating a linked list and continue by making it reactive.

List

01:49 The basic non-reactive linked list is an enum that's generic over whatever we want to store in it. The two cases are an empty list and a value, the latter of which is usually called cons. We have to mark the cons case as indirect because it's recursive:

enum List<A> {
    case empty
    indirect case cons(A, List<A>)
}

02:32 We define a list:

let list: List<Int> = .cons(1, .cons(2, .cons(3, .empty)))

03:06 reduce would be a powerful method to add to the list type, because we can use that to build other functionality. The method is generic over the result value; it takes an initial value and a function that combines an intermediate result and an element from the list, and finally it returns the result:

extension List {
    func reduce<B>(_ initial: B, _ combine: (B, A) -> B) -> B {
        
    }
}

04:09 reduce abstracts away the recursive nature of our list structure. No matter the result we want from reduce, we only need to tell the method how to combine one cons element with a result type and it will loop through the recursive list for us. Once we have reduce, we can very quickly define other functions, like sum and filter.

04:51 To implement reduce, we switch over the list. In the empty case, there's nothing else to do but return the initial value:

extension List {
    func reduce<B>(_ initial: B, _ combine: (B, A) -> B) -> B {
        switch self {
        case .empty:
            return initial
        // ...
        }
    }
}

05:19 In the cons case, we use the combine function with the initial value and the current element and then recurse with the tail (the rest of the list):

extension List {
    func reduce<B>(_ initial: B, _ combine: (B, A) -> B) -> B {
        switch self {
        case .empty:
            return initial
        case let .cons(value, tail):
            let intermediate = combine(initial, value)
            return tail.reduce(intermediate, combine)
        }
    }
}

06:18 We can try this out and add up the elements in our list:

let list: List<Int> = .cons(1, .cons(2, .cons(3, .empty)))
list.reduce(0, +) // returns 6

Reactive List

06:38 If we want to append something to the list and then want to know the new sum, we have to reduce the entire list again. We can avoid that by making a new reactive version of the list. The empty case stays the same, but we wrap the tail in a MutableProperty:

enum RList<A> {
    case empty
    indirect case cons(A, MutableProperty<RList<A>>)
}

08:11 For ease of use, we add an initializer that loops over an array and adds each element to the list. Because we have to add elements by prepending them to the list, we reverse the array before looping over it so that elements are listed in the correct order:

extension RList {
    init(array: [A]) {
        self = .empty
        for element in array.reversed() {
            self = .cons(element, MutableProperty(self))
        }
    }
}

let sample = RList(array: [1,2,3])

09:46 The next step is to write reduce for the reactive list. We copy and paste the non-reactive version, and next we'll update it to work with RList. Because we want to be able to observe the result, we wrap it in a Property. This return type deviates from the conventional reduce method because we don't just get a result value out:

extension RList {
    func reduce<B>(_ initial: B, _ combine: (B, A) -> B) -> Property<B> {
        let result = MutableProperty(initial)
        switch self {
            // ...
        }
        return Property(result)
    }

}

11:18 We don't want to recursively call reduce and introduce another MutableProperty in each recursion. Instead, we only create one MutableProperty for the result and move the recursion into a helper function, reduceH, which writes into that result.

12:51 In the empty case we don't return intermediate, the value built up thus far. Instead, we write it into the result. In the cons case, we combine its value with the current intermediate and perform the recursion by calling reduceH with the rest of the list and the new intermediate:

extension RList {
    func reduce<B>(_ initial: B, _ combine: @escaping (B, A) -> B) -> Property<B> {
        let result = MutableProperty(initial)
        func reduceH(list: RList<A>, intermediate: B) {
            switch list {
            case .empty:
                result.value = intermediate
            case let .cons(value, tail):
                let newIntermediate = combine(intermediate, value)
                reduceH(list: tail.value, intermediate: newIntermediate)
            }
        }
        reduceH(list: self, intermediate: initial)
        return Property(result)
    }
}

Observing the Reactive List

14:52 When we call reduce on our sample list, we get a Property out with the result as its value. Now we can try to observe it for updates. To do so, we'll append a value to the list.

16:12 We write append as a top-level function and not in the RList namespace because it works with a MutableProperty<RList>:

func append<A>(_ value: A, to list: MutableProperty<RList<A>>) {
    switch list.value {
    case .empty:
        list.value = .cons(value, MutableProperty(.empty))
    case .cons(_, let tail):
        append(value, to: tail)
    }
}

17:57 In order to use the append method, we have to wrap our sample list in a MutableProperty. Before appending, we want to observe the reduce result, which is also a MutableProperty. By doing some RxSwift stuff — we flatMap over it and take the latest value — we can set up an observer of the reduce result:

let sample = MutableProperty(RList(array:[1,2,3]))
let sum = sample.flatMap(.latest) { $0.reduce(0, +) }
sum.value // 6
sum.signal.observeValues { print($0) }
append(4, to: sample) // no prints yet

19:38 We don't see any prints because we're not reacting to any changes yet: the value of sum isn't actually updated to 10. To fix this, we have to observe the tail of the list within our reduce method.

20:24 We observe the tail of each cons case and perform the same reduce operation whenever any tail updates:

// ...
case let .cons(value, tail):
    let newIntermediate = combine(intermediate, value)
    tail.signal.observe { newTail in
        reduceH(list: newTail, intermediate: newIntermediate)
    }
    reduceH(list: tail.value, intermediate: newIntermediate)
// ...

21:48 The value 10 is now printed in the console. What's interesting about what happens here is that only the newly appended element 4 is added to the previous sum. We can illustrate that by printing a line anytime an addition is executed:

func add(_ l: Int, _ r: Int) -> Int {
    print("going to add: \(l) and \(r)")
    return l + r
}

let sample = MutableProperty(RList(array:[1,2,3]))
let sum = sample.flatMap(.latest) { $0.reduce(0, add) }
sum.signal.observeValues { print($0) }
print("–––")
append(4, to: sample)

/*
going to add: 0 and 1
going to add: 1 and 2
going to add: 3 and 3
–––
going to add: 6 and 4
10
*/

23:05 As we can see, the initial elements of the list are first added up. When we append 4 to the list, only the previous result and the new value are added, and RList didn't have to recompute the entire sum.

Pros and Cons

23:19 In academic literature, this kind of programming is called incremental programming. More of this already exists in Swift, like the GlueKit library created by our recent guest, Károly, which uses incremental programming.

23:51 Using reactive properties and observers to react to small changes can be more efficient — and therefore faster — when performing small mutations on big data structures. However, this approach comes at a price, because we're keeping the entire graph of observers in memory.

24:50 Depending on what our code needs to do and the kind of data we expect, we can choose between roughly three approaches. In imperative programming, we need to keep everything — like the sample array and its sum — in sync manually. With an architecture like Elm, or with functional programming, we keep computing a desired end result and then do some differentiating to see what actually changes. Today's example of reactive or declarative programming showed a way to avoid diffing and to mutate a data structure in a time-efficient way, but it also increases our memory usage.

25:43 In an upcoming episode, we'll build a reactive array and drive a table view with it.