为表达式树实现变形

Question

我正尝试在 Haskell 中实现一个表达式树，如下所示：

data ExprTr a b = 
                 Variable a 
                | Constant b 
                | Add (ExprTr a b) (ExprTr a b) 
                | Mul (ExprTr a b) (ExprTr a b)
                deriving (Eq, Show)

而且我希望能够使用变形对它执行操作。

目前我得到的功能是这样的：

cataTr f _ _ _ (Variable i) = f i
cataTr f g _ _ (Constant i) = g i
cataTr f g h i (Add e1 e2) = g (cataTr f g h i e1) (cataTr f g h i e2)
cataTr f g h i (Mul e1 e2) = h (cataTr f g h i e1) (cataTr f g h i e2)

但是，每当我尝试将它与 ExprTr String Integer 类型的表达式一起使用时，我都会遇到编译器错误。例如运行cataTr id id id id (Var "X")returns下面的编译错误而不是(Var "X").

Couldn't match type 'Integer' with '[Char]'
    Expected type: 'ExprTr String String'
    Actual type: 'ExprTr String Integer'

我不确定如何进行。此外，我将不胜感激关于如何键入诸如 cataTr 之类的函数的一些建议，以便以后更容易调试。

由于我是 Haskell 的新手，我想了解如何从 'first principles' 开始处理这种情况，而不是使用库为自己生成变形。

Answer 1

这是预期的行为。

我猜你在问题中打错了字，因为你应该使用 h 和 i 作为函数：

cataTr f _ _ _ (Variable i) = f i
cataTr f g _ _ (Constant i) = g i
cataTr f g h i (Add e1 e2) = <b>h</b> (cataTr f g h i e1) (cataTr f g h i e2)
cataTr f g h i (Mul e1 e2) = <b>i</b> (cataTr f g h i e1) (cataTr f g h i e2)

或者可能更优雅：

cataTr f g h i = go
    where go (Variable i) = f i
          go (Constant i) = g i
          go (Add e1 e2) = h (go e1) (go e2)
          go (Mul e1 e2) = i (go e1) (go e2)

或，带有 case 表达式：

cataTr f g h i = go
    where go v = case v of
              Variable i -> f i
              Constant i -> g i
              Add e1 e2 -> h (go e1) (go e2)
              Mul e1 e2 -> i (go e1) (go e2)

但是，您不能调用函数cataTr 将id 作为第三和第四个参数。这些函数需要两个参数。此外，如果 a 和 b 不同，则前两个参数不能都是 id，因为您的 f 将 a 映射到结果类型，并且g 将 b 映射到结果类型。

例如，您可以通过数据构造函数来构造一个恒等函数：

cataTr <b>Variable</b> <b>Constant</b> <b>Add</b> <b>Mul</b> (Variable "X")

这将因此再次产生 Variable "X"，或者您可以使用 const 0 将所有 Variable 映射到 0，然后使用 id， (+) 和 (*) 计算表达式：

cataTr (const 0) id (+) (*) (Variable "X")

为表达式树实现变形

Implementing a catamorphism for Expression Trees

haskell

catamorphism