Building Data Structures with closures

dsClosures.js

//Building Data Structures with closures

//What's the plan? Build some data structures without using assignment,
//then building some functions which operate on those data structures.

//Why? Exploring what we can do with the closure property, and to get a better
//understanding of how it works.

/*
cons, first, rest, list, head, tail, length, each,
print(using each), concat, map, reduce, sum(with reduce), product(with reduce)
 */


/*
  Terms:
    Bound vs Free Variable
    Pure vs Impure Function
    Closure
    Lexical Scope
 */

/*
cons -> f(x, y) -> f
  first -> f(cons) -> x
  rest -> f(cons) -> y
 */

function cons(x,y){
  return function(n){
    if (n === 0){ return x; }
    if (n === 1){ return y; }
    throw "Invalid"
  }
}

function first(c){
  return c(0);
}

function rest(c){
  return c(1);
}

/*
list -> f(n...) -> list
  head ->f(list) -> first thing in the list
  tail ->f(list) -> last thing in the list
 */

function nullo(){};

function list(){
  if (arguments.length === 1) { return cons(arguments[0], nullo); }
  return cons(arguments[0],
    list.apply(null, Array.prototype.slice.call(arguments, 1)));
}

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

function tail(list){
  return rest(list) === nullo? first(list) : tail(rest(list));
}

function length(list){
  return rest(list) === nullo? 1 :
    1 + length(rest(list));
}

function each(fn, list){
  fn(first(list));
  if (length(list) > 1)
    each(fn, rest(list));
}

function print(list){
  each(function(value){
    console.log(value);
  }, list);
}

function concat(list1, list2){
  if (length(list1) === 1) { return cons(first(list1), list2); }
  return cons(first(list1), concat(rest(list1), list2));
}

function map(fn, List){
  if (length(List) == 1){ return list(fn(first(List))); }
  return concat(list(fn(first(List))), map(fn, rest(List)));
}


function square(x) { return x * x; }


function reduce(combiner, fn, list){
  if (length(list) === 1) { return fn(first(list)); }
  return combiner(fn(first(list)), reduce(combiner, fn, rest(list)));
}


function summation(list){
  return reduce(sum, identity, list);
}


function sum(){
  return Array.prototype.slice.call(arguments,0)
    .reduce(function(sum, value){
      return sum + value;
    })
}

function identity(x) { return x; }

function range(start, end){
  if (start === end) { return list(start); }
  return cons(start, range(start+1, end));
}

/*
list(1,2,3)
cons(1, cons(2, cons(3, nullo)));

 */