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

Question

Data.Tree has a Tree a data type which is basically as:

Tree a = Tree a [Tree a]

(not exactly but that's the basic idea)

This structure (almost) looks very nice for a filesystem style tree.

Lets say I've got this structure, and I want to make a function of type:

f :: Tree a -> [a]

Which basically does the following:

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

now I'm not asking how to code this up, indeed it's fairly trivial to do. But the data type Tree is an instance of Foldable, Traversable, Monad, etc.

Could I implement f in terms of folds, maps, etc? Or is there some other abstraction that f is similar too? I'm happy for you to assume that a is a Monoid if that helps.

Answer 1

In terms of abstractions, if you generalize the tree type to any foldable container (not just lists), concatMap, Monoid, Foldable would apply:

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)

then

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