Recently, while implementing my game of immutable snake, I needed to write a function that produced an array of running totals.1 Since creating an array with reduce is all the rage these days, my first take was like this:
let start = 0
let array = [1,2,3]
let runningTotal = reduce(array, [start]) { $0 + [$0.last! + $1] }
// produces [0,1,3,6]
As you can see, that code snippet contains a force unwrap. It’s perfectly safe – you can see by inspection there’s no possible way that the array could ever be empty, so .last will never be nil. Well, except for that time in the future where I decide I don’t want the initial value at the start of the array after all, and so change reduce’s initial value to [], and kerplowie.
Obviously that’d be easy to catch in a test, and you’d probably spot the ! when making the change. But maybe there are a few lines between the change and the unwrap. Maybe it’s dependent on a variable rather than a literal. In Swift, a ! should be like a traffic Stop sign. Stop for a minute and look both ways very carefully or you might get run over by a truck. Do you really need it? Is it definitely safe, no shadow of a doubt?
The best outcome from this pause for thought is another, equally valid, equally readable, way to solve the problem that removes the need for the !.
For example, take the following snippet from the Swift section of John Siracusa’s Yosemite review:
let ages = [
"Tim": 53, "Angela": 54, "Craig": 44,
"Jony": 47, "Chris": 37, "Michael": 34,
]
let people = sorted(ages.keys, <).filter { ages[$0]! < 50 }
println(people)
There’s another way to write this that obviates the need for the ! completely:2
// dictionary's implementation of SequenceType (which is what filter takes)
// results in iterating over all the (key,value) pairs
let people = filter(ages) { $0.1 < 50 }.map { $0.0 }.sorted(<)
// or, if you find $0.1 ugly/unreadable:
let people = filter(ages) { (k,v) in v < 50 }.map { (k,v) in k }.sorted(<)
Hopefully just as concise, but no need for the force unwrap.
I couldn’t spot a similar rewrite for my runningTotal calculation, so I took the lazy option and threw it out as a question on twitter.3
First up, suggestions of using ?? or if let instead of !:
let runningTotal = reduce(array, [start]) { $0 + [($0.last ?? 0) + $1] }
let runningTotal = reduce(array, [start]) {
if let val = $0.last {
$0 + [$0.last! ?? 0 + $1]
}
else {
// what to put here?
}
}
These seem safer – but I feel like that safety can be an illusion. You know that thenil can never, ever, happen in the code as it stands. So what’s the point? Well, to kick in if you ever make a change by mistake that means you do force-unwrap a nil. But if that ever happened, you would have a bug, and sweeping it under the carpet and silently continuing could be just as bad. So perhaps what should go in that else clause is an assert, just like you’d get with the force-unwrap. In which case you’re not much better off.
How about eliminating the call to last, by passing the last value along as you go?
let runningTotal = reduce(a, (start,[start])) { ($0.0 + $1, $0.1 + [$0.0 + $1]) }.1
This version has no force-unwrap, but it’s pretty nasty to read as a one-liner. And the addition is being done twice so that could cause a performance problem for something more complex than an Int.
Speaking of performance, how about a version that uses map instead of reduce?
var runningValue = start
let runningTotal = [start] + map(a) {
runningValue += $0
return runningValue
}
“Ick, var”, you say. But you might change your mind if you ran a benchmark. This version screams ahead of the reduce version in terms of performance for arrays larger than a handful of elements. This is not surprising – Swift arrays aren’t lists. Concatenating two arrays is, in the absence of some kind of fancy optimization, O(n), and you’re doing that n times. So the innocent-looking reduce(array,[],+) version of flatmap is quadratic, so maybe best left as an educational example rather than something you actually do.
Anyway, if you must use a mutable variable, you can make yourself feel better by putting it in a generic function you know is safe and can use again and again. A function to produce a list of running totals is popular enough to find a place in plenty of standard libraries.
In Haskell, it’s called scanl. The Typelift Basis library has a very attractive recursive definition (which uses some other functions defined in Typelift, but you can probably get the idea):
public func scanl<B, A>(f : B -> A -> B) -> B -> [A] -> [B] {
return { q in { ls in
switch destruct(ls) {
case .Empty:
return q <| []
case .Destructure(let x, let xs):
return q <| scanl(f)(f(q)(x))(xs)
}
} }
}
As pretty as this is, relying on this kind of recursion in Swift as of now is probably also going to lead to performance problems. So here’s a more imperative implementation. In keeping with similar naming for reduce, I’ll call it accumulate, which is the name it has in Python:
// A version that returns any type that adheres so ExtensibleCollectionType
func accumulate
<S: SequenceType, C: ExtensibleCollectionType>
(source: S, var initial: C.Generator.Element, combine: (C.Generator.Element, S.Generator.Element) -> C.Generator.Element)
-> C {
var result = C()
result.append(initial)
for x in source {
initial = combine(initial, x)
result.append(initial)
}
return result
}
// And a default version that returns an Array, as with map
func accumulate<S: SequenceType, U>
(source: S, initial: U, combine: (U, S.Generator.Element)->U)
-> [U] {
return accumulate(source, initial, combine)
}
So there you go. I’ve started putting the re-useable functions found on this blog up in a library on github, SwooshKit, that you might want to take a look at.
- The actual code was to compute the coordinates of the snake’s body from the head through the tail. ↩
- This also has the benefit of forcing you to put the sort at the end, where it’s sorting a filtered list which ought to be quicker. Unfortunately it introduces a different performance problem, can you spot it? ↩
- Thanks to @nnnnnnnn, @jl_hfl, @CodaFi_, @rob_rix, @inthehands and @maxbucknell for all their helpful replies. ↩
Airspeed Velocity 