How to write an empty list using S, K and I combinators?

Question

I know that:

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

I want to write a list like this

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

, which is going to be something like this:

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

But I don't know how to compile 'nil' into S, K and I combinators. Does anyone know?

Thanks in advance, Edwin Jose Palathinkal

Answer 1

The only thing you need from a nil representation is to be able to identify it -- write some null? predicate that returns "true" for nil and "false" for all other pairs. This means that the answer depends on your representation of true/false. With the common choice of λxy.x and λxy.y, a convenient encoding for nil is λf.[true]. Translating this to SKI is very easy now (and I won't do it here, since it looks like homework...).

(Also, implementing a null? predicate given this representation for nil is a good exercise.)