3 April 2013

A foldr in javascript

Hello visitor,
If you know what a foldr is and if you know javascript you probably already know how to approach its functionality in javascript. If not perhaps you would like to read on.

What is foldr and why do I need it?
Wikipedia has a good explanation (http://en.wikipedia.org/wiki/Fold_(higher-order_function) but anyway I'll try a shorter one, for foldr:

  • arguments:
    1. a function (that takes a list element and a value (a possible partial result) of the same kind of the value it returns);
    2. a specification of the initial result for the empty list special case;
    3. a list.
  • return value:
    • some final result.
  • What it does:
    • It first applies the function to the last element in the list and the empty list result. It then reapplies the function with this result and the previous element, and so forth until it takes some current result and the first element of the list to return the final result.

Fold "folds" a list around an initial result using a function that takes an element and some previous folding result. It repeats this for each element. So, foldr does this starting at the end off the list, or the right side of it:
folr(f, emptyresult,[1,2,3,4]) Represents and constructs the expression f(1, f(2, f(3, f(4, emptyresult) ) ) )
which then may be evaluated. Blue gets evaluated first, then salmon, green and lastly purple.

  • Side note:
    • In this site ( http://foldr.com/ ) you can see an expression being constructed for

      folr(function(elem, partialres) { return elem + partialres;} , emptypr, [1,1,1,1,1...])

      It is an infinite list of ones and each click builds the expression further. Because it is an infinite list it never stops constructing the expression thus it will never start being evaluated. So I don't really get the = ∞ part, maybe it means exactly that.

So, the desire to be complied is to go through a list's elements progressively building a result with each element. Widely required wouldn't you say?

Why fold?

  • Maybe write less by just telling the function, the data, and any predefined special cases that would needlessly break it. In foldr, just tell the function, the list, and the empty list case.
  • Also knowing other ways of doing things is just cool too. :)

How to implement it?
From Haskell prelude definition, this next implementation uses recursion. And to keep it simpler because of the javascript baggage I'll let it be uncurried:


function foldr(fn, ult, xs) {     if (xs.length == 0){         return ult;     }else{         return fn(xs[0], foldr(fn, ult, xs.slice(1)));     } }

Because of the recursive definition probably some kind of heap growth will happen before it starts to shrink again while working on yielding the result. So a non recursive definition should improve speed and memory usage stability. There are some short examples of the following definition


function foldr(fn, ult, xs) {
    var result = ult;
    for (var i = xs.length - 1; i !== -1; i--) {
        result = fn(xs[i], result);
    }
    return result;
}
Surely enough it does perform much better as shown in this test http://jsperf.com/foldr-recursive-versus-not-so.
Also, you may want to do [1,2,3,4].foldr(Math.max, 0). If so you can go about polluting Array.prototype for extra points:


if (!Array.prototype.foldr){
    Array.prototype.foldr = function (fn, ult /* , xs */) {
        var result = ult;
        var ls = arguments[2] || this;
        console.log(ls);
        for (var i = ls.length - 1; i !== -1; i--) {
            result = fn(ls[i], result);
        }
        return result;
    }
}

If you don't need a special result that is different from the element's 'type' and want to use the last element as the initial result itself, there is
foldr1(f,[1,2,3,4]) that does
f(1, f(2, f(3, 4)))
also implying that the list cannot be empty. This limited foldr version, foldr1, is


function foldr1(fn, xs) {
    var result = xs[xs.length - 1];
    for (var i = xs.length - 2; i > -1; i--) {
        result = fn(xs[i], result);
    }
    return result;
}
Also could be Array.prototype.foldr1:

if (!Array.prototype.foldr1){
    Array.prototype.foldr1 = function (fn /* , xs */) {
        var ls = arguments[1] || this;
        var result = ls[ls.length - 1];
        for (var i = ls.length - 2; i > -1; i--) {
            result = fn(ls[i], result);
        }
        return result;
    }
}
...that makes you able to do for example [1,2,36,3,4].foldr1(Math.max)
and get 36 "yey me!..". That comes from Math.max(1, Math.max(2, Math.max(36, Math.max(3, 4)))). It should be noted that you can still use this foldr1 as a normal foldr if you push the initialresult into the end of the list, as in

//just a function that gets even numbers from the list into a result array
function geteven(e, pr) { 
    if(e % 2 === 0){
        pr.unshift(e);
    }
    return pr;
}
so doing [1,2,6,3,4,[]].foldr1(geteven) will yield [2,6,4].

  • Side note for Haskell:
    • In Haskell this exact reasoning for getting a foldr from foldr1 means we would have to create some type for the list like [Either et prt], so it could also hold the result; then we extract just the result from that type like:

      geteven (Left e) (Right pr) = if (even e) then Right (e:pr) else Right pr
      foldr1foldr f ir ls = (\(Right r) -> r) (foldr1 geteven ((map Left ls) ++ [Right ir]))
      -- the list ('initial state') for foldr1 will be [Left 1,Left 2,Left 6,Left 3,Left 4, Right []]
      result = foldr1foldr geteven [] [1,2,6,3,4] -- yields [2,6,4]

Some short javascript examples of the original full foldr (as a simply declared function):

JS Bin


Final note: we don't need to strictly have the same javascript type carried throughout the iterations. As long as the supplied function can handle its own return value as its second argument it will work, as an implicit custom type.


No comments:

Post a Comment