Functional linked list

Question

I've been implementing functional linked lists in different languages, just as a learning exercise. I'm looking for feedback in general: code correctness, best practices, design patterns; everything you think about this. Is it bad code? Where can it be improved?

/**
*
* Constructing Linked Lists
*
* Our linked list data structure consists of two fundamental building blocks: Nil and cons. Nil represents the 
* empty list and serves as a sentinel for more complex lists. The cons operation extends a list at the front by 
* inserting a new value.
*
* The lists we construct using this method consist internally of nested arrays of 2 items. For example, the list [1, 2, 3] 
* is represented by the expression cons(1, cons(2, cons(3, Nil))) which evaluates to the nested arrays [1, [2, [3, Nil]]].
*
*/

var Nil = "Nil";

/** Extends a list at the front by inserting a new value. */
function cons(head, tail) {
    tail = typeof tail === "undefined" ? Nil : tail;
    return [head, tail];
}

/**
* Define list instances using a more convenient syntax and without deeply nested cons calls.
* lst() === Nil                                                                                                                                                                
* lst(1, 2, 3) === [1, [2, [3, Nil]]] 
*/
function lst() {
    var arg_array = Array.prototype.slice.call(arguments);  // arguments cast from object to array
    if (arg_array.length === 0) return Nil;
    else return cons(arg_array[0], lst.apply(this, arg_array.slice(1)));
}

/** Returns the first element of a list */
function head(xs) {
    return xs[0];
}

/** Returns a list containing all elements except the first. */
function tail(xs) {
    return xs[1];
}

/** Returns True if the list contains zero elements. */
function isEmpty(xs) {
    return xs === Nil;
}

/** Returns number of elements in a given list. */
function length(xs) {
    if (isEmpty(xs)) return 0;
    else return 1 + length(tail(xs));
}

/** Concatenates two lists. */
function concat(xs, ys) {
    if (isEmpty(xs)) return ys;
    else return cons(head(xs), concat(tail(xs), ys));
}

/** Returns the last element of a non-empty list. */
function last(xs) {
    if (isEmpty(tail(xs))) return head(xs);
    else return last(tail(xs));
}

/** Returns all elements except the last one. */
function init(xs) {
    if (isEmpty(tail(tail(xs)))) return cons(head(xs));
    else return cons(head(xs), init(tail(xs)));
}


/** Returns the input list, reversed. */
function reverse(xs) {
    if (isEmpty(xs)) return xs;
    else return concat(reverse(tail(xs)), cons(head(xs), Nil));
}

/** Returns the first n elements of the given list. */
function take(n, xs){
    if (n < 1) return Nil;
    else return cons(head(xs), take(n - 1, tail(xs)));
}

/** Returns a copy of input list, without the first n elements. */
function drop(n, xs){
    if (n < 1) return xs;
    else return drop(n - 1, tail(xs));
}

/**  Returns a subset of the input list that includes the items in the range from, to. */
function piece(from, to, xs){
    return take(to - from, drop(from, xs));
}

/** Removes the element of the list at given index */
function removeOne(index, xs){
    return concat(take(index - 1, xs), drop(index, xs));
}

Answer 1

Your code runs into a lot of problems because it chooses a weird value for Nil, and because it fails to check for that value. What is the correct result for head(lst())? "N", Nil, or a type error?

Because "Nil" === "Nil" holds (value type), but [] === [] does not (reference type), I suggest you use the empty array to represent Nil (this is also closer to Lisp semantics). The advantage of this is that your cons can then contain any value in the tail position – the string "Nil" was previously forbidden.

Another good possibility would be to use a false value, this would even remove the need for isEmpty! I will assume var Nil = undefined for the rest of this answer, even though now undefined and Nil cannot be distinguished.

As already mentioned, you fail to check for Nil, therefore your code can be considered incorrect. E.g. head could be:

function head(xs) {
  if (!xs) return Nil;
  return xs[0];
}

or even

function head(xs) {
  if (!xs || !(xs instanceof Array)) {
    throw "Expected pair";
  }
  return xs[0];
}

Other functions that build on these primitives are in turn correct, although the new value for Nil simplifies the code a bit, e.g.

function length(xs) {
    if (!xs) return 0;
    return 1 + length(tail(xs));
}

Notice that I removed the unnecessary else, but this is a matter of personal style.

You may want to specify what exactly the output of take(3, Nil) and similar functions should be. It seems you are assuming that all indices will always be inside the correct bounds. Better be explicit about that. In this case, valid interpretations of var n = 3; take(n, Nil) would be to:

• Use the n as an upper limit, and return the empty list/Nil.
• Use n as a strict limit, and fill up the surplus cons with Nil in the head.
• Throw an error that the index is out of bounds.

The first solution is most DWIM, it would seem to me.

Your piece function does not document if the from and to bounds are inclusive or exclusive. Because you will drop(from, xs), the from index is not included in the output. The to is exclusive as well. This counterintuitive behaviour is not made clear in the documentation!

Your removeOne is even weirder by using one-based indexing instead of zero-based indexing, like piece does.

Interestingly, you don't have an indexing function, e.g. at(1, lst(0, 1, 2)) === 1.

Summary

Your code looks fine, but you haven't carefully considered (or tested) the actual behaviour of your functions. When writing complex code, a few well-chosen test cases can help detect errors early.