"tree traversal" 将节点组合到根节点究竟是什么抽象？

Question

Data.Tree 有一个 Tree a 数据类型，基本上是：

Tree a = Tree a [Tree a]

（不完全是，但这是基本思想）

这个结构（几乎）看起来非常适合文件系统样式树。

假设我有这个结构，我想创建一个类型的函数：

f :: Tree a -> [a]

它基本上执行以下操作：

f (Tree "a" [Tree "b" [], Tree "c" [Tree "d" []]] 
  == ["a", "ab", "ac", "acd"]

现在我不是在问如何编写代码，这确实很简单。但是数据类型Tree是Foldable、Traversable、Monad等的实例

我可以在折叠、贴图等方面实现 f 吗？或者还有其他一些抽象 f 也很相似吗？如果有帮助，我很高兴您假设 a 是 Monoid。

Answer 1

在抽象方面，如果将树类型概括为任何 可折叠容器（不仅仅是列表）， concatMap, Monoid, Foldable 将适用：

import Prelude hiding (concatMap)
import Control.Applicative ((<$>))
import Data.Foldable (Foldable, concatMap)
import Data.Monoid (Monoid, mappend, mconcat)

data Tree a f = Tree a (f (Tree a f))

flatten :: (Monoid a, Foldable t) => Tree a t -> [a]
flatten (Tree r tr) = r: (mappend r <$> concatMap flatten tr)

然后

\> let tr = Tree "a" [Tree "b" [], Tree "c" [Tree "d" []]]
\> flatten tr
["a","ab","ac","acd"]

"tree traversal" 将节点组合到根节点究竟是什么抽象？

What abstraction exactly is a "tree traversal" combining nodes to the root?

tree

haskell