Implementing zip

zip is a handy global function in the Swift standard library that will take two sequences and zip them together into a single sequence of pairs:

let xs = [1, 2, 3]
let ys = [4, 5, 6]
let zipped = Array(zip(xs, ys))
println(zipped) // [(1, 4), (2, 5), (3, 6)]

Here we are creating two arrays of ints and calling the zip function wrapped in the Array initializer which will get an array from the Zip2 struct. From the printed results, we can see that the corresponding elements from both arrays get paired together. Element 0 of the first array gets paired with element 0 of the second array, etc.

For kicks, let's try to implement our own version of zip using recursion. Here is the function declaration:

func myZip<A, B>(a: [A], b: [B]) -> [(A, B)]

Here we are declaring a function called myZip. The <A, B> means this is a function that deals with two different generic types A and B. Parameter a: is an array of generic type A. Parameter b: is an array of generic type B. Our return value is saying this function returns an array of tuple pairs of generic type A and B.

A common pattern when recursively iterating through arrays is to split the array into a head and tail and perform some recursive call on the tail. The head is the first element of the array and the tail is every element but the first element. As of this writing, there is no functionality in the Swift standard library for quickly performing this head:tail split. This snippet from objc.io implements this functionality as an extension on Array:

extension Array {
    var decompose : (head: T, tail: [T])? {
        return (count > 0) ? (self[0], Array(self[1..<count])) : nil
    }
}

This read-only computed property returns an optional tuple pair that is split into the head and tail of an array. Now we can start with our function:

func myZip<A, B>(a: [A], b: [B]) -> [(A, B)] {
    if let (x, xs) = a.decompose {
    }
}

Here we are performing an optional bind where x is our head of our array and xs is the tail of the array. Swift 1.2 adds the ability to unwrap multiple optionals at once, which we can use here with both parameters:

func myZip<A, B>(a: [A], b: [B]) -> [(A, B)] {
    if let (x, xs) = a.decompose, (y, ys) = b.decompose {
        // TODO: Implement.
    } else {
        return []
    }
}

We added base-case handling in the else clause by simply returning an empty array. Now that we have our head and tail for both arrays, we can finish:

func myZip<A, B>(a: [A], b: [B]) -> [(A, B)] {
    if let (x, xs) = a.decompose, (y, ys) = b.decompose {
        return [(x, y)] + myZip(xs, ys)
    } else {
        return []
    }
}

[(x, y)] means we are creating an array of one element with a tuple pair of our head of the array of A and our head of the array of B. + myZip(xs, ys) means that we are concatenating the previous element of the array with the result of recursively calling our function with our two tails xs and ys. At a conceptual level, think of this as creating the first element of the array with the two heads and then creating the rest of the array by zipping the two tails together!

let xs = [1, 2, 3]
let ys = [4, 5, 6]
let zipped = myZip(xs, ys)
println(zipped) // [(1, 4), (2, 5), (3, 6)]

Implementing zipWith

In Haskell, zipWith is a function similar to zip in that it takes two lists, except the "with" is for calling a given function between the corresponding elements of each list, and then returning the results as one list. In this Haskell example, we are taking two lists and adding the elements from each list together:

zipWith (+) [1, 2, 3] [4, 5, 6] -- prints [5,7,9]

As of Swift 1.2, there is no zipWith function in the standard library. A quick way to perform zipWith would simply be to combine map with zip!

let xs = [1, 2, 3]
let ys = [4, 5, 6]
let zippedWith = map(zip(xs, ys), +)
println(zippedWith) // [5, 7, 9]

But for kicks again, let's try to implement zipWith ourselves using an implementation similar to our myZip:

func myZipWith<A, B, C>(a: [A], b: [B], f: (a: A, b: B) -> C) -> [C]

Our function signature is similar to myZip with the addition of our f parameter and the different generic return values. Here f is defined as a closure that takes a generic type A, a generic type B, and returns a generic type C. We can repeat the head:tail split and base case handling like we did with myZip:

func myZipWith<A, B, C>(a: [A], b: [B], f: (a: A, b: B) -> C) -> [C] {
    if let (x, xs) = a.decompose, (y, ys) = b.decompose {
        // TODO: Implement.
    } else {
        return []
    }
}

Now we can finish the recursive implementation of the function body:

func myZipWith<A, B, C>(a: [A], b: [B], f: (a: A, b: B) -> C) -> [C] {
    if let (x, xs) = a.decompose, (y, ys) = b.decompose {
        return [f(a: x, b: y)] + myZipWith(xs, ys, f)
    } else {
        return []
    }
}

return [f(a: x, b:y)] means we are creating a single element array with the result of our passed in closure that gets called using the two heads x and y. Then with + myZipWith(xs, ys, f), we recursively call our myZipWith function using the two tails and the passed in closure.

Now we can do things like zip two arrays of numbers together using addition:

let xs = [1, 2, 3]
let ys = [4, 5, 6]
let zippedWith = myZipWith(xs, ys, +)
println(zippedWith) // [5, 7, 9]

Or, if we have an array of first names and an array of last names, we can zip them together with spaces between the two, giving us an array of full names. We can use trailing closure syntax since we made our closure the last parameter of the function:

let xs = ["Mary",  "John",  "Jane"]
let ys = ["White", "Smith", "Doe"]
let zippedWith = myZipWith(xs, ys) { $0 + " " + $1 }
println(zippedWith) // [Mary White, John Smith, Jane Doe]