Zip Arrays-Recursion Patterns in JS

This is an article about functional way to Zip two Arrays .
for example if we have two arrays [1, 2, 3]
and [6, 7, 8, 7, 9, 10, 11]
we want to construct a function zip that would combine those two and give as a result the following
[1, 6, 2, 7, 3, 8, 7, 9, 10, 11]
the following section is again the definition of pattern matching on the Native array . [if you have already seen this in previous articles skip the section]
Pattern Matching
First we can write the following patternMatch method that allow us to separate the different parts of the list
The pattern object is something like this:
- Where in the
pattern.concat(head, tail)
method thehead
is the first value of the Array andtail
the rest of the array if the array is not empty. - If its empty the
pattern.empty()
is called.
Zip
Now we can use pattern matching in order to define a Zip
the core algorithms is the following :
1
2
3
4
5
6
7
8
9
10
Array.prototype.zip = function (a2) {
return this.matchWith({
empty: () => a2,
concat: (x, xs) => a2.matchWith({
empty: () => this,
concat: (y, ys) => [x, y].concat(xs.zip(ys))
})
});
}
by structural induction its easy to see why this works. Its like a nested pattern matching
-
If the first list is empty just return the second list :
empty: () => a2
-
if the first list is not empty then we pattern match on the second array
concat: (x, xs) => a2.matchWith({
you can try to continue the reasoning by yourself.
Excerpt from the Book Functional Programming in Javascript in LeanPub