Comment écrire une liste vide en utilisant S, K et I combinators?

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

Answer 1

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.)