I have a little project where i am implementing an immutable linked-list (not only...) based on a pair-structure like the LISP cons-cell.The linked list works well and is basically wrapping two variables in a closure in an object, the variables are head and rest (think LISPs car and cdr). I have also added some useful functions like map, fold, forEach, merge, reverse and sort among others. All work well except for sort. As it only works with the default compare-function. I know that the reason is of how i append the list back together after a comparison.Anyone has a better idea of how this might be done? merge-sort? Also suggestions on other parts of the project are welcome! :-)var list = function (arr) {    var listBuilder = function (arr, i) {        if (i + 1 === arr.length)            return pair(arr[i], nil);        else            return pair(arr[i], listBuilder(arr, i + 1));    };    return arr.length > 0 ? listBuilder(arr, 0) : nil;};var pair = function (a, b) {    var cons = function (a, b) {        var p = function (p) { //base closure to hold the data            return p ? a : b;        };                p.head = function () {            return this(true);        };        p.rest = function () {            return this(false);        };        p.equal = function (a) {            return this === a;        };        p.toString = function () {            return '( ' + p.head() + ' , ' + p.rest() + ' )';        };        p.len = function () {            if(nil.equal(p))                return 0;            else                return nil.equal(p.rest()) ? 1 : 1 + p.rest().len();        };        p.get = function (i) {            if(i <= 0){                return p.head();            }else if(nil.equal(p.rest())){                return nil;            }else                return p.rest().get(i - 1);        };        p.append = function(l) {            if(nil.equal(p))                return l;                        if(nil.equal(p.rest()))                return pair(p.head(),l);            else                return pair(p.head(),p.rest().append(l));                        }        p.map = function (fn) {            return p.merge(fn, pair);        };        p.fold = function (fn) {            return p.merge(function (e) {                return e;            }, fn);        }        p.forEach = function (fn) {            if (!nil.equal(p)) {                fn(p.head());                p.rest().forEach(fn);            }        };        p.merge = function (modifierFn, concatFn) {            if(nil.equal(p))                return nil;            else if (nil.equal(p.rest()))                return modifierFn(p.head());            else                return concatFn(modifierFn(p.head()), p.rest().merge(modifierFn, concatFn));        };        p.reverse = function () {                        if (nil.equal(p.rest()))                return p;            else                return p.rest().reverse().append( list([p.head()]) );        };        p.sort = function(cmp){ //quick-sort            var pivot = p.head();                        var left=nil,right=nil;            cmp = cmp === undefined ? function(a,b){return a < b;}: cmp; //defaults to numerical less then             var partion = function(l){                if(cmp(l.head(), pivot))                    left = pair(l.head(),left);                else                    right = pair(l.head(),right);                    if(!nil.equal(l.rest()))                     partion(l.rest());             };                        if(!nil.equal(p) && !nil.equal(p.rest())){                partion(p.rest());                    return left.sort().append(pair(pivot,nil)).append(right.sort());                                    }else{                return p;            }        };        return p;    };    return cons(a, b);};var nil = pair(null, null);nil.toString = function () {    return 'nil';};//uses casesvar l = list([213, 342, 654, 543, 213, 321, 54365, 564, 3221, 45, 7, 8, 53, 6542, 24, 8, 523, 543, 984]);var append = function(a,b){ return a+ ' ' +b;};alert(l.sort().reverse().fold(append));
Quick-sort a linked list?
javascript;linked list;functional programming