在 Haskell 中，是否有一个标准函数可以对树执行“scan”操作？

Question

我有一棵树：

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

我希望将一个类似于列表的“扫描”操作应用到它上面，但是与返回列表不同的是，它应该返回一棵遍历路径的树。例如：

scan (+) 0 a

请将其简化为:

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

通过树来累计求和，是否有标准函数可用？

- MaiaVictor

Answer 1

没有标准库函数可以做到这一点。对于列表：Haskell已经在中拥有你能想到的任何函数，但实际上相当稀少。

幸运的是，你所需要的函数非常简单。

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 

- Jeremy List

---

实际上，使用Traversable类和一些辅助函数，您可以仅使用标准库函数通用地完成此任务。 - Thomas M. DuBuisson

我知道Traversable，但它似乎没有一个执行这个特定任务的函数。 - Jeremy List

没有展示Functor实例，如果它能够完成预期的功能，这将意味着整个子树的重复重新进入和重新扫描（二次行为）。 - Will Ness

我的错误，我误解了目标。 - Thomas M. DuBuisson

对于 f = (+)，这意味着函数链被应用于每个节点，例如对于最左下角的节点，(+1) . (+20) . (+300) $ 400。我不希望编译器将其转换为 (+321) $ 400，这将使其成为线性，并且如果它确实执行了，那将是非常好的。（如果您愿意添加一条说明，我可以删除我的投票反对 - 或者我可以自己添加，如果您允许...） - Will Ness

Answer 2

如果您想传递一个累加器，那么定义如下：

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

这个版本也更加高效，与这个和那个进行比较。

- effectfully

---

@Will Ness，Tree数据类型只有一个构造函数，所以我已经自动放置了它。但是，无论如何，map都会强制使用ns。已修复，谢谢。此外。 - effectfully

嗯，但它没有强制执行 x，因此 treeHead $ scan const "pointless" undefined 返回 "pointless"。这确实是毫无意义的。 - effectfully

你的意思是，使用惰性模式 它返回 "pointless"。（只是为了澄清） - Will Ness

Answer 3

更新：这个结果与所请求的不同；但它展示了一种有价值的通用方法，可以在适用的情况下提供帮助，并且在这里也很有帮助，作为对比。

完全可以使用base和GHC来通用地执行这种遍历。你要找的类是Traversable，以及mapAccum{R,L}函数和fst或snd：

让我们避免编写自己的实例：

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

现在我们可以推导出必要的部分：

import Data.Traversable
import Data.Foldable

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

然后使用起来非常简单。如果您不想要最终的累加器，则只需使用 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 []
          ]

- Thomas M. DuBuisson

---

这种类型及其适当的实例在containers包中的Data.Tree中定义，该包随GHC一起提供。 - dfeuer

是的，但如果他正在使用自定义声明，则了解如何派生实例对他有益。问题省略了这一部分。 - Thomas M. DuBuisson

我认为这并没有解决问题。OP要求累积从根节点到每个节点的路径，而不是累积整个遍历过程。请将您的结果与他所要求的结果进行比较。 - Petr

确切地说，结果与我所要求的不同。不过，我从那个答案中学到了一些东西，所以感谢你发布它。 - MaiaVictor

啊，我明白了。我没听清楚。 - Thomas M. DuBuisson