¿Cuál sería la forma correcta de definir las funciones cons , car y cdr si usáramos javascript y programación funcional? Hasta ahora tengo:
// 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)); Pero mi problema es que pair(car) parece una forma extraña de invocar la función. Parece que car(pair) parece una mejor manera, pero no estoy seguro de cómo guardar el par para que pueda pasarse así. ¿Cómo se haría eso?
Puedes escribirlos usando continuaciones -
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 Defina más como list , toString , map y 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->Ø Tenga en cuenta que podría escribir con la misma facilidad abstracciones cons , car y cdr usando una matriz. Lambda es más divertido, pero cualquier cosa que cumpla con el contrato es aceptable. Ser capaz de cambiar la representación subyacente de esta manera y no requerir cambios en otras partes de su programa es lo que hace que la abstracción de datos sea una técnica poderosa.
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 nullLa siguiente sería una forma de definirlo, donde car y cdr toman un argumento (un par) en lugar de dos:
// 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)); O, si permitimos un par como un solo argumento, como (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)));