LambdaCalc.hs

import Control.Applicative

data Expr = Var String
          | Abs String Expr
          | App Expr Expr

instance Show Expr where
    show (Var v)    = v
    show (Abs v e)  = "(\\" ++ v ++ " -> " ++ (show e) ++ ")"
    show (App e e') = "(" ++ (show e) ++ " " ++ (show e') ++ ")"

subst :: Expr -> String -> Expr -> Expr
subst e v e'@(Var v')     = if v == v' then e else e'
subst e v e'@(Abs v' e'') = let uv = v ++ "'" in Abs uv (subst e v $ subst (Var uv) v' e'')
subst e v (App e' e'')    = App (subst e v e') (subst e v e'')

reduce :: Alternative f => Expr -> f Expr
reduce (Abs v e)          = Abs v <$> reduce e
reduce (App (Abs v e) e') = pure $ subst e' v e
reduce (App e e')         = (App e <$> reduce e') <|> (flip App e' <$> reduce e)
reduce _                  = empty

normalize :: Expr -> Expr
normalize e = maybe e normalize $ reduce e

main = print $ normalize (App (App (Abs "x" (Var "x")) (Abs "x" (Var "x"))) (App (Abs "x" (Var "x")) (Abs "x" (Var "x"))))