Fold Right in Javascript (with all thinkable examples)

Gist: Fold right (aka reduce right) is the basic list recursion operator. Way more intelligent than its cousin fold left. It has a non-intuitive way to handle its own parameters (trying to follow the nested calls with paper and pen or with the stepper of DrRacket is kind of funny), but the operation you entrust it with (represented by the function f) gets performed outside the recursion call, which is the general thing you’d expect a recursive function to do. This makes fold right extremely versatile. Unlike fold left (which has signed a suicidal pact to reach the end of the list or blow the stack in the effort) during the trip with fold right you may talk to the driver and tell it for example to fetch the result and get out of the loop.

Why folds matter

An introduction before we plunge in the real stuff. If you are (like I am) even moderately proficient with recursive functions and know how to pass values to a continuation, why would you need to bend, tweak and express your algo through an exotic thing like fold right?

The reason is told in crisp clear terms in [2], page 93.

Folds have regular, predictable behavior. This means that a reader with little experience will have an easier time understanding a use of a fold than code that uses explicit recursion. A fold isn’t going to produce any surprises, but the behavior of a function that recurses explicitly isn’t immediately obvious. Explicit recursion requires us to read closely to understand exactly what’s going on.

In other words, once more it’s all about code maintainability. That “reader with little experience” is me, coming back to my own stuff six months later or delving into the code of a long gone colleague to add a functionality.

Fold it right!

The definition of fold right (shortly fold, to express the fact that fold right is the fold) is (*):

fold (f) (v) ([]) = v

fold (f) (v) (x:xs) = f (x) (fold (f) (v) (xs))

Where:

  • x:xs is a binary tree that represents a list containing elements x of type α, that’s to say that the type of x:xs is [α]
  • f is a binary function of type α -> β -> β (**)
  • v (type β) is the value that gets substituted to the last empty leaf of the list-tree
  • fold f v altogether is a function of type [α] -> β (***)

(*) I am putting brackets JavaScript-style; in Haskell they wouldn’t be necessary.

(**) I am embracing the Haskell habit of providing multiple parameters one at a time, by creating a chain of partially applied functions.

(***) you may see this in the fact that after fold f v we have either [], x:xs or xs, which are all of type [α].

When you feed an α to an f (e.g. f(x) in the second equation) the next operand gotta be a β and (look at that!) fold f v xs is indeed a β.

The hunting of the f-nark

As source [1] explains clearly, expressing an operation g on a list (e.g. the sum of all its elements) as a fold right means finding a function f such that (please follow carefully the chain of equalities):

g (x:xs) = f x (g xs) = f x (fold f v xs)

with the additional constraint that:

g ([]) = v

In any real-world, non-trivial case this f is not a ready-made operator, but rather a custom-built anonymous lambda. Because my goal is to get used to generic problems and solutions, in the following Haskell examples I will use for g real names like sum, filter, etc., but will write always anonymous lambdas for f, also in the cases where an operator is available.

In some cases I will write explicitly the lambda the first time it occurs and refer later to it as ‘f’.

Fold right in JavaScript – geiesfolds on GitHub

Having abandoned my initial goal of learning functional programming in Java (one of the most foolish undertakings of my whole professional life), since about one year I am thoroughly enjoying the study and applications of FP in JavaScript. I have made quite a few repositories on GitHub presenting various aspects of the matter. The repository handling folds is currently in beta status and its name is geiesfolds (which reads j-s-folds in Italian). It contains both fold right and left. All its implementations are covered by tests, using YUI.

Fold right in JavaScript reads like this:

function fold(f){
  return function(v){
    return function(xs){
      if (isEmpty(xs)){
        return v;
      } else {
        return f(head(xs))(fold(f)(v)(tail(xs))); // fx fold f v xs
      }
    };
  };
};

JS implementations of all mainstream list functions (like head/car, tail/cdr, isEmpty) are presented in another post of mine and are to be found in geieslists.

CAVEAT EMPTOR: as I anticipated two paragraphs before, this implementation is based upon partially applied functions; you see that e.g. the arguments for f are given one at a time. That’s very elegant to see and I believe is the best way for understanding the inner working of the whole mechanism, but alas: appending partially applied functions is implemented very inefficiently in JavaScript, because it creates a bunch of short-lived closures (see [3]). When I need a sound implementation for folds (and for a lot of other functions) my choice is always underscore.js. But there you have to respect the signatures and provide tuples of parameters exactly the way the API requires.

