SKI combinator calculus

*Main> termToString $ ski (E2 (E3 S (E2 K (Var 'x')) (E3 S I I)) (Var 'y'))
"xyy"

という感じで動作するプログラム．某 Skype チャットに SKI という単語が出てきてふと思い出したので書いてみた．例によって間違ってる可能性ありありなので適当に指摘してもらえるとありがたいのです．

data Term = Var Char
          | I
          | K
          | S
          | E2 Term Term
          | E3 Term Term Term
          | E4 Term Term Term Term


ski :: Term -> Term

ski (E2 t1 t2) = eval (E2 (ski t1) (ski t2))
ski (E3 t1 t2 t3) = eval (E3 (ski t1) (ski t2) (ski t3))
ski (E4 t1 t2 t3 t4) = eval (E4 (ski t1) (ski t2) (ski t3) (ski t4))
ski t = t


eval :: Term -> Term

eval (E2 I t) = eval t
eval (E3 K t1 t2) = eval t1
eval (E4 S t1 t2 t3) = eval (E2 (eval (E2 (eval t1) (eval t3))) (eval (E2 (eval t2) (eval t3))))

eval (E2 (E2 t1 t2) t3) = eval (E3 t1 t2 t3)
eval (E2 (E3 t1 t2 t3) t4) = eval (E4 t1 t2 t3 t4)
eval (E2 (E2 t1 t2) (E2 t3 t4)) = eval (E3 t1 t2 (E2 t3 t4))
eval (E3 (E2 t1 t2) t3 t4) = eval (E4 t1 t2 t3 t4)

eval t = t


termToString :: Term -> String

termToString S = "S"
termToString K = "K"
termToString I = "I"

termToString (Var c) = [c]

termToString (E2 t1 t2) = termToString t1 ++ termToString t2
termToString (E3 t1 t2 t3) = termToString t1 ++ termToString t2 ++ termToString t3
termToString (E4 t1 t2 t3 t4) = termToString t1 ++ termToString t2 ++ termToString t3 ++ termToString t4