Как написать пустой список, используя комбинаторы 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" для всех остальных пар.Это означает, что ответ зависит от вашего представления значения true / false.С общим выбором λxy.x и λxy.y, удобная кодировка для nil является λf.[true].Перевести это на SKI сейчас очень легко (и я не буду делать это здесь, так как это выглядит как домашнее задание ...).

(Кроме того, реализация null? предикат, заданный этим представлением для nil это хорошее упражнение.)