```OCaml                                                          Haskell
==========================================================     =========================================================

type term = I | S | K | App of (term * term)                   data Term = I | S | K | App Term Term deriving (Eq, Show)

let skomega = App (App (App (S,I), I), App (App (S,I), I))     skomega = (App (App (App S I) I) (App (App S I) I))

reduce_one_step :: Term -> Term
let reduce_one_step (t:term):term = match t with               reduce_one_step t = case t of
App(I,a) -> a                                                App I a -> a
| App(App(K,a),b) -> a                                         App (App K a) b -> a
| App(App(App(S,a),b),c) -> App(App(a,c),App(b,c))             App (App (App S a) b) c -> App (App a c) (App b c)
| _ -> t                                                       _ -> t

is_redex :: Term -> Bool
let is_redex (t:term):bool = not (t = reduce_one_step t)       is_redex t = not (t == reduce_one_step t)

reduce :: Term -> Term
let rec reduce (t:term):term = match t with                    reduce t = case t of
I -> I                                                       I -> I
| K -> K                                                       K -> K
| S -> S                                                       S -> S
| App (a, b) ->                                                 App a b ->
let t' = App (reduce a, reduce b) in                          let t' = App (reduce a) (reduce b) in
if (is_redex t') then reduce (reduce_one_step t')             if (is_redex t') then reduce (reduce_one_step t')
else t'                                                       else t'
```
```let rec reduce_lazy (t:term):term = match t with