Haskell:函数折叠:无法匹配预期类型 `a' 与实际类型 `Expr'

Question

我有一个数据类型data Expr = Val Int | Add Expr Expr
我必须定义一个类型为“folde”的函数folde :: (Int -> a) -> (a -> a -> a) -> Expr -> a这样折叠 f g 用函数 f 替换表达式中的每个 Val 构造函数，用函数 g 替换每个 Add 构造函数

我写过这样的代码:

data Expr = Val Int | Add Expr Expr

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

但我收到了错误

 Couldn't match expected type `a' with actual type `Expr'
      `a' is a rigid type variable bound by
        the type signature for:
          folde :: forall a. (Int -> a) -> (a -> a -> a) -> Expr -> a
        at C:\code\haskell\types.hs:51:1-49
    * In the first argument of `g', namely `z'
      In the expression: g z x
      In an equation for `folde': folde f g (Add z x) = g z x
    * Relevant bindings include
        g :: a -> a -> a (bound at C:\code\haskell\types.hs:53:9)
        f :: Int -> a (bound at C:\code\haskell\types.hs:53:7)
        folde :: (Int -> a) -> (a -> a -> a) -> Expr -> a

你能澄清错误在哪里吗？提前致谢。

Answer 1

你在这里有第二个条款:

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

基于数据构造器， Add有两个 Expr s。所以这意味着 z和 x有类型 x, z :: Expr .您因此无法调用 g z x , 自 g有类型 g :: a -> a -> a .

您需要做的是对这两个项目执行递归，例如:

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

或使用辅助功能:

folde :: (Int -> a) -> (a -> a -> a) -> Expr -> a
folde f g = go
    where go (Val n) = f n
          go (Add z x) = g (go z) (go x)