Examples of fold right

This page is mainly a JavaScript implementation of the examples given in [1], along with personal observations, a few original discoveries and some remaining doubts. To be frank, [1] is a great academic paper to study from, if you want to get to a good level of understanding; but for a well-willing practitioner like I am, it sounds at some points so smug! The most blazingly daring demonstrations (like fold left expressed through fold right) are liquidated in one or two lines with dismissals like “using a simple substitution…”, “this is a plain application of…”, and so on. This page of mine is certainly less rigorous, but probably easier to follow.

JS implementations are all available on GitHub.

Even though I am always greatly reluctant to fire up the clumsy Haskell REPL, I must admit that the syntax which allows me to better follow the various chained function applications is indeed Haskell. When I am trying to solve a case with paper and pencil, the syntax I find myself jotting down is kind of that one, with a few Scala/JavaScript keywords here and there.

Therefore I will present first an Haskell-ish solution of the various cases, followed by a rigorous and runnable one in JavaScript.

sum, product, length, and, or (the basic stuff)

These are mentioned in many other pages. Here are the Haskell and JS implementations.

  • sum

The Haskell definition is:

sum x:xs = (\x y -> x+y) x (sum xs)

Let’s see how this works in detail: function f is an anonymous lambda (\ is the Haskell shortcut for lambda); it receives first an x (the current head of the list) and then an y, that’s to say the remainder of the sum (which we find at the right corner of the previous equation, written as sum xs). After that, f returns their sum.

At each passage the remainder of the sum is actually … fold f v xs.

Therefore we write that:

sum xs = fold (\x y -> x+y) 0 xs

v is 0, because the sum of an empty list is 0 and (from the definition of fold)

sum [] = 0 = fold f v [] = v

In JS the function f is the following (I have renamed it adder for the sake of clarity):

function adder(x){
  return function(y){
    return x + y;
  }
};
var sumWithFold = fold(adder)(0);

Please note that 0 is not the starting value (as is the case when sum is defined using fold left), but the last value, which gets bound when the empty list is met.

IMPORTANT ADVICE: if your goal is like me to become self-sufficient in the analysis of real-world cases and in expressing them as folds by creating custom-made functions f, my strong recommendation is for you to download paper [1], and make sure that you fully understand the technique presented in paragraph 3.3.

  • product

The Haskell definition is:


product x:xs = (\x y -> x*y) x product xs 
             = (\x y -> x*y) x (fold (\x y -> x*y) 1 xs)

and the JS implementation is:

function multiplier(x){
  return function(y){
    return x * y;
  }
};
var productWithFold = fold(multiplier)(1);
  • length

Haskell: in this case we better call the second variable n, which is the length of the remainder of the list. We don’t care what the value of x is, we just increment n at each step.


length x:xs = (\x n -> n+1) x length xs 
            = (\x n -> n+1) x (fold (\x n -> n+1) 0 xs)

JS:

function lenghter(x){
  return function(n){
    return n + 1;
  };
};
var lengthWithFold = fold(lenghter)(0);
  • and

The Haskell-ish definition is:

and x:xs = (\x y -> x&&y) x (fold (\x y -> x&&y) True xs)

and the JS implementation is:

function and(x){
  return function(y){
    return x && y;
  }
};
var andWithFold = fold(and)(true);
  • or

Haskell-ish:

or x:xs = (\x y -> x||y) x (fold (\x y -> x||y) False xs)

JS:

function or(x){
  return function(y){
    return x || y;
  }
};
var orWithFold = fold(or)(false);

reverse

In the case of reverse, function f must take the head of the list and put it at the tail of the other elements (reversed).


reverse x:xs = (\x y -> y::[x]) x reverse xs 
             = (\x y -> y::[x]) x (fold (\x y -> y::[x]) [] xs)

In order to define reverse, we need therefore a JS concatter function. Geieslists features a binary implementation of concat, but here we want only partially applied unary function, so we create a curried concat.

function curriedConcat(aList){
  return function(bList){
    if (isEmpty(aList)) return bList;
    else if (isEmpty(bList)) return aList;
    else if (isEmpty(tail(aList))) return cons(head(aList),bList);
    else return cons(head(aList),curriedConcat(tail(aList))(bList));
  };
};

