functions-can-be-lists.js

// This technique is very old. It's based on Church pairs.
// http://en.wikipedia.org/wiki/Church_encoding#Church_pairs

cons = function (a, b) {
  return function (f) {
    return f(a, b);
  }
}

first = function (a, b) {
  return a;
}

second = function (a, b) {
  return b;
}

head = function (list) {
  return list(first);
}

tail = function (list) {
  return list(second);
}

list = cons(4, cons(3, cons(2,1)));
console.log(head(list));              // => 4
console.log(head(tail(list)));        // => 3
console.log(head(tail(tail(list))));  // => 2
console.log(tail(tail(tail(list))));  // => 1

//--------------------------------------------------------

// head and tail are compatible with other list-like
// functions as well.
//
// example: the infinite list of natural numbers.

console.log("infinite list: natural numbers");

nat = (function _nat (n) {
  return function (f) {
    return f(n, _nat(n+ 1));
  };
})(1);

console.log(head(nat));                         // => 1
console.log(head(tail(nat)));                   // => 2
console.log(head(tail(tail(nat))));             // => 3
console.log(head(tail(tail(tail(nat)))));       // => 4
console.log(head(tail(tail(tail(tail(nat)))))); // => 5
                                                // …

http://en.wikipedia.org/wiki/Church_encoding#Church_pairs

My brain hurts