string - Haskell Lambda fold -

i have following algebraic data type representing lambda calculus in haskell:

data lexpr     = var string         -- variable     | app lexpr lexpr    -- function application     | lam string lexpr   -- lambda abstraction      deriving (eq, show)   

i trying build accompanying fold function. acquainted general fold form algebraic data types, can in such way present:

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

so, have done far:

lfold :: (string -> a) -> (a -> -> a) -> (string -> -> a) -> lexpr ->   --given definition lfold f z = go       go (var _) = z            --not sure here how base case     go (lam v e) = v f go e 

is correct way? if not, wrong , how fix it?

i provide hint.

suppose have list of integers type follows:

data list = nil | cons int list 

then, fold becomes

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

notice that, once name arguments nil, cons it's matter of 1) mapping nil (constructor) nil (parameter), 2) mapping cons cons, 3) applying go subterms of type list (i.e., xs).

for type,

data lexpr     = var string         -- variable     | app lexpr lexpr    -- function application     | lam string lexpr   -- lambda abstraction  

we can use same trick:

lfold :: (string -> a) -> (a -> -> a) -> (string -> -> a) -> lexpr ->    lfold var app lam = go       go (var v)     = ??     go (app e1 e2) = ??     go (lam v e)   = ?? 

notice how named 3 arguments: var, app, lam. checking happened in list type above, should able fill in blanks.