Saturday, January 3, 2015

On Zipping

"With those legions
Which I have spoke of, whereunto your levy
Must be supplyant: the words of your commission
Will tie you to the numbers and the time
Of their despatch.
-- Shakespeare, Cymbeline
Act III, Scene VIII, Lines 12.2 - 16.1

Zipping is a very simple concept from higher order functions which does not get talked about much.

With a zip you have a number of collection which you wish to apply a function against each matching member in order to produce a single "zipped" collection.

In general:

GIVEN a function f

FOREACH x_i in X, y_i in Y, ...
  r_i = f(x_i, y_i, ..)

GIVING r_i in R

The function f is the "zipper", while X, Y, ... are the collections being zipped with R being the zipped result.

A simple example with 2 collections:

Let's use Add as the "zipper", [1, 2, 3] as the first collection, and [10, 20, 30] as the second collection.

We see that this gives us the resulting collection of [11, 22, 33].

What should happen if the first or second collection has a different number of elements?


We'll look at what C#, Clojure, and Haskell do in these cases.

We see that they each have a resulting collection as large as the smallest input collection and simply just ignore the rest of the input in the larger collection.  There you have it a very simple introduction to Zip.