Como escrever uma lista vazia usando S, K e I combinators?

Question

Eu sei que:

(cons [p] [q]) is ((s ((s i) (k [p]))) (k [q]))
(car [lst]) is ([lst] k)
(cdr [lst]) is ([lst] (k i))

Eu quero escrever uma lista como esta

(cons [a] (cons [b] (cons [c] [nil])))

, que vai ser algo como isto:

((s ((s i) (k [a]))) (k ((s ((s i) (k [b]))) (k ((s ((s i) (k [c]))) (k [nil]))))))

Mas eu não sei como compilar 'nulo' em S, K e I combinadores. Alguém sabe?

Agradecemos antecipadamente, Edwin Jose Palathinkal

Answer 1

A única coisa que você precisa de uma representação nil é ser capaz de identificá-lo - escrever algum predicado null? que retorna "true" para nil e "false" para todos os outros pares. Isto significa que a resposta depende de sua representação de verdadeiro / falso. Com a escolha comum de λxy.x e λxy.y, uma codificação conveniente para nil é λf.[true]. Traduzindo isso para SKI é muito fácil agora (e não vou fazê-lo aqui, pois parece que a lição de casa ...).

(Além disso, a implementação de um predicado null? dada esta representação para nil é um bom exercício.)