S, K, and I COMBINATORS in HASKELL
by
Gary T. Leavens
$Date: 2013/02/20 14:47:22 $
This (semi-)literate Haskell program gives some simple combinators.
> module SKICombinators where
The historical names for the combinators below use capital letters.
This can't be done in Haskell.
The s combinator given the following type by Haskell.
s :: (a -> b -> c) -> (a -> b) -> a -> c
Unfortunately, this isn't general enough, as the functions need to be
polymorphic.
> i x = x
> k c x = c
> s f g x = f x (g x)
b is a curried version of compose
> b = s (k s) k
Church numerals, which represent numbers by repeated application:
> zero = k i
> add1 = s b
d is a decision procedure. It satisfies the equations:
(((d x) y) zero) = x
(((d x) y) (add1 z)) = y
> d = ((s (k (s ((s (k s)) ((s (k (s i))) ((s (k k)) k)))))) ((s (k k)) k))
The y combinator, even when translated into s, k, and i, doesn't type check.
This is because, fundamentally, the type assigned to s is not polymorphic
enough, as it assumes that x is a monomorphic function. Thus the subterm
((s i) i) below doesn't typecheck...
The y combinator is supposed to satisfy the unrolling property:
(y f) = f (y f)
y = ((s ((s ((s (k s)) k)) (k ((s i) i)))) ((s ((s (k s)) k)) (k ((s i) i))))
The same problem occurs with Turing's fixpoint combinator...
theta = (((s (k (s i))) ((s i) i)) ((s (k (s i))) ((s i) i)))