haskell - 求叶子的总和

Question

我应该编写这样的代码

A polymorphic tree type with nodes of an arbitrary number of children might be represented as follows (note that the leaves store a list, and interior nodes store list of “ListTree”s):

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

Write a function foldListTree that takes a function (f), a base value (base), and a ListTree (t) and combines the values in the lists of the leaf notes in tree t by applying function f. (The leaves of the tree are scanned from left to right). foldListTree is invoked as:

foldListTree f base t where f is the combining function of type a->a->a. The type of foldListTree should be:

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

我正在尝试读取列表中的每个节点，但我猜它正在进入无限循环。

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


foldListTree :: (Num a) => (a -> a -> a) -> a -> ListTree a -> a 
foldListTree op base (ListLEAF []) = base
foldListTree op base (ListNODE []) = base
foldListTree op base (ListLEAF [a]) = foldr op base [a]
foldListTree op base (ListNODE b) = (op (foldListTree op base x) 
                                        (foldListTree op base (ListNODE xs)))
                                        where x:xs = b

t4 = ListNODE
       [ ListNODE
           [ ListLEAF [1,2,3]
           , ListLEAF [4,5]
           , ListNODE [ListLEAF [6], ListLEAF []]
           ]
       , ListNODE []
       , ListLEAF [7,8]
       , ListNODE [ListLEAF [], ListLEAF []]
       ]

命令:foldListTree (+) 0 t4

> Error : *** Exception: indi.hs:(86,1)-(90,54): Non-exhaustive patterns in function foldListTree

Answer 1

如果您打开-Wall，这真的很有帮助。因为 Haskell 可以为您提供您未涵盖的模式的列表。

主要问题是你写成模式:

foldListTree op base (ListLEAF <b>[a]</b>) = foldr op base [a]

这意味着您将模式限制为单例列表。代码中没有任何地方存在 ListLEAF 构造函数的模式，该构造函数采用具有任意数量元素的列表。

但是，您可以通过实现两种情况使上述过程变得简单得多:每个构造函数一个。在 ListNODE 情况下，我们可以使用 foldListTree 作为折叠函数:

foldListTree :: Num a => (a -> a -> a) -> a -> ListTree a -> a 
foldListTree op base (ListLEAF x) = foldr op base x
foldListTree op base (ListNODE b) = foldr (flip (foldListTree op)) base b

这给了我们:

Prelude> foldListTree (+) 0 t4
36

Note: Although strictly speaking not wrong, I find it odd to write LEAF and NODE in all caps, usually one writes this in camelcase, so ListLeaf and ListNode.

 

Note: It might be better that your ListLeaf stores an a, not an [a], since then you give more freedom what to store in your leaves. It does not exclude the possibility at all to store lists in the leaves, but you leave that decision to the user of the data type.