From 3a67e69bfe9492d2a2fc5e4b07cc8c909a346064 Mon Sep 17 00:00:00 2001
From: Arnaud Bailly <arnaud@pankzsoft.com>
Date: Mon, 13 Oct 2025 09:27:07 +0200
Subject: add minimal evaluator and type inference

---
 lambda-calcul/haskell/src/Minilang/Lambda/Eval.hs | 36 +++++++++++++++++++++++
 1 file changed, 36 insertions(+)
 create mode 100644 lambda-calcul/haskell/src/Minilang/Lambda/Eval.hs

(limited to 'lambda-calcul/haskell/src/Minilang/Lambda/Eval.hs')

diff --git a/lambda-calcul/haskell/src/Minilang/Lambda/Eval.hs b/lambda-calcul/haskell/src/Minilang/Lambda/Eval.hs
new file mode 100644
index 0000000..68b01be
--- /dev/null
+++ b/lambda-calcul/haskell/src/Minilang/Lambda/Eval.hs
@@ -0,0 +1,36 @@
+module Minilang.Lambda.Eval where
+
+import Data.Text (Text)
+
+data Term
+  = Var Text
+  | Lam Text Term
+  | App Term Term
+  deriving (Show, Eq)
+
+type Env = [(Text, Term)]
+
+-- call-by-value evaluator
+eval :: Term -> Env -> Term
+eval (Var x) env = case lookup x env of
+  Just v -> v -- we do not need to eval v again
+  Nothing -> Var x
+eval (Lam x body) _env = Lam x body
+eval (App f a) env =
+  -- we need to force evaluation of the argument
+  -- because haskell's default semantics is non-strict
+  -- so if a' is never used, it will not be evaluated!
+  let a' = eval a env
+   in seq a' $ case eval f env of
+        Lam x body -> eval body ((x, a') : env)
+        f' -> App f' a'
+
+evalNeed :: Term -> Env -> Term
+evalNeed (Var x) env = case lookup x env of
+  Just v -> evalNeed v env -- we need to eval v because it might be a redex
+  Nothing -> Var x
+evalNeed (Lam x body) _env = Lam x body
+evalNeed (App f a) env =
+  case evalNeed f env of
+    Lam x body -> evalNeed body ((x, a) : env)
+    f' -> App f' a
-- 
cgit v1.2.3