Skip to content

Instantly share code, notes, and snippets.

@buzzdecafe
Last active November 17, 2021 10:11
Show Gist options
  • Save buzzdecafe/5272249 to your computer and use it in GitHub Desktop.
Save buzzdecafe/5272249 to your computer and use it in GitHub Desktop.
cons car and cdr implemented as javascript functions. cribbed from SICP http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-14.html#%_thm_2.4then implemented a bunch of functions just for fun.
// clean and pure:
function cons(x, y) {
return function(pick) {
return pick(x, y);
}
}
// does more stuff:
function cons(x, y) {
var fn = function(pick) {
return pick(x, y);
};
fn.toString = function() {
return "(" + asArray(this).join(" ") + ")";
};
fn.pair = true; // to support atom? function
return fn;
}
function car(f) {
return f(function(x, y) { return x; });
}
function cdr(f) {
return f(function(x, y) { return y; });
}
function atom(x) {
return !x.pair;
}
function pair(x) {
return x.pair;
}
function list() {
var args = Array.prototype.slice.call(arguments);
return (args.length === 0) ? null : cons(args.shift(), list.apply(null, args));
}
function map(fn, lat) {
return (lat === null) ? null : cons(fn(car(lat)), map(cdr(lat), fn));
}
function flip(fn) {
return function(a, b) { return fn(b, a); };
}
function foldl(fn, acc, lat) {
return (lat === null) ? acc : foldl(cdr(lat), fn(acc, car(lat)), fn);
}
function append(l, m) {
return (l === null) ? m : cons(car(l), append(cdr(l), m));
}
function reverse(l) {
return (l === null) ? null : append(reverse(cdr(l)), cons(car(l), null));
}
function foldr(fn, acc, lat) {
return (lat === null) ? acc : fn(car(lat), foldr(fn, acc, cdr(lat)));
}
function filter(fn, lat) {
if (lat === null) return null;
if (pred(car(lat))) return cons(car(lat), filter(cdr(lat), fn));
return filter(cdr(lat), fn);
}
function some(pred, lat) {
return (lat === null) ? false : pred(car(lat)) || some(cdr(lat), pred);
}
function every(pred, lat) {
function everyAcc(lat, acc) {
if (lat === null) return acc;
return everyAcc(cdr(lat), pred(car(lat)) && acc);
}
return (lat === null) ? false : everyAcc(lat, true);
}
function leftmost(tree) {
// get the leftmost leaf node
if (tree === null) return null;
if (atom(car(tree))) return car(tree);
return leftmost(car(tree));
}
function contains(tree, a) {
if (tree === null) return false;
if (atom(car(tree)))
return car(tree) === a || contains(cdr(tree), a);
else
return contains(car(tree), a) || contains(cdr(tree), a);
}
function asArray(list) {
var arr = arguments[1] || [];
return (list && car(list)) ? (arr.push(car(list)), asArray(cdr(list), arr)) : arr;
}
function asList(arr) {return list.apply(null, arr);}
@CrossEye
Copy link

As discussed:

function cons(x, y) {
    var fn = function(pick) {
        return pick(x, y);
    };
    fn.toString = function() {
        var nested = !!arguments.length;
        var output = (nested ? x : "(" + x) + " ";
        output += y ? y.toString(true) : "";
        if (!nested) {
            output = output.substring(0, output.length - 1) + ")";
        }
        return output;
    };
    return fn;
}

Then

> cons(50, (cons(100, cons(200, null))));
(50 100 200)

Obviously this should be attached more generically, and not on each such function, but that's the basic idea.

@buzzdecafe
Copy link
Author

nice! I've added a list function that works for arbitrary arguments. Efficient it ain't!

my earlier oversight was not calling apply with a context. duh.

@CrossEye
Copy link

Yeah, I saw that after you left. Figured you'd get it quickly enough. I had to get into it with a debugger a few times before I realized...

@CrossEye
Copy link

Damn it all, I swore I was going to stay away from this stuff for a while. It's a drug, damn it!

This is a little cleaner:

function cons(x, y) {
    var fn = function(pick) {
        return pick(x, y);
    };
    fn.toString = function() {
        return "(" + asArray(this).join(" ") + ")";
    };
    return fn;
}

function asArray(list) {
    var arr = arguments[1] || [];
    return (list && car(list)) ? (arr.push(car(list)), asArray(cdr(list), arr)) : arr;
}

function asList(arr) {return list.apply(null, arr);}

But there is probably a much more clever, cleaner way to do this altogether.

@buzzdecafe
Copy link
Author

yes, fun stuff, i think i dreamed about how this works last night ....

@AutoSponge
Copy link

function toList(arr, list){
    return arr.length ? toList(arr, cons(arr.shift(), list)) : list;
}

car(toList([1,2,3]));            //3
car(cdr(toList([1,2,3])));       //2
car(cdr(cdr(toList([1,2,3]))));  //1

@CrossEye
Copy link

CrossEye commented Apr 4, 2013

Forked and made some changes: https://gist.github.com/CrossEye/5307355

@dkinzer
Copy link

dkinzer commented Oct 3, 2014

cool, have you seen this implementation? https://gist.github.com/bishboria/1170180

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment