functional-programming - 如何使用 S、K 和 I 组合器编写一个空列表？

Question

我知道：

(cons [p] [q]) is ((s ((s i) (k [p]))) (k [q]))
(car [lst]) is ([lst] k)
(cdr [lst]) is ([lst] (k i))

我想写一个这样的列表

(cons [a] (cons [b] (cons [c] [nil])))

，这将是这样的：

((s ((s i) (k [a]))) (k ((s ((s i) (k [b]))) (k ((s ((s i) (k [c]))) (k [nil]))))))

但我不知道如何将“nil”编译成 S、K 和 I 组合器。有人知道吗？

在此先感谢埃德温·何塞·帕拉思卡尔

Answer 1

你唯一需要的nil就是能够识别它——写一些null?谓词，对所有其他对返回“true”，nil对所有其他对返回“false”。这意味着答案取决于您对真/假的表示。λxy.x使用and的常见选择，对isλxy.y进行方便的编码。现在把它翻译成 SKI 很容易（我不会在这里做，因为它看起来像家庭作业......）。nilλf.[true]

（此外，在null?给定这种表示的情况下实现谓词 fornil是一个很好的练习。）