Como escrever uma lista vazia usando S, K e I combinators?
-
16-09-2019 - |
Pergunta
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 ??p>
(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
Solução
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.)