0

我正在尝试在 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")返回以下编译器错误，而不是(Var "X").

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

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

由于我对 Haskell 还很陌生，我想了解如何从“第一原则”处理这种情况，而不是使用库为自己生成 catamorphism。

4

1 回答 1

3

这是预期的行为。

我猜你在这个问题中打错了，因为你应该使用handi作为函数：

cataTr f _ _ _ (Variable i) = f i
cataTr f g _ _ (Constant i) = g i
cataTr f g h i (Add e1 e2) = h (cataTr f g h i e1) (cataTr f g h i e2)
cataTr f g h i (Mul e1 e2) = i (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)

或者正如@DanielWagner 建议的那样，用一个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将 an 映射a到结果类型，而g将 a 映射b到结果类型。

例如，您可以传递数据构造函数来构造一个标识函数：

cataTr Variable Constant Add Mul (Variable "X")

这将因此Variable "X"再次产生，或者您可以例如将所有Variables 映射到0with const 0，并使用id, (+)and(*)来评估表达式：

cataTr (const 0) id (+) (*) (Variable "X")
于 2020-10-02T22:11:40.490 回答