Wie eine leere Liste mit S, K und I combinators schreiben?
-
16-09-2019 - |
Frage
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
Lösung
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.)