Emulating lisp list operations in js

Question

What would be the proper way to define the cons, car, and cdr functions if we were to use javascript and functional programming? So far I have:

// CAR = λxy.x
// CDR = λxy.y
// CONS = λxy => ?
const car = a => b => a;
const cdr = a => b => b;
const cons = f => a => b;

let pair = cons(3)(4);
console.log(pair(car));
console.log(pair(cdr));

But my issue is pair(car) seems like an odd way to invoke the function. It seems like car(pair) seems like a better way but I'm not sure how to save the pair so it can be passed like that. How would that be done?

Mulan · Accepted Answer · 2022-04-04T18:36:52.703

You can write them using continuations -

const cons = (a,b) => k => k(a,b)
const car = k => k((a,b) => a)
const cdr = k => k((a,b) => b)
const l = cons(1, cons(2, cons(3, null)))
console.log(car(l), car(cdr(l)), car(cdr(cdr(l))), cdr(cdr(cdr(l))))
// 1 2 3 null

Define more like list, toString, map, and filter -

const cons = (a,b) => k => k(a,b)
const car = k => k((a,b) => a)
const cdr = k => k((a,b) => b)

const list = (v, ...vs) => v == null ? null : cons(v, list(...vs))
const toString = l => l == null ? "Ø" : car(l) + "->" + toString(cdr(l))

console.log(toString(list(1,2,3,4,5)))
// 1->2->3->4->5->Ø

const square = x => x * x
const map = (f, l) =>
  l == null
    ? null
    : cons(f(car(l)), map(f, cdr(l)))

console.log(toString(map(square, list(1,2,3,4,5))))
// 1->4->9->16->25->Ø

const isOdd = x => x & 1
const filter = (f, l) =>
  l == null
    ? null
    : Boolean(f(car(l)))
        ? cons(car(l), filter(f, cdr(l)))
        : filter(f, cdr(l))

console.log(toString(filter(isOdd, map(square, list(1,2,3,4,5)))))
// 1->9->25->Ø

Note you could just as easily write cons, car, and cdr abstractions using an array. Lambda is more fun but anything that fulfills the contract is acceptable. Being able to change the underlying representation like this and not require changes in other parts of your program is what makes data abstraction a powerful technique.

const cons = (a,b) => [a,b]
const car = k => k[0]
const cdr = k => k[1]
const l = cons(1, cons(2, cons(3, null)))
console.log(car(l), car(cdr(l)), car(cdr(cdr(l))), cdr(cdr(cdr(l))))
// 1 2 3 null

thanks for this. Is the answer I have close to this aside from currying the arguments? — David542, Apr 04 '22 at 18:25
@David it effectively works the same yes but yours has more abstraction — Mulan, Apr 04 '22 at 18:33
thanks for the feedback. Ok, I added a second example which now allows passing it pairs instead of everything having to be a separate argument. Does that seem a bit better? — David542, Apr 04 '22 at 18:36
the last part is very cool as well -- thanks for taking the time to answer this it's so great! — David542, Apr 04 '22 at 18:37
I'm glad you enjoyed :D There's another representation for `cons` in [this Q&A](https://stackoverflow.com/a/51460654/633183). — Mulan, Apr 04 '22 at 18:49

David542 · Answer 2 · 2022-04-04T18:39:36.417

The following would be one way to define it, where car and cdr take one argument (a pair) instead of two:

// CAR = λxy.x or λp.p[0] where p is xy and p[0] means the first argument (x)
// CDR = λxy.y or λp.p[1] where p is xy and p[1] means the second argument (y)
// CONS = λxyf.xyf -- basically just saving x and y in a closure and deferring a function call
const first = a => b => a;
const second = a => b => b;
const getFirstFromPair = p => p(first), car = getFirstFromPair;
const getSecondFromPair = p => p(second), cdr = getSecondFromPair;
const cons = a => b => f => f(a)(b);

let pair = cons(3)(4);
console.log(car(pair));
console.log(cdr(pair));

Or, if we allow a pair as a single argument, such as (1,2):

const cons = (a,b) => f => f(a,b); // f is like a fake function call to do encapsulation
const car  = f => f((a,b) => a);     // and we have to un-do the function call here by passing it the first
const cdr  = f => f((a,b) => b);
console.log(cdr(cons(1,2)));

small typo in your edit. `f((a,b))` will always evaluate to `f(b)`. update to `f(a,b)` and it will fix the problem. — Mulan, Apr 04 '22 at 18:38

Emulating lisp list operations in js

2 Answers2