Haskell 数据声明：查找二叉树中叶子的总和

Question

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

数据声明已给出

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.I 认为问题是程序无法计数，当有节点时有两片叶子，但我不知道如何解决 it.A 非常感谢您的帮助。

已编辑：测试 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]) 在 programm.How 中工作，我可以克服它吗？

Answer 1

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

sumLeaves :: Tree -> Int
sumLeaves (Tleaf x) = x
sumLeaves (TNode x <b>trees</b>) = sum (…)

此处 … 应创建节点子节点总和的列表。因此，您应该为 trees 中的每个元素创建一个映射。我把它留作练习。你可能想看看 map :: (a -> b) -> [a] -> [b].

也就是说，您不必自己对元素求和。您可以提升 Tree 数据类型并利用 DeriveFoldable extension 让 Haskell 为您派生一个 Foldable 实例：

{-# LANGUAGE <b>DeriveFoldable</b> #-}

data Tree <b>a</b> = TNode <b>a</b> [ Tree <b>a</b> ] | TLeaf <b>a</b> <b>deriving Foldable</b>

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

Haskell 数据声明：查找二叉树中叶子的总和

Haskell Data Declaration : Find sum of Leaves in a binary Tree

haskell

binary-tree

non-exhaustive-patterns