Expression for defining recursive function

Question

How do I use recursive function in Haskell?

I'm writing an evaluator for a little expression language, but I'm stuck on the Rec construct.

This is the language:

    data Expr = Var Nm  | Lam (Nm,Ty) Expr | App Expr Expr
          | Val Int | Add Expr Expr | If Expr Expr Expr
          | Rec Expr         

And this the evaluator so far:

    type Env = [ (Nm, Value) ]
    data Value = Clos Env Expr
               | Vint Int
           deriving Show
    ev :: Env -> Expr -> Value
    ev _   (Val n) = Vint n 
    ev env (Add e1 e2) = Vint (n1 + n2)  
       where
         Vint n1 = ev env e1  
         Vint n2 = ev env e2
    ev env (If e e1 e0) = if n==0 then ev env e0 else ev env e1
                              where 
                                Vint n = ev env e
    ev env (Var x) = case lookup x env of
                          Nothing -> error (x)
                          Just v  -> v
    ev env (Lam x e) = Clos env (Lam x e)
    ev env (App e1 e2) = case v1 of
                            Clos env1 (Lam (x,t) e) -> ev ((x,v2):env1) e
                              where
                                v1 = ev env e1
                                v2 = ev env e2

I would like to call the actual recursive function and execute it to get the sum from 1 to 100.

This is my test function I want to evaluate:

    t1 = Rec  (Lam ("f", INT :-> INT) . Lam ("i", INT) $
                If (Var "i")
                    (Var "i" `Add` (App (Var "f") (Var "i" `Add` Val(-1))))
                    (Var "i")
            )
    ev [] (App t1 (Val 100))

asnwer : Vint 5050

I've tried to make expression.

but,I got this error, ":(6,1)-(29,98): Non-exhaustive patterns in function ev"
I think there is a running error because the recursive function is not working properly.
Can you help me solve the problem?

Answer 1

You might be looking for:

eval env (Rec (Lam (f,t) e)) = v
  where v = eval ((f,v):env) e

It's a little tricky. The idea is to close the body e of the Rec (Lam ...) construction in an environment that binds f to the value v of the returned closure itself. The easiest way to do it is using the recursive construction above, where the returned closure v references its own value in its context, lifting the recursive binding in your expression language to a recursive binding in Haskell.

Alternatively, if you don't want to use a recursive binding in the host language, there are other ways to do it. You can introduce a new value that represents a recursively bound closure:

data Value = ...
       | Loop Nm Value  -- this Value is a Clos
       ...

and then evaluating a Rec produces a Loop in place of the recursive binding:

eval env (Rec (Lam (f,t) e)) = Loop f (eval env e)

and you add a case to your App evaluator to handle the recursion:

eval env (App e1 e2) = case v1 of
  Loop f (Clos env1 (Lam (x,t) e)) -> eval ((x,v2):(f,v1):env1) e
  Clos env1 (Lam (x,t) e) -> eval ((x,v2):env1) e
  where
    v1 = eval env e1
    v2 = eval env e2

(I think I got that right. You might need to check some variable capture scenarios to be sure.)