在js中模拟lisp列表操作

Question

如果我们要使用 javascript 和函数式编程，定义 cons、car 和 cdr 函数的正确方法是什么？到目前为止我有：

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

但我的问题是 pair(car) 调用该函数的方式似乎很奇怪。 car(pair) 似乎是一种更好的方法，但我不确定如何保存这对，以便它可以像那样传递。那要怎么做呢？

Answer 1

以下是定义它的一种方法，其中 car 和 cdr 采用一个参数（一对）而不是两个：

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

或者，如果我们允许一对作为单个参数，例如 (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)));

Answer 2

您可以使用延续来编写它们 -

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

定义更像 list、toString、map 和 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->Ø

请注意，您可以使用数组轻松编写 cons、car 和 cdr 抽象。 Lambda 更有趣，但任何满足合同的东西都是可以接受的。能够像这样更改底层表示而不需要更改程序的其他部分，这使得数据抽象成为一种强大的技术。

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

在js中模拟lisp列表操作

Emulating lisp list operations in js

javascript

functional-programming

lisp