Come scrivere un elenco vuoto utilizzando K S e I combinatori?

Question

Io 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 a questo:

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

Ma non so come compilare 'nil' in K S e I combinatori.Qualcuno lo sa?

Grazie in anticipo, Edwin Jose Palathinkal

Answer 1

L'unica cosa che avete bisogno di un nil la rappresentazione è quello di essere in grado di identificare -- scrivere alcune null? predicato che restituisce "true" per nil e "false" per tutte le altre coppie.Questo significa che la risposta dipende dalla vostra rappresentazione del vero/falso.Con la scelta comune di λxy.x e λxy.y, un comodo codifica per nil è λf.[true].La traduzione di questo SCI è molto facile ora (e non voglio farlo qui, dal momento che sembra compiti a casa...).

(Anche con l'attuazione di una null? predicato dato questo tipo di rappresentazione nil è un buon esercizio.)