From 7752d73216578d5961751b5d0535088d384b4aa6 Mon Sep 17 00:00:00 2001
From: Arnaud Bailly <arnaud.bailly@iohk.io>
Date: Sat, 25 Jan 2025 10:45:41 +0100
Subject: Move λ-calcul workshop code to subdirectory
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 lambda-calcul/elixir/ast.ex | 34 ++++++++++++++++++++++++++++++++++
 1 file changed, 34 insertions(+)
 create mode 100644 lambda-calcul/elixir/ast.ex

(limited to 'lambda-calcul/elixir/ast.ex')

diff --git a/lambda-calcul/elixir/ast.ex b/lambda-calcul/elixir/ast.ex
new file mode 100644
index 0000000..4305b7b
--- /dev/null
+++ b/lambda-calcul/elixir/ast.ex
@@ -0,0 +1,34 @@
+defmodule Ast do
+  def var(name), do: {:var, name}
+  def abs(param, body), do: {:abs, param, body}
+  def app(func, param), do: {:app, func, param}
+
+  def pprint(expr) do
+    case expr do
+      {:var, name} -> name
+      {:abs, param, body} -> "(λ #{param} . #{pprint(body)})"
+      {:app, func, param} -> "#{pprint(func)} #{pprint(param)}"
+    end
+  end
+
+  def free_vars(expr) do
+    case expr do
+      {:var, name} -> MapSet.new([name])
+      {:abs, param, body} -> MapSet.delete(free_vars(body), param)
+      {:app, func, param} -> MapSet.union(free_vars(func), free_vars(param))
+    end
+  end
+
+  def subst(expr, old_var, new_expr) do
+    case expr do
+      {:var, name} ->
+        if name == old_var, do: new_expr, else: expr
+
+      {:abs, param, body} ->
+        if param == old_var, do: expr, else: {:abs, param, subst(body, old_var, new_expr)}
+
+      {:app, func, param} ->
+        {:app, subst(func, old_var, new_expr), subst(param, old_var, new_expr)}
+    end
+  end
+end
-- 
cgit v1.2.3