update, add safe division
[lambda.git] / code / ski_evaluator.hs
1 data Term = I | S | K | App Term Term deriving (Eq, Show)
2
3 skomega = (App (App (App S I) I) (App (App S I) I))
4 test = (App (App K I) skomega)
5
6 reduce_if_redex :: Term -> Term
7 reduce_if_redex t = case t of
8   App I a -> a
9   App (App K a) b -> a
10   App (App (App S a) b) c -> App (App a c) (App b c)
11   _ -> t
12
13 is_redex :: Term -> Bool
14 is_redex t = not (t == reduce_if_redex t)
15
16 reduce_try2 :: Term -> Term
17 reduce_try2 t = case t of
18   I -> I
19   K -> K
20   S -> S
21   App a b ->
22     let t' = App (reduce_try2 a) (reduce_try2 b) in
23       if (is_redex t') then reduce_try2 (reduce_if_redex t')
24                        else t'