A few weeks back, @SwiftLDN ran a hands-on, and the challenge was a calculation of the Luhn checksum for credit card numbers in Swift. Implementing this algorithm features as an early problem to solve in some functional programming tutorials, and can serve as a nice example for contrasting different programming styles.
(If you’re already familiar with more functional-style Swift, you’ll already know about many of the techniques in this article, but I’m also going to use it as a jumping off point to talk more about overloading, and also performance.)
Here’s wikipedia’s description of the algorithm:
- From the rightmost digit, which is the check digit, moving left, double the value of every second digit; if the product of this doubling operation is greater than 9 (e.g., 8 × 2 = 16), then sum the digits of the products (e.g., 16: 1 + 6 = 7, 18: 1 + 8 = 9).
- Take the sum of all the digits.
- If the total modulo 10 is equal to 0 (if the total ends in zero) then the number is valid according to the Luhn formula; else it is not valid.
Let’s start by writing an imperative version, and then getting all judgmental about it:
func checksum(ccnum: String) -> Bool {
var sum = 0
var idx = 0
for char in reverse(ccnum) {
if let digit = String(char).toInt() {
if (++idx)%2 == 0 {
sum += digit < 5
? digit * 2
: digit * 2 - 9
}
else {
sum += digit
}
}
}
return sum % 10 == 0
}
let ccnum = "4012 8888 8888 1881"
println( checksum(ccnum) ? "👍" : "👎" )
This bit of code is perfectly adequate. It already uses some of Swift’s features to make it simpler and safer, such as for ... in, an if let binding to check if the character was a digit, and reverse to reverse the string.
But it’s not totally obvious at first glance that it’s correct. The mutable var sum means you have to run through the whole function in your head to understand what it does, figuring out how sum gets changed over time. Debugging it would probably involve stepping through line by line.
“But this is Swift!”, you say. “We should be avoiding var, and using map and reduce and stuff.” So, maybe something like this:
func checksum(ccnum: String) -> Bool {
let digits = map(ccnum) {
String($0).toInt()
}.filter {
$0 != nil
}.map {
$0!
}
let checksumDigits = map(enumerate(reverse(digits))) {
(idx: Int, digit: Int) -> Int in
if idx%2 == 0 {
return digit
}
else {
return digit < 5
? digit * 2
: digit * 2 - 9
}
}
return checksumDigits.reduce(0,+) % 10 == 0
}
let ccnum = "4012 8888 8888 1881"
println( checksum(ccnum) ? "👍" : "👎" )
Well, that’s is a bit of a dog’s breakfast. I’d say it’s worse than the version with the for loop, in terms of readability. But we can fix that.
Let’s start with the first part – the conversion of the string to an array of digits. It contains a force unwrap, often a sign there’s a better way. Needing to map and filter simultaneously is a pretty common problem. Common enough that Haskell has a function that combines the two, called mapMaybe (Maybe in Haskell is like Swift’s Optional type). Like map, it takes a function that transforms the elements, but that function returns an optional, and if it returns nil for an element, that element is not included in the result.
Here’s an equivalent function in Swift, which I’ll call mapSome: 1
func mapSome
<S: SequenceType, D: ExtensibleCollectionType>
(source: S, transform: (S.Generator.Element)->D.Generator.Element?)
-> D {
var result = D()
for x in source {
if let y = transform(x) {
result.append(y)
}
}
return result
}
let toInt = { (c: Character)->Int? in String(c).toInt() }
let ccnum = "4012 8888 8888 1881"
let digits: [Int] = mapSome(ccnum, toInt)
// digits = [4,0,1,2,8,8,8,8,8,8,8,8,1,8,8,1]
Note, when declaring digits, you have to give the type of [Int], because mapSome is written to work on any kind of container that supports the ExtensibleCollectionType – but you have to specify which type of extensible container you want to use (in this case, an array).2
Next, the part that applies a transformation (doubling, and combining double digits) to every other digit. One way to solve this is with another variant of map that only maps every nth entry.3
In fact you could generalize that even further, and write a map that took a function that determined if a given index should be transformed:
func mapIfIndex
<S: SequenceType, C: ExtensibleCollectionType
where S.Generator.Element == C.Generator.Element>
(source: S, transform: S.Generator.Element -> S.Generator.Element, ifIndex: Int -> Bool)
-> C {
var result = C()
for (index,value) in enumerate(source) {
if ifIndex(index) {
result.append(transform(value))
}
else {
result.append(value)
}
}
return result
}
With this, we can write a version of map that transforms every nth entry:
func mapEveryNth
<S: SequenceType, C: ExtensibleCollectionType
where S.Generator.Element == C.Generator.Element>
(source: S, n: Int, transform: S.Generator.Element -> C.Generator.Element)
-> C {
// enumerate starts from zero, so for this to work with the nth element,
// and not the 0th, n+1th etc, we need to add 1 to the ifIndex check:
let isNth = { ($0 + 1) % n == 0 }
return mapIfIndex(source, transform, isNth)
}
let double = { $0*2 }
let doubleEveryOther: [Int]->[Int] = { mapEveryNth($0, 2, double) }
let doubled = doubleEveryOther([1,2,3,4,5])
// doubled = [1,4,3,8,5]
Notice how, in the snippet above, instead of applying the map directly to some values, doubleEveryOther is defined as a function that takes an array of Ints, and returns a new array with every other one doubled. This is then used on an array of Ints. Bear this in mind for later.
Finally, we need to sum the result, and then check it’s a multiple of 10. Functions to do that are easy enough:
func sum
<S: SequenceType
where S.Generator.Element: IntegerType>
(nums: S) -> S.Generator.Element {
return reduce(nums, 0) { $0.0 + $0.1 }
}
let summed = sum(1...10) // 55
func isMultipleOf<T: IntegerType>(of: T) -> T -> Bool {
return { $0 % of == 0 }
}
let isMultipleOfTen = isMultipleOf(10)
isMultipleOfTen(5) // false
isMultipleOfTen(20) // true
Note this time, isMultipleOf is a function that returns another function – isMultipleOf(10) returns a function that tests whether a number is a multiple of 10. isMultipleOf(5) would return a function that tested if a number were a multiple of 5.
OK so now we have a function that can filter out digits, one that transforms every other value, one that sums integers, and one that checks if the result is a multiple of 10. All we need to do is string them all together.
The simple way would be to store each intermediate result in a variable:
func checksum(ccnum: String) -> Bool {
let digits: [Int] = mapSome(ccnum, toInt)
let reversed = reverse(digits)
let transformed: [Int] = mapEveryNth(reversed, 2) { i in
i < 5
? i * 2
: i * 2 - 9
}
let summed = sum(transformed)
return isMultipleOf(10)(summed)
}
That’s starting to look good. But those variable declarations are kinda cluttering up the place.
You could ditch the intermediate variables and write the whole thing like this:
func checksum(ccnum: String) -> Bool {
let doubleAndCombine = { i in
i < 5
? i * 2
: i * 2 - 9
}
return isMultipleOf10(sum(mapEveryNth(reverse(mapSome(ccnum, toInt) as [Int]), 2, doubleAndCombine) as [Int]))
}
Obviously that’s ridiculous – it’s not just impossible to read, it’s impossible to write. It took me a good few minutes plugging away, counting all the parenthesis, like an animal.4
Luckily there’s a handy operator we can define that makes chaining function calls together a lot easier: pipe forward.
It looks like this:
infix operator |> {
associativity left
}
public func |><T,U>(t: T, f: T->U) -> U {
return f(t)
}
Read that function definition as “take any value of type T as an argument on the left, and any function that takes type T and returns another value of type U on the right, apply the function to the value and return the result”.
This allows us to pipe the result of one function into the input of another , like so:
// returns 30 (sum of 1 to 5, doubled)
1...5 |> sum |> double
Using this, we can rewrite checksum again:
func checksum(ccnum: String) -> Bool {
let doubleAndCombine = { i in
i < 5
? i * 2
: i * 2 - 9
}
return ccnum
|> { mapSome($0, toInt) as [Int] }
|> reverse
|> { mapEveryNth($0, 2, doubleAndCombine) as [Int] }
|> sum
|> isMultipleOf(10)
}
Here, for the functions that take more than one parameter, we have to wrap them in a closure expression to turn them into a temporary function that takes one parameter, the one coming through the pipeline. To read more about pipe forward, try Kris Johnson’s post about it.
One last take. Instead of using the pipe forward, we could use function composition. We can define an operator that takes two functions and returns a new function that is the result of applying first one, then the other. That is, if f and g are functions that take one argument, we could compose them as a new function h that was equivalent to g(f(x)).
infix operator • {
associativity left
}
public func • <T, U, V> (g: U -> V, f: T -> U) -> T -> V {
return { x in g(f(x)) }
}
// define a new function that takes a range of Ints, sums
// them, then doubles the result
let sumThenDouble: Range -> Int = double • sum
sumThenDouble(1...5) // returns 30
Unless you’re too busy being incandescent with rage about someone defining an operator using •,5 you’ll notice that, unlike |>, composed functions read from right to left, to match the order if you wrote the application out in full i.e. g(f(x)). There’s nothing magic about this – it’s just how the • function was defined above, with g as the left-hand argument and f as the right-hand one.
You could also define a pipe backwards operator, <|, to go in a similar direction. The Functional Swift book defines >>> as a composition operator that goes left to right. Pick whichever you prefer – left-to-right might feel more natural because it’s similar to object method calls.
Composition can be very useful in building up new more complex functions out of smaller ones. Recall earlier when we were implementing mapEveryNth, we had to write a small function:
// add 1 to the index to check if
// this entry is the nth
isNth = { ($0 + 1) % n }
Assuming we had a function that incremented a number, we could have used composition to build that function:
func successor<I: _Incrementable>(i: I) -> I {
return i.successor()
}
let isNth = isMultipleOf(n) • successor
And so, for one final go at writing checksum, assuming all the helper functions above are readily available:
let extractDigits: String->[Int] = { mapSome($0, toInt) }
let doubleAndCombine = { i in
i < 5
? i*2
: i*2-9
}
let doubleEveryOther: [Int]->[Int] = { mapEveryNth($0, 2, doubleAndCombine) }
let checksum = isMultipleOf(10) • sum • doubleEveryOther • reverse • extractDigits
let ccnum = "4012 8888 8888 1881"
println( checksum(ccnum) ? "👍" : "👎" )
The actual declaration is just a let. The checksum function is composed purely from other functions, some generic, some specific.6
Is this better then our original versions? I think so.7 The definition of checksum looks, to me, to be very readable. Reading from right to left, you extract the digits from the input, reverse them, double every other digit, sum them, and check if that’s a multiple of 10. The individual custom functions can be tested separately to check they work correctly – this approach is especially nice when combined with Swift playgrounds.
You could argue this is all cheating. You could take the same “breaking the problem down” steps with the imperative algorithm I started this blog with. And that’s true – but then I did title this post “a straw man”. And ultimately, you’d really still be circling the functional solution, getting closer to it. That’s what’s nice about Swift’s hybrid approach – it allows you to shift from one style to the other according to your preference.
It also assumes you have a library of re-useable functions just lying around that do stuff like this. But a lot of these kind of libraries already exist. They start with all the functions available in the Swift standard library (about which you can read more on this blog), but you might want to check out Swiftz, LlamaKit, or some of Rob Rix’s micro framworks.
Or you could start your own personal library of reuseable functions as you go along. Mine, with all the functions from this blog, is called SwooshKit and you can find it here.
Airspeed Velocity 