Functional JavaScript

A good old friend of mine challenged me with a small JavaScript assignment. Apparently he used it in his job interviews to see how good the candidates were. Here is a code snippet:

var add = function (a,b) { return a+b; };
var mul = function (a,b) { return a*b; };

var x = make(1)(2)(3)(4);
var y = x (5);

x (add) // 10
y (mul) // 120

The assignment is to implement make.

It didn't take me too long to produce a dirty version that worked:

var make = function() {
    var args = Array.prototype.slice.call(arguments, 0);
    if (args[0] instanceof Function) {
        var result = args[1];
        for (i = 2; i < args.length; i++) {
            result = args[0].apply(this, [result, args[i]]);
        }
        return result;
    } else {
        var curry_args = args;
        return function() {
            var args = Array.prototype.slice.call(arguments, 0);
            return make.apply(this, args.concat(curry_args));
        }
    }
}

I realize that it's a happy path with no error checks but it works. I figured I was relying on the commutative property of assignment and multiplication so I decided to reverse the collected arguments:

...
   for (i = args.length - 1; i > 1; i--) {
            result = args[0].apply(this, [result, args[i]]);
        }
...

The friend of mine didn't accept the solution and asked me to keep working on it to get rid of the loop. Iteration can easily be converted into a recursion and the result didn't take long to produce. My friend, however, didn't accept it either and asked me to get rid of arrays and get rid of working with the arguments (which isn't really an array but that's another story). The map function, he said, has arity of one so implement it as such, don't let the arguments collect behind the scenes. Well, I have to admit I was stuck. I knew I needed to somehow stack the closures and return functions of functions but the solution was out of my reach. I gave up. Here's his pure functional solution that he gladly shared with me after I admitted I couldn't get it:

var make = function (value) {
    return (function (f, g) {
        return f(g, f);
    })(function (cont, loop) {
        return function (v) {
            return (
                v instanceof Function ?
                    cont(v) :
                    loop(function (reducer) {
                        return reducer(v, cont(reducer));
                    }, loop));
        };
    }, function () {
        return value;
    });
};

Pretty, isn't it? Cryptic, sure, but pretty. He also broke it down into a more verbose but somewhat easier to navigate version:

var konst = function (v) {
    return function () {
        return v;
    };
};

var make2 = function (value) {
    var reducer;

    var reduce = function (v, cont) {
        return function () {
            return reducer(v, cont());
        };
    };

    var gen = function (cont, loop) {
        return function (v) {
            return v instanceof Function ? (reducer = v, cont()) : loop(reduce(v, cont), loop);
        };
    };

    return gen(konst(value), gen);
};

I would argue that for the benefit of the reader (and we all know how code is read much more often than it is written) my original version is "better", but his solution is just so much more awesome that I can't really support my argument :) The memoizing described in Douglas Crockford's "Javascript: The Good Parts" uses arrays, not exactly like I had it but close. I found another one on the web - Y Combinator in JavaScript and it is mind blowing. Do you see your school math or a recursion in:

x = x2 - 2

I see my school math. And to really get the functional solution to the make challenge I'd better had seen a recursion in it. My friend recommended the following reading to up my familiarity and awareness of those pure functional concepts:

• Structure and interpretation of computer programs. This one is famous. MIT has an online version of the book and the lectures recorded in 86 I believe.
• The Little Schemer
• Sketchy LISP

Let's see if working through the SICP book gets me closer to the functional nirvana. The book is coming any day now.