3
\$\begingroup\$

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 LISP´s 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 cases
var 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));
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

The way quick sort is defined (requiring random access) it cannot be efficient for linked lists (especially immutable ones).

I recommend a recursive implementation of merge sort. It will be clear and concise. It should also be relatively efficient.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.