3

我有一棵树：

a :: Tree Double
a = 
    Node 1 
       [Node 20 
           [Node 300 
               [Node 400 [], 
               Node 500 []], 
           Node 310 []], 
       Node 30 [], 
       Node 40 []]

我想对它应用一个scan类似于列表的操作——除了返回一个列表，它应该返回一个带有行进路径的树。例如：

scan (+) 0 a

应减少为：

Node 1 
    [Node 21 
        [Node 321 
            [Node 721 [], 
            Node 821 []], 
        Node 331 []], 
    Node 31 [], 
    Node 41 []]

通过树累加总和。这有标准功能吗？

4

3 回答 3

3

没有标准库函数可以做到这一点。在列表的情况下：Haskell 几乎有你能想到的任何函数Data.List，但Data.Tree实际上非常稀疏。

幸运的是，您想要的功能非常简单。

scan f ~(Node r l) = Node r $ map (fmap (f r) . scan f) l

- 编辑 -

上述函数有一个问题：在 OP 给出的示例中，它将“721”计算为“1 + (20 + (400 + 300))”，这会阻止“1 + 20”计算在其他分支。

下面的函数没有这个问题，但我将原始函数留在原处，因为它仍然有用，具体取决于作为第一个参数传递的函数。

scan f ~(Node r l) = Node r $ map (scan' r) l where
  scan' a ~(Node n b) = let a' = f a n in Node a' $ map (scan' r) b
于 2015-01-04T10:43:05.597 回答
2

update: this produces different results than requested; but it shows a valuable general approach that can be helpful where applicable, and is helpful here as well, as a counterpoint.

It is entirely possible to do this sort of traversal generically using base and GHC. The class you are looking for is Traversable and the mapAccum{R,L} functions along with fst or snd:

Lets avoid writing our own instances:

{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveFunctor #-}

Now we can derive the necessary parts:

import Data.Traversable
import Data.Foldable

data Tree a = Node a [Tree a]
            deriving (Functor, Traversable, Foldable, Show)

Then the use is quite easy. If you don't want the final accumulator then just use snd.

main :: IO ()
main = print $ mapAccumL (\acc e -> (acc+e,acc+e)) 0 demo

demo :: Tree Int
demo =
   Node 1 [Node 20.
            [Node 300 [Node 400 []
                      , Node 500 []]
            , Node 310 []
            ]
          , Node 30 [], Node 40 []
          ]
于 2015-01-05T00:00:53.493 回答
2

如果你想传递一个累加器，那么定义是

scan f a (Node x ns) = Node a' $ map (scan f a') ns where a' = f a x

这个版本也比较高效，比较this和this。

于 2015-01-04T18:22:17.703 回答