Lambda Calculus reducer

LCReducer.hs

data Expr = DeBruijn Int
          | App Expr Expr
          | Lambda Expr deriving Show


eval :: Expr -> Expr
eval (App (Lambda body) arg) = (arg `captureIn` body) 0
eval (App (App lhs rhs) arg) = eval $ App (eval (App lhs rhs)) arg
eval a = a

captureIn :: Expr -> Expr -> Int -> Expr
-- 
captureIn arg body@(DeBruijn i) depth
    | depth == i = arg
    | otherwise  = body

captureIn arg (App lhs rhs) depth =
    eval $ App ((arg `captureIn` lhs) depth)
               ((arg `captureIn` rhs) depth)

captureIn arg (Lambda body) depth =
    Lambda $ (arg `captureIn` body) (depth + 1)


main = print $ eval $ App (Lambda (DeBruijn 0)) (DeBruijn 1)