Comment écrire une liste vide en utilisant S, K et I combinators?
-
16-09-2019 - |
Question
Je sais que:
(cons [p] [q]) is ((s ((s i) (k [p]))) (k [q]))
(car [lst]) is ([lst] k)
(cdr [lst]) is ([lst] (k i))
Je veux écrire une telle liste
(cons [a] (cons [b] (cons [c] [nil])))
, qui va être quelque chose comme ceci:
((s ((s i) (k [a]))) (k ((s ((s i) (k [b]))) (k ((s ((s i) (k [c]))) (k [nil]))))))
Mais je ne sais pas comment compiler « néant » en S, K et I combinateurs. Est-ce que quelqu'un sait?
Merci d'avance, Edwin Jose Palathinkal
La solution
La seule chose que vous avez besoin d'une représentation de nil
est de pouvoir identifier - écrire du prédicat null?
qui retourne « true » pour nil
et « false » pour toutes les autres paires. Cela signifie que la réponse dépend de votre représentation de vrai / faux. Avec le choix commun de λxy.x
et λxy.y
, un codage pratique pour nil
est λf.[true]
. Traduire ce Skier est très facile maintenant (et je ne le ferai pas ici, car il ressemble à ses devoirs ...).
(En outre, la mise en œuvre d'un prédicat null?
donné cette représentation pour nil
est un bon exercice.)