Come scrivere un elenco vuoto utilizzando K S e I combinatori?
-
16-09-2019 - |
Domanda
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
Soluzione
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.)