Выражение для определения letrec, реализующего небольшой язык в Haskell

Обратите внимание, что ваша тестовая программа неверна. Вы не хотите применять «не». Число n четное, если n-1 НЕчетное, а не если оно НЕ НЕЧЕТНОЕ. Итак, должно быть:

t1 = LetRec
    [ (("even", INT:->INT), Lam ("i",INT) $ If (Var "i")
                                            (App (Var "odd") 
                                                 (Var "i" `Add` Val (-1)))
                                            (Val 1))
    , (("odd",  INT:->INT), Lam ("i",INT) $ If (Var "i")
                                            (App (Var "even") 
                                                 (Var "i" `Add` Val (-1)))
                                            (Val 0))
    ]
  (App (Var "odd") (Val 7))

Ваш случай LetRec почти правильный. По какой-то причине вы только что написали его для обработки только одноэлементных списков. Кроме того, вы хотите поместить привязки letrec в начало списка привязок среды, а не в конец, иначе привязки за пределами letrec будут иметь приоритет. Пытаться:

eval env (LetRec bnds body) = v
  where v = eval env' body
        env' = [(n, eval env' e) | ((n,_),e) <- bnds] ++ env

Вот полная программа. При запуске он должен печатать Vint 1:

type Nm = String
data Ty = INT | Ty :-> Ty
  deriving (Show)

data Expr = Var Nm  | Lam (Nm,Ty) Expr | App Expr Expr
          | Val Int | Add Expr Expr | If Expr Expr Expr
          | Let Nm Expr Expr
          | LetRec [((Nm,Ty),Expr)] Expr
          deriving (Show)

type Env = [ (Nm, Value) ]
data Value = Clos Env Expr
           | Vint Int
       deriving (Show)

eval :: Env -> Expr -> Value
eval _   (Val n) = Vint n
eval env (Add e1 e2) = Vint (n1 + n2)
  where
    Vint n1 = eval env e1
    Vint n2 = eval env e2
eval env (If e e1 e0) = if n==0 then eval env e0 else eval env e1
  where
    Vint n = eval env e
eval env (Var x) = case lookup x env of
  Nothing -> error (x ++ " not defined")
  Just v  -> v
eval env e@(Lam _ _) = Clos env e
eval env (App e1 e2) = case v1 of
  Clos env1 (Lam (x,t) e) -> eval ((x,v2):env1) e
  where
    v1 = eval env e1
    v2 = eval env e2
eval env (Let x e1 e2) = eval env' e2
  where
    env' = (x,v) : env
    v = eval env e1
eval env (LetRec bnds body) = eval env' body
  where env' = [(n, eval env' e) | ((n,_),e) <- bnds] ++ env

t1 :: Expr
t1 = LetRec
    [ (("even", INT:->INT), Lam ("i",INT) $ If (Var "i")
                                            (App (Var "odd")
                                                 (Var "i" `Add` Val (-1)))
                                            (Val 1))
    , (("odd",  INT:->INT), Lam ("i",INT) $ If (Var "i")
                                            (App (Var "even")
                                                 (Var "i" `Add` Val (-1)))
                                            (Val 0))
    ]
  (App (Var "odd") (Val 7))

main :: IO ()
main = print (eval [] t1)