1

使用 Haskell，我正在编写一个计算树中叶子总数的函数。我已经将树定义为：

data Tree a = Leaf | Node a (Tree a) (Tree a)

我编写了一个通过以下方式执行此操作的函数：

countL :: Tree a -> Int
countL Leaf = 1
countL (Node x tL tR) = (countL tL) + (countL tR)

这可行，但我想通过使用 fold 函数做同样的事情来更进一步。我通过以下方式定义的树有一个工作折叠功能：

mytFold :: (a -> b -> b -> b) -> b -> Tree a -> b
mytFold f g Leaf = g
mytFold f g (Node a xl xr) = f a (mytFold f g xl) (mytFold f g xr)

我试图包含 fold 函数（也使用了我通过这样做定义的辅助函数：

countL' :: Tree a -> Integer
countL' Leaf = 1
countL' = mytFold leafy 0 where
        leafy tL tR = tL + tR

但是我遇到了一些奇怪的错误。有人对出了什么问题有任何见解吗？

4

1 回答 1

5

有两个句法/类型问题。首先，每个顶级绑定必须有相同数量的参数，所以

countL' Leaf = ..
countL' = ..

无效。一种解决方案是

countL' Leaf = ..
countL' tree = mytFold leafy 0 tree

完成此操作后，GHC 会给您一个错误，例如

    Couldn't match expected type `Integer -> Integer'
                with actual type `Integer'
    Expected type: Integer -> Integer -> Integer -> Integer
      Actual type: Integer -> Integer -> Integer
    In the first argument of `mytFold', namely `leafy'
    In the expression: mytFold leafy 0 tree

这是因为mytFold需要一个 3 参数函数作为它的第一个参数，并且leafy只需要 2。通过使用leafy _ tL tR = tL + tR.

但是，一旦你这样做了，你会发现这给出了错误的答案：countL' (Node 1 Leaf Leaf) == 0. 一种可能使解决方案清晰的方法是删除countL' Leaf案例，并尝试将其写入countL折叠。IE

countL'' = mytFold f a

你在哪里决定什么f和a是（提示：你已经有f == leafy == const (+)）。考虑mytFold leafy a Leaf。

于 2012-10-19T18:34:22.317 回答