Lambda-calculus beta-reduction algorithm

gistfile1.hs

import Data.Traversable

data Term a = 
      Var a
    | Lambda a (Term a)
    | Apply (Term a) (Term a)

instance Show a => Show (Term a) where
    show (Var v)       = show v
    show (Lambda n t)  = "/" ++ (show n) ++ "." ++ (show t)
    show (Apply t1 t2) = "(" ++ (show t1) ++ " " ++ (show t2) ++ ")"

--instance Traversable (Term a) where
--    traverse f (Var a) = f (Var a)
--    traverse f (Lambda n t) = f (Lambda n (traverse t))
--    traverse f (Apply t1 t2) = f (Apply (traverse t1) (traverse t2))

reduce :: Eq a => Term a -> Term a
reduce (Var v)       = Var v
reduce (Lambda a t)  = Lambda a (reduce t)
reduce (Apply t1 t2) = apply (reduce t1) (reduce t2)

apply :: Eq a => Term a -> Term a -> Term a
apply (Lambda param t1) t2 = reduce $ rename param t2 t1
apply t1 t2 = Apply t1 t2

fmap' :: (Term a -> Term a) -> Term a -> Term a 
fmap' f (Var v) = f (Var v)
fmap' f (Lambda v t) = Lambda v (fmap' f t)
fmap' f (Apply t1 t2) = Apply (fmap' f t1) (fmap' f t2)
 
rename :: Eq a => a -> Term a -> Term a -> Term a
rename a t1 t2 = fmap' replace t2
    where replace = \(Var x) -> if x == a then t1 else (Var x)

Why didn't you do more???

Still beat myself about it till this day

…

On 2 Dec 2019, at 21:13, Matthew Evans ***@***.***> wrote:  Why didn't you do more??? — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or unsubscribe.

Haha, thanks very much for this gist, was super helpful!

how do you run it?
I mean function call and arguments stuff