如何编写使用S，K和我组合程序列表为空？

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

但我不知道如何编译“零”为S，K和我组合程序。有谁知道？

在预先感谢 埃德圣何塞Palathinkal

Answer 1

您从nil表示唯一需要的是能够识别它 - 写一些null?断言，对于nil和“假”的所有其它对返回“真”。这意味着，答案取决于你的真/假代表性。与λxy.x和λxy.y的共同选择，对于nil便利编码λf.[true]。翻译这SKI现在是很容易的（我不会做它在这里，因为它看起来像功课...）。

（另外，实施给予该表示为null?一个nil谓词是很好的运动。）