In the previous article, about implementing the Luhn algorithm using function composition in Swift, I had a footnote to the part about using mapEveryNth to double every other digit:

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.

This post is about doing just that. I’ll define some more generic helper functions, and then use them to build a variant of our checksum function.

First up: cycling through a sequence multiple times. Suppose you have a sequence, and you want to repeat that sequence over and over. For example, passing in 1...3 would result in 1,2,3,1,2,3,1,...etc.

You could do this by returning a SequenceOf object that takes a sequence, and serves up values from its generator, but intercepts when that generator returns nil and instead just resets it to a fresh one:

func cycle
  <S: SequenceType>(source: S) 
  -> SequenceOf<S.Generator.Element> {
    return SequenceOf { _->GeneratorOf<S.Generator.Element> in
        var g = source.generate()
        return GeneratorOf {
            if let x = g.next() {
                return x
            }
            else {
                g = source.generate()
                if let y = g.next() {
                    return y
                }
                else {
                    // maybe assert here, if you want that behaviour
                    // when passing an empty sequence into cycle
                    return nil
                }
            }
        }
    }
}

// seq is a sequence that repeats 1,2,3,1,2,3,1,2...
let seq = cycle(1...3)

This code does something that might be considered iffy – it re-uses a sequence for multiple passes. Per the Swift docs, sequences are not guaranteed to be multi-pass. However, most sequences you encounter from day-to-day are fine with multiple passes. Collection sequences are, for example. But some non-collection sequences like StrideThrough ought to be too. My (possibly misguided) take on this: it seems OK to take multiple passes over a sequence, so long as you make it clear to the caller that this will happen. The caller needs to know if their sequence allows this, and if they pass a sequence that doesn’t support it, the results would be undefined.¹

OK, next, suppose you have two sequences. Maybe they’re both finite, maybe one is finite and one infinite (such as a sequence created by cycle above). You want to combine the elements at the same point in each one together, using a supplied function that takes two arguments. We’ll call that zipWith, and it’s very simple:

func zipWith
  <S1: SequenceType, S2: SequenceType, T>
  (s1: S1, s2: S2, combine: (S1.Generator.Element,S2.Generator.Element) -> T) 
  -> [T] {
    return map(Zip2(s1,s2),combine)
}

// returns an array of 1+1,2+2,3+3,4+4,5+5,
// so [2,4,6,8,10]
zipWith(1...5, 1...5, +)

How does this work? Zip2 is a SequenceType that takes two sequences, and serves up elements from the same position in each as a pair.² For example, if you passed it [1,2,3] and ["a","b","c"], Zip2 would be a sequence of (1,"a"), (2,"b"), (3,"c"). If one sequence is longer than the other, Zip2 stops as soon as it’s used up the shortest sequence.³

Then, that zipped sequence of 2-tuples is passed into map, along with the combiner function. Map does it’s thing, calling a transformation function on each element to produce a new combined value. Remember, Swift functions that take n arguments can instead take one n-tuple. That is, if you have a function f(a,b), and a pair p = (x,y), you can call f as f(p). So if Zip2 produces p = (1,1), then +(p) returns 2.

Finally, map spits out the array of combined pairs, and that’s returned.

So, we have a function that cycles over a given sequence forever, and a function that takes two sequences and combines their elements using a given function. How does this help double every other number in a sequence?

Well, suppose you had a sequence of two functions: one that did nothing, just returned its input unchanged, and one that doubled its input. If you cycled that sequence, you’d have an infinite sequence of functions that alternated between doing nothing and doubling.

How could zipWith be used to combine that cycling pair of functions, with a sequence of numbers, such that every other number was doubled? What would the combiner function need to be? It would have to take a value (the number), and a function (do-nothing or double), and apply the function to the number.

We’ve already written a function that does that, last time: pipe forward.

infix operator |> {
    associativity left
}

public func |> <T,U>(t: T, f: T->U) -> U {
    return f(t)
}

So, if we passed in pipe forward as the function to zipWith, it’d do exactly what we want:⁴

// a function that does nothing to its input
func id<T>(t: T) -> T {
    return t
}

// a function that doubles its input
func double<I: IntegerType>(i: I) -> I {
    return i * 2
}

// an array of those two functions, for Ints:
let funcs: [Int->Int] = [id, double]

// double every other number from one to ten
// returns [1,4,3,8,5,12,7,16,9,20]
zipWith(1...10, cycle(funcs), |> )

Finally, let’s implement the new checksum function. We’re going to re-use the •, mapSome, toInt, sum and isMultipleOf functions from the previous article, just redefining the digit-doubling part:

let doubleThenCombine = { i in
    i < 5
        ? i * 2
        : i * 2 - 9
}

let idOrDouble: [Int->Int] = [
    id,
    doubleThenCombine,
]

let doubleEveryOther: [Int]->[Int] = { zipWith($0, cycle(idOrDouble), |> ) }

let extractDigits: String->[Int] = { mapSome($0, toInt) }

let checksum = isMultipleOf(10) • sum • doubleEveryOther • reverse • extractDigits

let ccnum = "4012 8888 8888 1881"
println( checksum(ccnum) ? "👍" : "👎" )

This shows another benefit of the function composition approach. We completely changed the way the doubleEveryOther function was implemented, but because its interfaces in and out remained the same, everything else could stay untouched. Compare this with the iterative version, where looping and doubling and summing were all tangled up together.

So that’s nice, but you might ask if this version is any better than the version from the last post that used mapEveryNth. And it probably isn’t.

But what it does do is show the power of treating functions like any other object, storing them in a collection and iterating over them.

Suppose the Luhn algorithm actually required you to double the even-positioned numbers, but halve the odd ones. Using the mapIfIndex function, you’d need to take two passes (or write another function that took two transformations). With the zipWith technique, all you’d have to do is replace id with a function to halve its input.

You could take this even further. In this example, the array was built literally. But imagine a scenario where you needed more dynamic behaviour – where the array of functions you passed into zipWith were built at runtime, perhaps chosen via user interaction.

“Big whoop,” you say. “This is just like an array of delegates. I’ve been doing this for years.” And that’s totally fair. But functions can be both lighter-weight and more flexible. No need to create an interface, define methods, create an object that implements the interface, worry about which methods need real implementations and which just need stubbing out. The callee defines the function type, the caller writes a closure expression, maybe captures a few variables, and we’re done. For more on this, see Peter Norvig’s slides on how language features can make design patterns invisible or simpler.⁵

As ever, you can find all the general-purpose functions defined in this post in the SwooshKit framework.