Come scrivere una lista vuota usando i combinatori S, K e I?

Question

So che:

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

Voglio scrivere una lista come questa

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

, che sta per essere qualcosa di simile:

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

ma non lo faccio sapere come compilare 'nil' in combinatori S, K e I. Qualcuno sa?

Grazie in anticipo, Edwin Jose Palathinkal

Answer 1

L'unica cosa che serve da una rappresentazione nil è quello di essere in grado di identificarlo - scrivono alcuni null? predicato che restituisce "true" per nil e "false" per tutte le altre coppie. Ciò significa che la risposta dipende dalla tua rappresentazione di vero/falso. Con la scelta comune di λxy.x e λxy.y, una comoda codifica per nil è λf.[true]. Tradurre questo in SKI è molto semplice ora (e non lo farò qui, dato che sembra un compito a casa ...).

(Inoltre, l'attuazione di un null? predicato dato questa rappresentazione per nil è un buon esercizio.)