Singly-linked lists

functionList.js

function List() {}

function EmptyList() {}
EmptyList.prototype = new List();
EmptyList.prototype.constructor = EmptyList;

EmptyList.prototype.toString = function() { return '()'; };
EmptyList.prototype.isEmpty = function() { return true; };
EmptyList.prototype.length = function() { return 0; };
EmptyList.prototype.push = function(x) { return new ListNode(x, this); };
EmptyList.prototype.remove = function(x) { return this; };
EmptyList.prototype.append = function(xs) { return xs; };

function ListNode(value, next) { this.v = value; this.n = next; }
ListNode.prototype = new List();
ListNode.prototype.constructor = ListNode;
ListNode.prototype.isEmpty = function() { return false; };

ListNode.prototype.toString = function() {
  var n = this.n;
  var r = [this.v];
  while (!n.isEmpty()) {
    r.push(n.v);
    n = n.n;
  }
  return '(' + r.join(' ') + ')';
};

ListNode.prototype.head = function() { return this.v; };
ListNode.prototype.tail = function() { return this.n; };
ListNode.prototype.length = function() { return 1 + this.n.length(); };
ListNode.prototype.push = function(x) { return new ListNode(x, this); };
ListNode.prototype.remove = function(x) {
  var t = this.n.remove(x);
  if (x == this.v) return t;
  if (t == this.n) return this;
  else return new ListNode(this.v, t);
};
ListNode.prototype.append = function(xs) { return new ListNode(this.v, this.n.append(xs)); };


var assert = require('assert');
var should = require('should');


describe("Basic Tests of Functional List (javascript)", function() {
  var mt, l1, l2, l3, l4;

  before(function() {
    mt = new EmptyList;
    l1 = mt.push('a');
    l2 = l1.push('b');
    l3 = l1.push('c');
    l4 = l3.append(l2);
  });

  it('Tests on the empty list.', function() {
    assert(mt.length() === 0, 'Has length zero.');
    assert(mt.isEmpty() === true, 'Empty list is empty.');
    assert(mt.toString() === '()', 'To String on empty list.');
  });

  it("After pushing an 'a'", function() {
    assert(l1.length() === 1, 'Length is one.');
    assert(l1.isEmpty() === false, 'List no longer empty');
    assert(l1.head() === 'a', 'First item in list is correct.');
    assert(l1.tail().isEmpty(), 'Tail is empty.');
    assert(l1.toString() === '(a)', "To String on l1.");
  });

  it("After pushing a 'b'", function() {
    assert(l2.length() === 2, 'After two items, length is two.');
    assert(l2.head() === 'b', 'Second item is in the list.');
    assert(l2.tail() === l1, 'Tail of l1.push() is l1.');
    assert(l2.toString() === '(b a)', 'To String on l2.');
  });

  it("After pushing a 'c' onto the list of just 'a'", function() {
    assert(l3.length() === 2, 'After two items, length is 2');
    assert(l3.head() === 'c', 'Second item is in the list.');
    assert(l3.tail() === l1, 'Tail of l1.push() is l1.');
    assert(l3.toString() === '(c a)', 'To String on l3');
  });

  it("Appending (b a) to (c a)", function() {
    assert(l4.length() === 4, 'After append, have twice as many elements');
    assert(l4.head() === 'c', 'Append puts this first (a)');
    assert(l4.tail().head() === 'a', 'Append puts this first (b)');
    assert(l4.tail().tail() === l2, 'Append leaves argument untouched.');
  });

  it("Removing 'a' from '(c a b a)'", function() {
    assert(l4.remove('a').length() === 2, "Remove both 'a' from l4");
  });

  it("Removing 'b' from '(c a b a)'", function() {
    assert(l4.remove('b').length() === 3, 'Length should be three');
    assert(l4.remove('b').tail().tail() === l4.tail().tail().tail(), 'l4.remove l4.head() is l4.tail()');
  });

  it("Removing 'c' from '(c a b a)'", function() {
    assert(l4.remove('c').length() === 3, 'Length should be three');
    assert(l4.remove('c') === l4.tail(), 'l4.remove(first) is l4.tail()');
  });
  
    
  it("Removing 'a' from '(a)'", function () {
    assert(l1.remove('a') === mt, 'l1.remove(first) is empty');
  });
});