如何使用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组合器.有人知道吗？

在此先感谢Edwin Jose Palathinkal

Answer 1

nil表示中唯一需要的是能够识别它 - 写一些null?返回"true"的谓词nil和所有其他对的"false".这意味着答案取决于您对真/假的表示.通常选择?xy.x和?xy.y,方便的编码nil是?f.[true].将其翻译成SKI现在非常简单(我不会在这里做,因为它看起来像家庭作业......).

(另外,null?给出这种表示的谓词nil是一个很好的练习.)