problem 2

1 files changed, 7 insertions, 1 deletions

diff --git a/src/HW.hs b/src/HW.hs
index 7e4e579..ac06695 100644
--- a/src/HW.hs
+++ b/src/HW.hs
@@ -21,10 +21,16 @@ fv (App m1 m2) = (fv m1) `Set.union` (fv m2)
     subst n x e     e[x := n]
 -}
 subst :: Expr -> String -> Expr -> Expr
--- subst _ _ _ = Var "UNIMPLEMENTED" -- Replace with your solution to problem 2
 subst n x (Var e)
     | x == e = n
     | otherwise = Var e
+subst n x (App m1 m2) = App (subst n x m1) (subst n x m2)
+subst n x (Lam y m)
+    | x == y = Lam y m
+    | y `Set.notMember` (fv n) = Lam y (subst n x m)
+    | otherwise = Lam y' (subst n x (subst (Var y') y m))
+  where
+    y' = pickFresh ((fv n) `Set.union` (fv m)) y
 
 -- | Take a single step in normal order reduction or return Nothing
 normalstep :: Expr -> Maybe Expr