如何使用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組合器。有人知道嗎？

由於提前， 埃德溫·何塞Palathinkal

Answer 1

您從nil表示唯一需要的是能夠識別它 - 寫一些null?謂詞返回nil「真」和「假」爲所有其他對。這意味着答案取決於您對真/假的表示。通過λxy.x和λxy.y的共同選擇，nil的便利編碼是λf.[true]。現在把它翻譯成SKI非常簡單（我不會在這裏做，因爲它看起來像作業...）。

（此外，實施給予這種表示的nil一個null?謂詞是一個很好的鍛鍊。）