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 类型中发生的情况，您现在应该能够填写空白。

Haskell Lambda 折叠

Haskell Lambda fold

string

lambda

haskell

fold

algebraic-data-types