A few weeks back, @SwiftLDN ran a handson, 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 functionalstyle 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 Int
s. 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 lefthand argument and f
as the righthand 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 – lefttoright 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*29 } 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 reuseable 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.

I realize
mapOptional
would be the equivalent name tomapMaybe
, but to memapSome
sounds better and seems more descriptive of what it actually does. ↩ 
The standard library goes the other route – the free
map
function only returns arrays. There is a trick you can do that allows you to default to arrays if not specified, but still be generic – but I’ll leave that for another time. ↩  An alternative could be a version of map that cycled over a sequence of different functions. You could then give it an array of two functions – one that did nothing, and another that did the conversion. ↩
 Or a LISP programmer. ↩
 I really like it. The main argument against it is that, while it’s easy to type option8 (because it looks like a *?) on my keyboard, that’s not the case for everyone e.g. Chinese or Arabic keyboards. I’d be interested in feedback from people affected by this (and not so interested in feedback from people who are ASCIIonly fans even on English keyboards 😛 ). ↩

You could even take it further, and compose a function that did the thumbs up/down conversion (using a further functional equivalent of the ternary operator – the VB programmer in me would call that
iif
), and then compose that with theprintln
function. But let’s not get silly. ↩  Except in one, possibly crucial, respect – it’s slower than the imperative version. I’ll cover why in a later post. ↩
So you replace a 17 line method with a 16 line method that requires 70 lines of helper functions (or third party libraries) and it is slower? Sign me up!
Snark aside, how is this better than just writing the iterative method? Doesn’t each of the helper functions introduce the possibility of bugs and the overhead of switching between all of your helper libraries?
You could also define mapOptional(…) as a method on String:
extension String {
func mapOptional(transform: (Character)>U?) > [U] {
var result = [U]()
for x in self {
if let y = transform(x) {
result.append(y)
}
}
return result
}
}
and mapIfIndex(…) as a method on Array:
extension Array {
func mapIfIndex(ifIndex: Int > Bool, transform: (T) > T) > [T] {
var result = [T]()
for (index,value) in enumerate(self) {
if ifIndex(index) {
result.append(transform(value))
}
else {
result.append(value)
}
}
return result
}
}
checksum could be written as
func checksum(ccnum: String) > Bool {
let n = ccnum.mapOptional { c in
String(c).toInt()
}
.reverse()
.mapIfIndex({idx in idx % 2 == 1}) { i in
i < 5
? i * 2
: i * 2 – 9
}
.reduce(0, +)
return n % 10 == 0
}
which seems very readable to me (very close to the algorithm in plain English), and using idioms of Swift.
I dont understand this kind of emphasis on functional programming. The big problems on software engineering are in the big picture. A GRASP 😉 on SOLID principles, for example, would be much more relevant to the science and art of software than this. Another fad I see everywhere is the usage of closures and blocks “for commodity”, when the reality is that developers can’t design software.
> Except in one, possibly crucial, respect – it’s slower than the imperative version. I’ll cover why in a later post.
Even then a better readable and understandable functional version of the algorithm is still useful as you can use it in a Quickcheck property uglyFastAlgorithm(x) == niceSlowAlgorithm(x) to validate the ugly slow version.
[…] the previous article, about implementing the Luhn algorithm using function composition in Swift, I had a footnote to the […]
[…] Note: this is an article for people new to functional programming style, and to closures. Unlike the rest of this blog, it is very much an explantion for beginners, so if you’re already familiar with these topics you might want to skip it.1 You may find these other articles interesting though – Implemeting an Accumulator in Swift, and A Strawman Argument for Trying More Functional Programming in Swift. […]
[…] a while back I wrote about using some functional programming techniques in Swift to solve the Luhn credit card checksum […]