Immutable Javascript Linked List

immutable-list.js

// immutable linked list
// Some functional patterns use head/tail a *lot*, and this particular collection
// has constant time for both head and tail. Concatenation is also constant time.

var nil = {};

// used to make the fields on the list truly immutable
function props(obj, fields){
  var args = {};
  for(var key in fields){
    args[key] = {
      value: fields[key],
      writable: false
    };
  }
  Object.defineProperties(obj, args);
}

props(nil, {
  isEmpty: true,
  head: undefined,
  tail: undefined,
  map: function() { return nil; },
  forEach: function() {},
  reduce: function(accu, func){ return accu; },
  reduceRight: function(func, accu){ return accu; },
  takeWhile: function(){ return nil; },
  dropWhile: function() { return nil; },
  toArray: function() { return []; },
  toString: function() { return 'list()'; },
  append: function(ls) { return ls; },
  prepend: function(ls) { return ls; },
  union: function(ls) { return ls; }
});

function Link(){}
var linkProto = {};

props(linkProto, {
  isEmpty: false,
  map: function(func) {
    return link(func(this.head), this.tail.map(func));
  },
  forEach: function(func){
    func(this.head);
    this.tail.forEach(func);
  },
  reduce: function(accu, func){
    var res = func(accu, this.head);
    return this.tail.reduce(res, func);
  },
  reduceRight: function(accu, func){
    return func(this.tail.reduceRight(accu, func));
  },
  // get a new list with the element added at the end.
  append:  function(val){
    var ls = link(val, nil);
    return this.reduceRight(ls, function(elem, accu){
      return link(elem, accu);
    });
  },
  // join the two lists together to create one big list.
  union: function(ls){
    return this.reduceRight(ls, function(accu, e){
      return link(e, accu);
    });
  },
  // create a new list with an element added at the begining.
  prepend: function(val){
    return link(val, this);
  },
  dropWhile: function(test){
    if(test(this.head)){
      return this.tail.dropWhile(test);
    } else {
      return this;
    }
  },
  takeWhile: function(test) {
    if(test(this.head)) {
      return link(this.head, this.tail.takeWhile(test));
    } else {
      return nil;
    }
  },
  toArray: function(){
    return this.reduce([], function(accu, elem){
      accu.push(elem);
      return accu;
    });
  },
  toString: function(){
    return 'list(' + this.toArray().join(', ') + ')'
  },
  toJson: function(){
    return JSON.parse(this.toArray());
  }

});

Link.prototype = linkProto;
Link.prototype.constructor = Link;

// link factory. A list is a series of links containing a value and a reference
// to another link or nil.
function link(head, tail){
  var ln = new Link();
  Object.defineProperties(ln, {
    head:{
      value: head,
      writable: false
    },
    tail:{
      value: tail,
      writable: false
    }
  });
  return ln;
}

// list factory
// list([1, 2, 3]) or list(1, 2, 3)
function list(arr){
  if(Array.isArray(arr)){
    return list.apply(undefined, arr);
  }
  var ls = nil;
  for(var i = arguments.length - 1; i >= 0; i--){
    ls = link(arguments[i], ls);
  }
  return ls;
}

module.exports = list;
module.exports.cons = link; // in some functional languages, its called cons.
module.exports.nil = nil;

immutable-list.test.js

var chai = require('chai');
var expect = chai.expect;
chai.should();

var list = require('../index');
var cons = list.cons;
var nil = list.nil;

describe('list creation', function(){

  it('should not throw exceptions...', function(){
    var err;
    try { list(1, 2); }
    catch (ex) { err = ex; }
    expect(err).to.not.exist;
  });

  it('should give a properly formed array', function(){
    list(1, 2, 3).toArray().should.be.eql([1,2,3]);
  });
});

describe('immutability', function(){
  var ls3 = list(1, 2, 3);

  it('should be impossible to modify tail', function(){
    ls3.tail = cons(10, nil);
    ls3.tail.toArray().should.be.eql([2, 3]);
  });

  it('should be impossible to modify methods', function(){
    ls3.map = {};
    ls3.map.should.be.an.instanceof(Function);
  });
});

describe('reduce', function(){
  var ls = list(1, 2, 3);

  it('should access all elements in the list', function(){
    var result = ls.reduce(0, function(accu, e){ return accu + e; });
    result.should.be.equal(6);
  });

  it('should call the function from left to right', function(){
    var arr = [];
    ls.reduce([], function(a,e){
      arr.push(e);
    });
    arr.should.be.eql([1, 2, 3]);
  });

});

describe('map', function(){
  var ls = list(1, 2, 3);

  it('should go over all elements', function(){
    ls.map(function(e){ return e * 2; }).toArray().should.be.eql([2, 4, 6]);
  });

});

describe('forEach', function(){
  var ls = list(1, 2, 3);

  it('should go over all elments from left to right', function(){
    var arr = [];
    ls.forEach(function(e){
      arr.push(e);
    });
    arr.should.be.eql([1, 2, 3]);
  });

});

describe('isEmpty', function(){
  it('should have the proper values from the factory', function(){
    list().isEmpty.should.be.true;
    list(1).isEmpty.should.be.false;
  });

  it('should have the proper values at the tails', function(){
    list(1,2).tail.isEmpty.should.be.false;
    list(1,2,3).tail.tail.tail.isEmpty.should.be.true;
  });

});

describe('dropWhile', function(){
  it('should drop things...', function(){
    var res = list(1,2).dropWhile(function(e) { return e === 1 }).toArray();
    res.should.be.eql([2]);
  })
});

describe('takeWhile', function(){
  it('should keep until the predidate becomes false', function(){
    var res = list(1,2,3,4).takeWhile(function(e) { return e < 3}).toArray();
    res.should.be.eql([1, 2]);
  })
});

describe('prepend', function(){
  it('should add at the begining', function(){
    var res = list(2,3).prepend(1).toArray();
    res.should.be.eql([1, 2, 3]);
  })
})