string - Haskell Lambda 折叠

Question

我有以下代表 Haskell 中的 Lambda 演算的代数数据类型:

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

我正在尝试构建附带的折叠功能。我熟悉代数数据类型的一般折叠形式，它可以以这种方式呈现:

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

那么，到目前为止我所做的:

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

这是正确的方法吗？如果不是，我错在哪里以及如何解决？

Answer 1

我只会提供一个提示。

假设您有一个整数类型列表，如下所示:

data List = Nil | Cons Int List

然后，折叠变成

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

请注意，一旦我仔细命名参数 nil, cons，那么只需 1) 将 Nil (构造函数)映射到 nil > (参数)，2) 将 Cons 映射到 cons，3) 将 go 应用于 List 类型的子项 (即，xs)。

对于您的类型，

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

我们可以使用同样的技巧:

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)   = ??

请注意我如何命名这三个参数:var、app、lam。通过检查上面的 List 类型中发生的情况，您现在应该能够填写空白。