Haskell数据声明:在二叉树中查找叶的和

Question

这是一个二叉树，我正在尝试计算叶的总和

-1
/   
-5     10
/    
-4  30  
/ 
13  17

给出了数据声明。

data Tree = TNode Int [ Tree ] | TLeaf Int 

这是我的代码

let t = TNode (-1) [TNode (-5)  [  TNode (-4) [ Tleaf 13, Tleaf 17] ,  Tleaf 30 ] ,Tleaf 10 ]
sumLeaves (Tleaf x)= x
sumLeaves (TNode x [tree])=  sum[sumLeaves tree]

当我运行程序sumLeaves t时，它表明函数sumLeaves中存在非穷举模式。我认为问题是程序无法计数，当有一个节点有两个叶子时，但我不知道如何解决它。非常感谢您的帮助。

编辑时间：测试1:

sumLeaves1 (Tleaf x)= [x]
sumLeaves1 (TNode x [Tleaf y])=[y]
sumLeaves1 (TNode x (y:ys))= sum ( (sumLeaves1 y) ++ (sumLeaves1 (TNode x ys)) )

测试2:

sumLeaves (Tleaf x)= x
sumLeaves (TNode x [Tleaf y])=y
sumLeaves (TNode x (y:ys))= (sumLeaves y) + sumLeaves (TNode x ys)

测试2运行良好，但测试1给出错误，当我删除sum((时，它给出了一个列表[13,17,30,10]，这是正确的列表，但>sum([13,17,30,10](在程序中起作用。我该如何克服它？

Answer 1

只有当节点恰好有一个子树时，(Tnode x [tree])才匹配。您应该匹配sublistlist的任何值，因此：

sumLeaves :: Tree -> Int
sumLeaves (Tleaf x) = x
sumLeaves (TNode xtrees) = sum (…)

这里CCD_ 2应该创建节点的子节点的和的列表。因此，您应该为trees中的每个元素制作一个映射。我把这个留作练习。您可能需要查看map :: (a -> b) -> [a] -> [b]。

话虽如此，你不必自己对这些元素求和。您可以提升Tree数据类型，并使用DeriveFoldable扩展让Haskell为您派生一个Foldable实例：

{-# LANGUAGEDeriveFoldable#-}
data Treea= TNodea[ Treea] | TLeafaderiving Foldable

sum :: (Foldable f, Num a) => f a -> a定义在任何Foldable上，因此我们可以用求和

Prelude> sum (TNode (-1) [TNode (-5)  [  TNode (-4) [ TLeaf 13, TLeaf 17] ,  TLeaf 30 ] ,TLeaf 10 ])
60