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

Folds-Recursion Patterns in JS

Folds-Recursion Patterns in JS

This is an article about functional Recursion on the Array data structure.

This article was inspired by the article “Functional JS with ES6 — Recursive Patterns” but here we are going to take a road that is more profound and has to do that the algebraic definition of a List is List = 1+a*List

This says that the list is either the empty list [] or a concatenation of an element a and a smaller list .

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.

After defining pattern matching we can immediately define some concepts like for example the first element of the array :

Or similarly the tail of the array:


Functional Folds

Now I am going to define a method that is simple yet can be confusing. The following method define a catamorphism on the Array or more commonly called Fold ( i will keep the name cata but you can name it fold) .

[the parameter evaluation is often called an algebra.]

The critical point here is the:

1
concat: (head, tail) => evaluation.concat(head, tail.cata(evaluation))

We recursively pass the evaluation to evaluate the tail of the array **tail.cata(evaluation)**

*Note : If it helps you you can rename the method to evaluation this might make more sense for object oriented programmers:

Catamorhism/Fold is the most general way to decompose an Array to some other Type. the evaluation parameter has (almost) the same methods with the pattern that we used in pattern matching:

1
2
3
4
evaluation= { 
  empty: () => {...},
  concat: (headEval, tailEval) => {...}
}

Let’s use the cata function to define the Length of the array.

Length

Why did this work? Unfortunately, JavaScript does not have types so you cannot see what the Types are. But in this length-algebra you might think everything is an integer:

1
2
3
4
{                               
  empty: () => 0,                  
 concat: (v, r) => 1 + r          
}

The empty array we want to be 0 , and if its not empty add the length of the head which is 1 and the length of the rest **r**

We can of course do that without the cata() simply with pattern matching and recursion:

In a way we factor out the recursion inside the **cata()** method. And we can write definitions without recursion

Let’s see some more examples. For reversing the array

Reverse

Here we used an algebra that exchanges the part of the first value (v) and the rest of the array ( …r).

Filter

The algebra we use here checks the head of the list. if the value doesn’t satisfy the filter we just keep the rest of the array.

Map

The map is pretty default:

Reduce

Finally Reduce is the what most people use as the closest to the catamorhism definition. (This is the same with cata by making some renaming and rearrangements which I won’t do here).

Conclusion : Catamorphism is the most general way of converting an Array into some other Type. Because of the underling idea can be confusing as developers we use the reduce array method that is equivalent. We can use catamorhism on other Data structures like Trees.


If you want to search more you can define the cata on the Tree structure in this article “How to reverse a tree in JavaScript the Functional way

comments powered by Disqus