Having that, the concatter that will be passed to fold right is ready in a few keystrokes:

function concatter(x){
  return function(y){
    return curriedConcat(y)(cons(x,EMPTY));
  };
};
var reverseWithFold = fold(concatter)(EMPTY);

map (f comes of age)

In the case of map, things get really interesting. map produces always a list, therefore we will say that in this case result type β = [γ]. The operation that we want to perform has type [α] -> [γ]; the new thing is that map cannot do the job alone: it must carry a transformer t of type α -> γ and invoke it, in order to replace every x with t(x). Therefore the function we are actually folding is not map, but map t

map t x:xs = (\x y -> t(x):y) x map t xs 
           = (\x y -> t(x):y) x (fold f [] xs)

The JS counterpart won’t care about α, β and γ and reads as follows. The transformer will have to be nested carefully inside the call to fold.


function mapper(t){
  return function(x){ // \x,y -> t(x):y
    return function(y){
      return cons(t(x),y);
    };
  };
};
var mapWithFold = function(t){
  return fold(mapper(t))(EMPTY);
};

filter

Alike map, in this case we fold a function (filter) and a predicate p. At each step, function f uses the predicate to check the head of the list. if p(x) is true, x gets at the head of the remainder of the filtering, otherwise it gets discarded

filter p x:xs = (\x y -> if (px) x:y else y) x filter p xs 
              = (\x y -> if (px) x:y else y) x (fold f [] xs)

where f is a shortcut for the whole preceding lambda.

The JS implementation you find in geiesfolds is:

function filterer(p){
  return function(x){ // \x,y -> if px then y else x:y
    return function(y){
      return (p(x)) ? y : cons(x,y);
    };
  };
};

var filterWithFold = function(p){
  return fold(filterer(p))(EMPTY);
};

sumlength (handling tuples to unleash the power of fold)

Using tuples allows to carry out more list operations in parallel. Suppose we have a function defined like this:

sumlength xs = (sum xs, length xs)

The f function is a mix of both primitives sum and length, bound together inside a pair.

sumlength x:xs = (\x (s,l) -> (s+x,l+1)) x (sumlength xs) 
               = (\x (s,l) -> (s+x,l+1)) x (fold (\x (s,l) -> (s+x,l+1)) (0,0) xs) 

Please remind that f‘s type is α -> β -> β; in other words f receives first an input type, then a result type and eventually produces a result type. In our case β is a pair (sum, length), therefore lambda’s two arguments must be \x (s,l).

The JS implementation uses a curried definition of pair and is the following:

function sumlengther(x){
  return function(y){
    return pair(x+_1(y))(1+_2(y));
  };
};
var sumLengthWithFold = fold(sumlengther)(pair(0)(0));

Where the tuple management functions are defined in this post.

dropWhile (a good technique for the FP toolbox!)

dropWhile is the function that chops a list from the front, as long as its elements satisfy a predicate, for example:

dropWhile (\x -> x<3) [1,2,3,2,1] = [3,2,1]

Let’s try to implement dropWhile naïvely, just pretending it’s some case similar to the previous ones. At a generic step we check the head of the list and we either discard it and keep processing the remainder or we return the whole list, because x happens to be the first element that doesn’t satisfy p:

dW p x:xs = if p(x) dW p xs else x:xs

If we want to play by the usual rules, the right side of the previous equation should be espressed as:

dW p x:xs = f x (fold f v xs)

But we can see that this is impossible. Function f may receive first x and then (dW p xs), but there’s no way to pass the bare xs to f so that (in case of p(x) = false) the return value may be x:xs. In proper words, xs is nowhere to be bound.

The solution for this case is a generic tool for the FP toolbox. Carry with you any unbound parameter paired together with the main function. So, let’s invent function dW':

dW' p xs = (dW p xs, xs)

Nothing to understand here. It’s just a definition: dW' takes a predicate and a list, and returns a pair which contains the application of the original dW on that list and the list itself.

Using it inside a fold right reasoning we write:

