haskell - Tree(Int,Int) 在 haskell 中是什么意思？

Question

我现在正在学习 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

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

我想获取的是每个节点的权值，并以元组的形式返回，单片叶子没有权值。

Answer 1

要修复即时错误，您需要向 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 的节点设置 (10,190)。这是下面所有内容的总和，但不包括当前项目。这意味着子树的总权重可以通过将其子树的权重添加到当前值来获得:

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)))

根据需要。