Jak napisać pustą listę używając kombinatorów S, K i I?

Question

wiem, że:

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

Chcę napisać listę jak ten

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

, która będzie coś takiego:

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

ale nie wiedzieć, jak skompilować "zero" w kombinatory S, K i I. Czy ktoś wie?

Dzięki z góry, Edwin Jose Palathinkal

Answer 1

Jedyne czego potrzebujesz od nil reprezentacja jest w stanie go zidentyfikować - napisać null? predykat, która zwraca „true” dla nil i „false” dla wszystkie pozostałe pary. Oznacza to, że odpowiedź zależy od reprezentacji wartości true/false. Przy powszechnym wyborze λxy.x i λxy.y wygodnym kodowaniem dla nil jest λf.[true]. Przetłumaczenie tego na SKI jest teraz bardzo łatwe (i nie zrobię tego tutaj, ponieważ wygląda jak zadanie domowe ...).

(także wdrożenie null? orzecznik W tej reprezentacji na nil jest dobrym ćwiczeniem.)