How to evaluate a simple lambda calculus with a call-by-value semantics: http://www.seas.harvard.edu/courses/cs152/2013sp/lectures/lec07.pdf

Evaluator.hs

data Expr
    = Literal Int
    | Lambda String Expr
    | Apply Expr Expr
    | Var String
    | Sum Expr Expr
    deriving Show

eval :: Expr -> Expr
eval expr =
  case expr of
    -- beta reduction
    Apply (Lambda x e) v | isValue v -> eval (substitute x v e)

    -- stepping application forward until we can get to beta reduction
    Apply f x | isValue f -> eval (Apply f (eval x))
              | otherwise -> eval (Apply (eval f) x)

    -- reduce sums
    Sum (Literal n) (Literal m) -> Literal (n + m)

    -- otherwise we have a value. If not, the initial program was
    -- ill-formed in some way which is what a type system guards against.
    _ | isValue expr -> expr
      | otherwise ->
            error $ "Could not fully evaluate (" ++ show expr ++
                    "). This program got stuck because of a type error or a free variable"

isValue :: Expr -> Bool
isValue expr =
    case expr of
      Var _ -> True
      Literal _ -> True
      Lambda _ _ -> True
      Apply _ _ -> False
      Sum _ _ -> False

substitute :: String -> Expr -> Expr
substitute x v expr =
    case expr of
      Var y | x == y    -> v
            | otherwise -> expr

      Literal _ -> expr

      Lambda y e | x == y    -> expr
                 | otherwise -> Lambda y (substitute x v e)

      Apply e1 e2 -> Apply (substitute x v e1) (substitute x v e2)

      Sum e1 e2 -> Sum (substitute x v e1) (substitute x v e2)