SKI.hs

data E = S | K | App E E

-- big step reduction, eager, may not terminate
reduce :: E -> E
reduce (App (App K x) y) = reduce x
reduce (App (App (App S x) y) z) =
  let a = reduce x in
  let b = reduce y in
  let c = reduce z in
  reduce (App (App a c) (App b c))
reduce (App x y) = reduce (App (reduce x) (reduce y))
reduce other = other