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?

CodePudding user response：

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

CodePudding user response：

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)));