3

我现在正在学习 Haskell 中的数据结构。我看到了类似的东西：

  Tree(Int,Int)

这是否意味着树的元组？我正在尝试写类似的东西：

  data Tree a = Leaf a | Node (Tree a) a (Tree a) deriving (Eq,Show)

  weight :: (Tree Integer) -> Tree(Integer,Integer)

  weight (Node left leaf right) = Node (leaf, (sum left) + (sum right)) 
                          where 
                          sum (Leaf a) = 0
                          sum (Node left leaf right) = leaf + sum left + sum right

但我得到了无法匹配的错误。

我想要得到的是每个节点的权重并将其作为元组返回，而单个叶子没有权重。

4

1 回答 1

5

要修复即时错误，您需要向Node构造函数提供三个参数：

weight (Node left leaf right) = Node (weight left) 
                                     (leaf, (sum left) + (sum right)) 
                                     (weight right)
                          where 
                          sum (Leaf a) = 0
                          sum (Node left leaf right) = leaf + sum left + sum right

也许是一个基本案例

weight (Leaf a) = Leaf (a,0)

..但我不确定这是你的意图：

ghci> weight (Node (Leaf 100) 10 (Node (Leaf 20) 30 (Leaf 40)))
Node (Leaf (100,0)) (10,30) (Node (Leaf (20,0)) (30,0) (Leaf (40,0)))

叶子上的值被忽略，每对中的第二个元素是子树总数。

不那么频繁地求和

当你计算它们的权重时，对左右子树求和有很多重复。为什么不重用价值？

我们可以通过获取顶部对的第二个元素来读取子树的总和：

topsecond :: Tree (a,a) -> a
topsecond (Leaf (x,y)) = y
topsecond (Node _ (x,y) _) = y

所以让我们用它来得到总和

weigh (Leaf a) = Leaf (a,0)
weigh (Node left value right) = Node newleft (value,total) newright where
       newleft = weigh left
       newright = weigh right
       leftsum = topsecond newleft
       rightsum = topsecond newright
       total = leftsum + value + rightsum

加起来不一样

在您提到的评论中，我们应该(10,190)为节点标记 10。这是下面所有内容的总和，但不包括当前项目。这意味着可以通过将其子树的权重添加到当前值来获得子树的总权重：

addTopPair :: Num a => Tree (a,a) -> a  -- or Tree (Integer,Integer) -> Integer
addTopPair (Leaf (x,y)) = x+y
addTopPair (Node _ (x,y) _) = x+y

接着

weighUnder (Leaf a) = Leaf (a,0)
weighUnder (Node left value right) = Node newleft (value,total) newright where
       newleft = weighUnder left
       newright = weighUnder right
       leftsum = addTopPair newleft
       rightsum = addTopPair newright
       total = leftsum + rightsum

给予

ghci> weighUnder (Node (Leaf 100) 10 (Node (Leaf 20) 30 (Leaf 40)))
Node (Leaf (100,0)) (10,190) (Node (Leaf (20,0)) (30,60) (Leaf (40,0)))

和

ghci> > weighUnder $ Node (Node (Leaf (-8)) (-12) (Node (Leaf 9) 3 (Leaf 6))) 5 (Node (Leaf 2) 14 (Leaf(-2)))
Node (Node (Leaf (-8,0)) (-12,10) (Node (Leaf (9,0)) (3,15) (Leaf (6,0)))) (5,12) (Node (Leaf (2,0)) (14,0) (Leaf (-2,0)))

按要求。

于 2013-05-15T23:21:12.467 回答