module Main where data Lam Var String Abs String Lam App Lam Lam deriv

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
module Main where
data Lam = Var String
| Abs String Lam
| App Lam Lam
deriving(Show)
eval (Var var) = Var var
eval (Abs var term) = Abs var (term)
eval (App (Abs var term) term2) = eval (passVars (Abs var term) var term2)
eval (App var1 term2) = eval (App (eval var1) (term2))
eval term = term
passVars (Abs var1 term) var term1 | var1 == var = passVars (term) var (renameVar term1 var)
passVars (Abs var1 term) var term1 | otherwise = Abs (var1) (passVars (term) var (renameVar term1 var1))
passVars (App t1 t2) var term1 = App (passVars t1 var term1) (passVars t2 var term1)
passVars (Var var1) var term1 | var1 == var = term1
passVars (Var var1) _ _ | otherwise = Var var1
renameVar term name = renameVar' term name 1
where renameVar' (Var name1) name i | name1 == name = Var (show i)
renameVar' (Var name1) _ _ | otherwise = Var (name1)
renameVar' (App t1 t2) name i = App (renameVar' t1 name i) (renameVar' t1 name i)
renameVar' (Abs name1 t) name i | name1 == name = Abs ((show (i+1))) (renameVar' t name (i+1))
renameVar' (Abs name1 t) name i | otherwise = Abs (name1) (renameVar' t name (i))
main = print (eval (App (Abs "a" (Var "a")) (Abs "b" (Var "b"))))