树的折叠列表-hasekell

Question

我正在研究这个问题，感到很沮丧。问题被发布在下面的图片上：

https://i.stack.imgur.com/SeXpF.png

在将其标记为重复之前，已经有人回答了这个问题，但是他们更改了功能定义以使其回答起作用。我已经在这里发布了他们的解决方案：

Find Sum of leaves

我正在寻找一个实际上可以与问题本身中描述的函数定义一起使用的答案。

foldListTree :: (a -> a -> a) -> a -> ListTree a -> a

我已经尝试按照以下方式进行解决：

data ListTree a = ListLEAF [a] | ListNODE [(ListTree a)]
                  deriving (Show, Read, Eq)

foldListTree :: (a -> a -> a) -> a -> ListTree a -> a
foldListTree f base (ListLEAF a) = foldr f base a
foldListTree f base (ListNODE iL) = foldListTree f base (map f iL)

但是我得到一个错误：

Couldn't match expected type `ListTree a' with actual type `[a -> a]'

任何帮助将不胜感激，谢谢！

Answer 1

让我们看一下这行：

foldListTree f base (ListNODE iL) = foldListTree f base (map f iL)

您有以下可用值：

• foldListTree :: (a -> a -> a) -> a -> ListTree a -> a
• f :: a -> (a -> a)
• base :: a
• iL :: [ListTree a]

并且您需要居住在a。

让我们追踪您的表情类型：

• map :: forall c d. (c -> d) -> ([c] -> [d])
• [map f :: [a] -> [a -> a]，其中c实例化为a，d实例化为a -> a。

为了使表达式map f iL正确键入，iL应该具有类型[a]，但是它具有[ListTree a]类型。这是一种类型错误，但不是类型检查器报告的错误。

在代码foldListTree f base (map f iL)中，第三个参数的类型应为ListTree a。但是，map f iL的类型为[a -> a]。

您真正想要的是：

foldListTree f base (ListNODE iL) = foldr (flip $ foldListTree f) base iL

这是派生：

• foldListTree :: (a -> a -> a) -> a -> ListTree a -> a
• foldListTree f :: a -> ListTree a -> a
• flip $ foldListTree f :: ListTree a -> a -> a
• foldr :: forall t elem acc. Foldable t => (elem -> acc -> acc) -> acc -> t elem -> acc
• [foldr (flip $ foldListTree f) :: a -> [ListTree a] -> a其中t实例化为[]，elem实例化为ListTree a，并且acc实例化为a。
• foldr (flip $ foldListTree f) base :: [ListTree a] -> a
• foldr (flip $ foldListTree f) base iL :: a