Haskell - 树中的总和值

Question

我的树看起来像这样,一棵树在每个节点都可以有或没有整数:

data Tree = Empty | Node (Maybe Integer) Tree Tree deriving Show

我想总结树中的所有值,不包括Nothing值,如果tree不为空但只有Nothing值,只返回Nothing,或者空树为0.这些情况我理解如何.

我想深入思考第一次遍历是最好的,或者只是一般的基本遍历,但是如何优雅地实现它.

treeValues ::树 - >可能是整数

Answer 1

你可以让你的树成为一个Foldable实例,你可以免费获得许多功能,包括sum:

sum ::(可折叠t,Num a)=> ta - > a Source

sum函数计算结构数量的总和.

但是你需要制作Tree一个参数类型:

data Tree a = Empty | Node (Maybe a) Tree Tree

此外,使用GHC 7.10,几乎所有Prelude函数都将使用Foldable和Traversable类型而不是列表,然后如果实现这些类型类,则可以自由地为树使用它们.

Answer 2

您已经知道如何对列表求和,因此您可以先将树转换为列表:

> toList :: Tree -> [Integer]
> toList Empty        = []
> toList (Node a l r) = maybeToList a ++ toList l ++ toList r
>   where maybeToList (Just x) = [x]
>         maybeToList Nothing  = []

现在,您希望在空树(Empty)和仅包含的树之间有所不同Nothing.由于toList过滤了所有Nothing值,因此归结为

> sumTree :: Tree -> Maybe Integer
> sumTree Empty = Just 0
> sumTree tree  = case toList tree of
>                  [] -> Nothing      -- all values in the tree are Nothing
>                  xs -> Just $ sum xs       -- some were Just x

但等等,还有更多!

sumTree还不是很好.如果我们想要计算a的乘积Tree怎么办？嗯.好吧,我们可以拿一棵树,把它变成一个列表,并使用......折叠功能!

> type I = Integer -- otherwise the lines get ridiculously long
>
> foldrTree' :: (I -> I -> I) -> I -> Tree -> Maybe I
> foldrTree' _ init Empty = init
> foldrTree' f init tree  = case toList tree of
>                            [] -> Nothing
>                            xs -> Just $ foldr f init xs
> --                                      ^^^^^

现在我们可以接受任何(Integer -> Integer -> Integer)并产生单个值,只要我们的操作是关联的:

> productTree :: Tree -> Maybe Integer
> productTree = foldrTree' (*) 1
>
> sumTree' :: Tree -> Maybe Integer
> sumTree' = foldrTree' (+) 0