dW' p x:xs = f x (dW' p xs) 
           = f x (dW p xs, xs) 
           = [definition of dW'] 
           = (if (p x) dW p xs else x:xs, x:xs)

Now you gotta follow carefully the definition of f:

f = \x (a,b) -> (if (p x) a else x:b, x:b)

First we give f the usual head of the list, then comes dW' p xs (that’s a pair!), which we bind to the paired variables a and b. a is dW p xs and gets returned when p(x) succeeds; in the other case we need to use xs, which is bound to b and we return x:b. We must return a pair so f bundles the if-then-else with x:xs, alias x:b.

This f is a valid fold operand in the case of dW' – the final value is (dW p [], []) = ([],[]):

dW' p xs = fold (\x (a,b) -> (if (p x) a else x:b, b) ([],[]) xs

But we want dW; so we must tweak a bit the result, borrowing some Scala syntax and extracting the first element of the resulting pair:

dW p xs = (fold (\x (a,b) -> (if (p x) a else x:b, b) ([],[]) xs)._1

Of course, in JS all this is a bit more convoluted:

function dwApexer(p){
  return function(x){ // \x,(a,b) -> (if px then a else x:b,x:b)
    return function(ab){
      var a=first(ab),b=second(ab);
      return pair(p(x) ? a : cons(x,b))(cons(x,b));
    }
  }
}
var dropWhileApexWithFold = function(p){
  return fold(dwApexer(p))(pair(EMPTY)(EMPTY));
}
var dropWhileWithFold = function(p){
  return first(fold(dwApexer(p))(pair(EMPTY)(EMPTY)));
}

sum from the left (another interesting technique)

A run of a fold right digs as fast as possible to the end of the list and then backtracks. This leads to the fact that while you’re tinkering with an f function imagining to be somewhere halfway the list, it is usually easier to refer to the “future” (that’s the y) than to the “past”. With “past” I mean the items at the beginning of the original list, which you’re supposed to have visited before, but that actually will be taken care of later in the execution.

This example shows how to emulate a function typically working a list “from the left” using fold right. The execution is a fold right, but the flow feels otherwise.

The standard recursive implementation of the sum of a list uses internally a binary helper function suml’ that carries an accumulator in the recursion:

suml' x:xs acc = suml' xs (x+acc)
suml' [] acc = acc

You see how suml’ penetrates the list adding each new x to the accumulator. When the list is empty, suml’ returns the accumulator with the whole sum inside.

Having this helper, we can define sum as

sum xs = suml' xs 0

The remarkable thing is that they tell me that suml' can actually be expressed as a fold right… It is actually a bit disappointing that [1] falls short of telling exactly what makes an operation right-foldable rather than left-foldable, but the paper gives an indication that this truly relevant piece of knowledge is given inside another book ([2]), which I have ordered at Amazon. We’ll see…

Since suml' is right-foldable, we may write (I have put a few non-mandatory brackets to help comprehension):

suml' x:xs = f x (suml' xs)

We know that suml' (whatever is the way it is expressed) is in dire need of an accumulator, so we provide one:

suml' x:xs acc = f x (suml' xs) acc
               = [definition of suml']
               = suml' xs (acc+x)

From here it is possible to derive f. In this case f has three arguments: x, (suml' xs) and acc

f = \x y a -> y(a+x)

In this function a represents what I called “the past”. In the middle of this fold right evaluation, a represents the sum of the list elements we have sliced at the previous levels of the recursion call stack. In the reality we are still hurrying to the bottom of the list (mighty y requests us to evaluate him first of all), but we know a is a placeholder for items that occur earlier in the original list. This can be a fertile idea, like the one presented in the case of dropWhile.

Let’s complete the sum from the left case: we need a bit of care in order to define v, the value that gets substituted at the EMPTY bottom of the list. We remind from the top of this page that the right-foldable operation g (in this case suml') must satisfy the constraint:

g [] = v

This means:

suml' [] = v

Let’s add the accumulator here, too:

suml' [] acc = v acc 
             = [definition of suml']
             = acc

v is here a function; that’s the function such that (I am putting here as well a few non-mandatory but helpful brackets):

v(acc) = acc

That’s the fixed point f(x)=x, also known as the IDENTITY (id in Haskell).

Therefore we express the sum from the left of a list as (please note the starting accumulator 0 at the far end of the equation):

sum xs = fold (\x y a -> y(x+a)) IDENTITY xs 0

And here it goes in JavaScript…

function sumLeftApex(x){ // head
  return function(y){ // sumLeftApex(xs)
    return function(z){ // acc
      return y(x+z); // sumLeftApex(xs)(x+acc)
    };
  };
};

function sumLeftWithFold(aList){
  return fold(sumLeftApex)(IDENTITY)(aList)(0);
};

get (grab that element and stop recursing!!)

This is actually an original contribution of mine, as it not enclosed in [1]. It shows that fold right is not forced to reach the end of a list, but can stop halfway. In this case we have a parameter n that indicates that we have to return the n’th element of a list. The idea is that we proceed through the list and at each step we decrement n. Once n is 0, the head of the list is what we were looking for. In pseudo-Haskell we write:

get x:xs n = get xs n-1
get x:xs 0 = x

The right-foldable version goes:

get x:xs n = f x get xs (n-1)
           = [definition of get]
           = if (n=0) x else get xs (n-1)

From the last step we deduce f the usual way:

f = \x y n -> if (n===0) x else y(n-1)

And here goes the JavaScript. We decide that if we ever get to the end of the list, an error be thrown: n was clearly larger than the size of the list!

function getterRight(x){ // head
  return function(y){ // getterRight(xs)
    return function(n){ // current index
      return (n===0)?x:y(n-1);
    };
  };
};

function getWithFold(xs){
  return function(index){
    return fold(getterRight)(function(n){throw 'OUT!'})(xs)(index);
  };
};

It is interesting the comparison with get n done using fold left. In the case of fold left we start with an empty accumulator; once we are in the n-th position (technically we may still decrement n and watch for value 0) we load the current list head item in the accumulator. Then fold left keeps going through the list. At the end the accumulator is returned and so we receive our coveted n-th element. But most of the times this is slower than the fold right implementation. For large lists this must be measurable.

That’s why the ultimate goal is to test the speed of the two implementations in jsperf. Watch here for news.

fold left (done right)

Having done sum from the left, we know that fold right can emulate also algorithms that process lists “from the head”.

No surprise that this means that also fold left can be emulated by fold right. But not the other way around: fold right is universal, fold left is not.

Paper [1] liquidates fold left as a “simple generalisation” of the technique used in the case of sum from the left. I can kind of follow that, but honestly every time I try to derive it rigorously the way I am able to derive suml’, I get stuck.

There is a whole companion page dedicated to fold left as implemented in geiesfolds. I anticipate a few things here. Unlike [1], I have decided to express fold left using fresh variable names s & a, so to avoid clashes and miscomprehensions with f & v:

foldl s a x:xs = foldl s (sax) xs // think Trane
foldl s a [] = a

So, here goes the expression of fold left using fold right (and renaming variables to keep them kind of apart):

foldl s a xs = fold (\x ss aa -> ss(s aa x)) IDENTITY xs a

The JS implementation is this baroque stuff, but it works (I am providing a test):

function foldLefter(s){ // the fold left operator
  return function(x){ // head
    return function(ss){ // the future of fold left in the hands of fold right
      return function(aa){ // placeholder for the accumulator
        return ss(s(aa)(x));
      };
    };
  };
};

var foldLeftByFoldRight = function(s){
  return function(a){
    return function(xs){
      return fold(foldLefter(s))(IDENTITY)(xs)(a);
    };
  };
};

// for the test we need an s
function oneMoreAdder(a){
  return function(x){
    return a+x;
  };
};

// YUI test does the rest...
Assert.areEqual(6, foldLeftByFoldRight(oneMoreAdder)(0)(ArrayToList([1,2,3])),'fold right: fold left is not right!');

A real production-level fold right

Celebrating the first real, original, professional usage of a fold right in my life and giving evidence that FP may be really useable in a normal programmer’s working day.

WIP

[1] A tutorial on the universality and expressiveness of fold, by Graham Hutton.
[2] Introduction to Functional Programming in Haskell 2nd ed., by R. Bird
[3] see http://spencertipping.com/js-instabench/ – please compare:
– allocating small structures -> 1M (int, int) pairs as array literals
– allocating small structures -> 1M (int, int) pairs as binary CPS closures
– accessing small structures -> 1M (int, int) pairs as array literals
– accessing small structures -> 1M (int, int) pairs as binary CPS closures

Advertisements

One thought on “Fold Right in Javascript (with all thinkable examples)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s