计算树中叶子的数量

Question

使用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

但是我得到了一些奇怪的错误.有没有人对什么是错的有任何见解？

Answer 1

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

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折叠.即

countL'' = mytFold f a

在这里你必须做决定什么f和a是(提示:你已经有了f == leafy == const (+)).考虑mytFold leafy a Leaf.