Wie eine leere Liste mit S, K und I combinators schreiben?

Question

Ich weiß, dass:

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

Ich möchte eine Liste wie folgt schreiben

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

, die in etwa so sein wird:

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

Aber ich weiß nicht, wie ‚Null‘ zu kompilieren in S, K und I combinators. Kennt jemand?

Vielen Dank im Voraus, Edwin Jose Palathinkal

Answer 1

Das einzige, was man von einer nil Darstellung muß in der Lage sein, es zu identifizieren - einig null? Prädikat schreiben, die „true“ für nil und „false“ für alle anderen Paare zurück. Dies bedeutet, dass die Antwort auf Ihre Darstellung wahr / falsch abhängt. Mit der gemeinsamen Wahl von λxy.x und λxy.y, eine bequeme Codierung für nil ist λf.[true]. Die Umsetzung dieses zu SKI ist sehr einfach, jetzt (und ich werde es hier nicht tun, da es wie Hausaufgaben sieht ...).

(Auch ein null? Prädikat Umsetzung dieser Darstellung für nil gegeben ist eine gute Übung.)