¿Cómo escribir una lista vacía usando los combinadores S, K y I?

Question

Sé que:

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

Quiero escribir una lista como esta

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

, que va a ser algo como esto:

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

Pero no lo hago saber cómo compilar 'nil' en los combinadores S, K y I. ¿Alguien sabe?

Gracias de antemano, Edwin José Palathinkal

Answer 1

La única cosa que necesita de una representación nil es ser capaz de identificarlo - escribir algunos null? predicado que devuelve "true" para nil y "falso" para todos los otros pares. Esto significa que la respuesta depende de su representación de verdadero/falso. Con la opción común de λxy.x y λxy.y, una codificación conveniente para nil es λf.[true]. Traducir esto a SKI ahora es muy fácil (y no lo haré aquí, ya que parece una tarea ...).

(Además, la implementación de un null? predicado dado esta representación para nil es un buen ejercicio.)