Haskell Lambda fold

Question

I have the following algebraic data type representing the Lambda Calculus in Haskell:

data LExpr
    = Var String         -- variable
    | App LExpr LExpr    -- function application
    | Lam String LExpr   -- Lambda abstraction 
    deriving (Eq, Show)  

I am trying to build the accompanying fold function. I am acquainted with the general fold form for algebraic data types, which can be in such way present:

foldr :: (α -> β-> β) -> β -> [α] -> β
foldr (#) z = go
  where
    go []     = z
    go (x:xs) = x # go xs 

So, what I have done so far:

lfold :: (String -> a) -> (a -> a -> a) -> (String -> a -> a) -> LExpr -> a   --given by definition
lfold f z = go
  where
    go (Var _) = z            --Not sure here how to do the base case
    go (Lam v e) = v f go e

Is this the correct way? If not, where I am wrong and how to fix it?

Answer 1

I will only provide a hint.

Suppose you have a list of integers type as follows:

data List = Nil | Cons Int List

Then, the fold becomes

foldr :: β -> (α -> β -> β) -> [α] -> β
foldr nil cons = go
  where
    go Nil         = nil
    go (Cons x xs) = cons x (go xs)

Notice that, once I carefully name the arguments nil, cons then it's just a matter of 1) mapping Nil (constructor) to nil (parameter), 2) mapping Cons to cons, 3) applying go to subterms of type List (i.e., xs).

For your type,

data LExpr
    = Var String         -- variable
    | App LExpr LExpr    -- function application
    | Lam String LExpr   -- Lambda abstraction 

we can use the same trick:

lfold :: (String -> a) -> (a -> a -> a) -> (String -> a -> a) -> LExpr -> a   
lfold var app lam = go
  where
    go (Var v)     = ??
    go (App e1 e2) = ??
    go (Lam v e)   = ??

Notice how I named the three arguments: var, app, lam. By checking what happened in the List type above, you should now be able to fill in the blanks.