SKI.hs

module SKI where

data SKI = S | K | I | A SKI SKI
  deriving (Eq, Show)

reduce :: SKI -> SKI
reduce (A (A (A S x) y) z) = reduce (A (A x z) (A y z))
reduce (A (A K x) y) = reduce y
reduce (A I x) = reduce x
reduce a@(A f x) = let f' = reduce f in if f==f' then a else reduce (A f' x)
reduce a = a