dimitris papadimitriou
dimitris papadimitriou More than 12 years’ experience as full stack developer and Software Architect . Functional javascript with categories.

Zip Arrays-Recursion Patterns in JS

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:

  1. Where in the pattern.concat(head, tail) method the headis the first value of the Array and tailthe rest of the array if the array is not empty.
  2. 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

  1. If the first list is empty just return the second list :empty: () => a2

  2. 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 https://leanpub.com/functional-programming-in-js-with-categories

comments powered by Disqus