Haskell

Question

我的树看起来像这样，一棵树的每个节点都可以有或不能有整数：

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

我想对树中的所有值求和，不包括 Nothing 值，如果树不为空但只有 Nothing 值，则 return Nothing，或者空树为 0。这些情况我理解如何。

我想考虑深度优先遍历是最好的，或者只是一般的一些基本遍历，但在如何优雅地实现它方面苦苦挣扎。

treeValues :: 树 -> 可能是整数

Answer 1

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

sum :: (Foldable t, Num a) => t a -> a Source

The sum function computes the sum of the numbers of a structure.

但您需要将 Tree 设为参数类型：

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

此外，对于 GHC 7.10，几乎所有 Prelude 函数都将使用 Foldable 和 Traversable 类型类而不是列表，然后如果您实现了这些类型类，您就可以将它们自由地用于您的树。

Answer 2

这里有一个提示：

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

reduce :: (a -> r -> r -> r) -> r -> Tree a -> r
reduce f z = go
    where
        go Empty        = z
        go (Node x l r) = f x (go l) (go r)

Answer 3

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

> 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 还不是很好。如果我们想计算 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

Answer 4

针对以上解决方案和意见加上lyah and Brent Yorgeys advice我整理了以下建议（在ghci中随意尝试）：

:set -XDeriveFoldable -XDeriveFunctor
:m + Data.Foldable Data.Monoid
data Tree a = Empty | Node (Maybe a) (Tree a) (Tree a) deriving (Show, Functor, Foldable)
let tree :: Tree Integer ; tree = Node Nothing (Node (Just 42) Empty Empty) (Node Nothing Empty Empty)
foldMap Sum tree

虽然 returns 仅 0 在这两种情况下仅给出 Nothing 值并且树是 Empty 但我希望它稍后能为像我这样的学习者提供提示。

Haskell - 树中的总和值

Haskell - Sum values in a tree

functional-programming

等等，还有更多！