add a catamorphism on Trees
authorDaniel Wagner <me@dmwit.com>
Tue, 17 May 2016 17:21:07 +0000 (10:21 -0700)
committerDaniel Wagner <me@dmwit.com>
Tue, 17 May 2016 17:21:07 +0000 (10:21 -0700)
Data/Tree.hs

index 4cd05a5..c35d0ed 100644 (file)
@@ -30,7 +30,7 @@ module Data.Tree(
     -- * Two-dimensional drawing
     drawTree, drawForest,
     -- * Extraction
-    flatten, levels,
+    flatten, levels, foldTree,
     -- * Building trees
     unfoldTree, unfoldForest,
     unfoldTreeM, unfoldForestM,
@@ -156,6 +156,11 @@ levels t =
         takeWhile (not . null) $
         iterate (concatMap subForest) [t]
 
+-- | Catamorphism on trees.
+foldTree :: (a -> [b] -> b) -> Tree a -> b
+foldTree f = go where
+    go (Node x ts) = f x (map go ts)
+
 -- | Build a tree from a seed value
 unfoldTree :: (b -> (a, [b])) -> b -> Tree a
 unfoldTree f b = let (a, bs) = f b in Node a (unfoldForest f bs)