Haskell 中布尔 AST 的遍历

Question

我在完成一项任务时遇到了问题，我要创建一个使用广义折叠函数来计算布尔 AST 的函数。我将向您展示一些示例来说明。

首先，我想要一个示例，但是对于求和整数的 AST：

data Expr = Val Int | Add Expr Expr deriving Show

folde :: (Int -> a) -> (a -> a -> a) -> Expr -> a
folde f g (Val x)   = f x
folde f g (Add x y) = g (folde f g x) (folde f g y)

eval :: Expr -> Int
eval expr = folde (\x -> x) (\x y -> x + y) expr

这很好用。

现在是布尔 AST 和折叠函数：

data Bexp = T | F | And Bexp Bexp | Or Bexp Bexp deriving (Ord, Eq)

foldb :: a -> a -> (a -> a -> a) -> (a -> a -> a) -> Bexp -> a
foldb t f a o T         = t
foldb t f a o F         = f 
foldb t f a o (And x y) = a (foldb t f a o x) (foldb t f a o y)  
foldb t f a o (Or x y)  = o (foldb t f a o x) (foldb t f a o y)

我遇到的问题是创建一个函数，它与上面简单 AST 的 eval 函数的作用相同，也就是说，使用带有一些 lambda 的 foldb 函数来评估 Bexp表达式是 T 或 F。

我不明白为什么这个功能不起作用：

evb :: Bexp -> Bool
evb bexp = foldb (\_ -> True) (\_ -> False) (\x y -> x == T && y == T) (\x y -> x == T || y == T) bexp

GHCi 因为类型错误甚至不想编译它。

提前致谢。

Answer 1

由于某些原因，代码无法编译。

-- Observe type signatures.
foldb :: a -> a -> (a -> a -> a) -> (a -> a -> a) -> Bexp -> a
evb bexp = foldb (\_ -> True) (\_ -> False) (\x y -> x == T && y == T) (\x y -> x == T || y == T) bexp

如果 foldb 将它的第一个参数作为函数 x -> Bool 那么从 foldb 的类型签名来看 a 是函数类型但是观察这个 (\x y -> x == T && y == T) 这里你用 a 作为 Bexp，根本不匹配。

a = Bexp 来自 (\x y -> x == T && y == T)

a = x -> Bool 来自 (\_ -> True)

而且 evb 的 return 类型是 Bool，但是从你传递给 foldb a 的参数可以是两件事和编译器为选择正确的类型而感到困惑。

Answer 2

如果我们想在最后使用foldb产生一个Bool，我们需要在其类型中选择a = Bool。所以，我们现在使用

foldb :: Bool 
      -> Bool
      -> (Bool -> Bool -> Bool)
      -> (Bool -> Bool -> Bool)
      -> Bexp
      -> Bool

因此，foldb (\_->True) (\_->False) ... 是错误的，因为前两个参数必须是布尔值，而不是函数。我们需要像 foldb True False ... 这样的东西。接下来的两个参数必须是布尔二元运算符，如\x y -> x && y，可以简写为(&&)。

我们终于得到：

evb :: Bexp -> Bool
evb bexp = foldb True False (&&) (||)

Haskell 中布尔 AST 的遍历

traversal of boolean AST in Haskell

haskell

abstract-syntax-tree