Как написать пустой список, используя комбинаторы S, K и I?
-
16-09-2019 - |
Вопрос
Я знаю это:
(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.Кто-нибудь знает?
Заранее спасибо, Эдвин Хосе Палатинкал
Решение
Единственное, что вам нужно от nil
представление заключается в том, чтобы иметь возможность идентифицировать его - напишите некоторые null?
предикат, который возвращает "true" для nil
и "false" для всех остальных пар.Это означает, что ответ зависит от вашего представления значения true / false.С общим выбором λxy.x
и λxy.y
, удобная кодировка для nil
является λf.[true]
.Перевести это на SKI сейчас очень легко (и я не буду делать это здесь, так как это выглядит как домашнее задание ...).
(Кроме того, реализация null?
предикат, заданный этим представлением для nil
это хорошее упражнение.)