functional-javascript-lists-1

build-list-1.js

var list = new Cons(1, new Cons(3, new Cons(42, new Cons(28, Nil))));

build-list-2.js

var cons = function(head, tail) {
  return new Cons(head, tail);
};

var list = cons(1, cons(3, cons(42, cons(28, Nil))));

cons-1.js

var Cons = function(head, tail) {
  this.head = head;
  this.tail = tail;
};

Cons.prototype.isEmpty = false;

fib-calls.js

fib(4)
fib(3) + fib(2)
fib(2) + fib(1) + fib(1) + fib(0)
fib(1) + fib(0) + 1 + 1 + 0
1 + 0 + 1 + 1 + 0
3

fib-imperative.js

function fib(n) {
  if (n < 2) {
    return n;
  }

  var n0 = 0;
  var n1 = 1;
  var ans = 0;

  for (var i = 2; i <= n; i++) {
    ans = n0 + n1;
    n0 = n1;
    n1 = ans;
  }

  return ans;
}

fib.js

function fib(n) {
  if (n < 2) {
    return n;
  }
  
  return fib(n - 1) + fib(n - 2);
}

list-calls.js

var myList = list(1, 3, 5);
//=> cons(1, cons(3, cons(5, Nil)));

var myOtherList = myList.map(n => n * 3);
//=> cons(3, cons(9, cons(15, Nil)));

var nine = myList.reduce((x, y) => x + y);
//=> 9

var listOfLists = list(list(1), list(2), list(3));
//=> cons(cons(1, Nil), cons(cons(2, Nil), cons(cons(3, Nil), Nil)));

var flattened = listOfLists.map(innerList => innerList.head);
//=> cons(1, cons(2, cons(3, Nil)));

list-constructor.js

var list = function () {
  if (arguments.length === 0) {
    return Nil;
  }

  var head = arguments[0];
  var tail = [].slice.call(arguments, 1);

  return cons(head, list.apply(null, tail));
};

map-call-1.js

var list = cons(1, cons(2, cons(3, Nil)));
var double = (n) => n * 2;

map(list, double); // yields:

cons(2, map(cons(2, cons(3, Nil)), double));
cons(2, cons(4, map(cons(3, Nil), double)));
cons(2, cons(4, cons(6, map(Nil, double))));
cons(2, cons(4, cons(6, Nil)));

map-call-2.js

var list = cons(1, cons(2, cons(3, Nil)));
var double = (n) => n * 2;

list.map(double); // cons(2, cons(4, cons(6, Nil)))

map-reduce.js

Cons.prototype.map = function(fn) {
  return this.reduce((item) => cons(), Nil);
};

map.js

var map = function(list, fn) {
  if (list.isEmpty) {
    return list;
  }

  return cons(fn(list.head), map(list.tail, fn));
};

nil-1.js

var Nil = {
  isEmpty: true,

  get head() {
    throw new Error('Accessing head on empty list.');
  },
  
  get tail() {
    throw new Error('Accessing tail on empty list.');
  }
};

oop-map-reduce.js

Cons.prototype.map = function (fn) {
  var consBuilder = function(memo, value) {
    return cons(fn(value), memo);
  };

  return this.reduceRight(consBuilder, Nil);
};

oop-map.js

Cons.prototype.map = function(fn) {
  return cons(fn(this.head), this.tail.map(fn));
};

Nil.map = function() {
  return this;
};

oop-reduce.js

Cons.prototype.reduce = function(fn, memo) {
  return this.tail.reduce(fn, fn(memo, this.head));
};

Nil.reduce = function(fn, memo) {
  return memo;
};

oop-reduceRight.js

Cons.prototype.reduceRight = function(fn, memo) {
  return fn(this.tail.reduceRight(fn, memo), this.head);
};

Nil.reduceRight = Nil.reduce;

reduce-call-1.js

var list = cons(1, cons(2, cons(3, Nil)));
var add = (x, y) => x + y;

reduce(list, add, 0); //=> 6

reduce.js

var reduce = function(list, fn, memo) {
  if (list.isEmpty) {
    return memo;
  }

  return reduce(list.tail, fn, fn(memo, list.head));
};