lambda1.hs

import Prelude hiding (sum)

data L1
  = F { ($$) :: L1 -> L1 }
  | V { unV :: Int }

infixl 1 $$

instance Show L1 where
  show (F _) = "Function"
  show (V i) = "V " ++ show i

sum :: L1
sum = F $ \f -> F $ sum' f
  where
    sum' f (V 0) = V 0
    sum' f (V n) = V $ n + (unV (f $$ (V $ n - 1)))

k :: L1
k = F $ \x -> F $ \_ -> x

s :: L1
s = F $ \f -> F $ \g -> F $ \x -> f $$ x $$ (g $$ x)

i :: L1
i = s $$ k $$ k

y :: L1
y = s $$ s $$ k $$ (s $$ (k $$ (s $$ s $$ (s $$ (s $$ s $$ k)))) $$ k)

-- y f = f (y f)

main = undefined