A newtype over Tree that folds and traverses in post-order.
Foldable examples
>>> import Data.Foldable (toList)
>>> toList $ PostOrder $ Node 1 [Node 2 [Node 3 [], Node 4 []], Node 5 []]
[3,4,2,5,1]
foldr produces elements incrementally, inspecting the structure of the
Tree just as much as necessary.
>>> take 3 $ foldr (:) [] $ PostOrder $ Node 1 ([Node 2 [Node 3 [], Node 4 []]] ++ undefined)
[3,4,2]
foldl also produces elements incrementally.
>>> foldl (flip (:)) [] $ PostOrder $ Node 1 [Node 2 [Node 3 [], Node 4 []], Node 5 []]
[1,5,2,4,3]
>>> take 4 $ foldl (flip (:)) [] $ PostOrder $ Node 1 [Node 2 [undefined, Node 4 []], Node 5 []]
[1,5,2,4]
PostOrder :: Tree a -> PostOrder a
unPostOrder :: PostOrder a -> Tree a
unfoldTree :: (b -> (a, [b])) -> b -> Tree a
Build a (possibly infinite) tree from a seed value.
unfoldTree f b constructs a tree by starting with the tree
Node { rootLabel=b, subForest=[] } and repeatedly applying f to each
rootLabel value in the tree's leaves to generate its subForest.
For a monadic version, see unfoldTreeM (depth-first) and
unfoldTreeM_BF (breadth-first).
Examples
Construct the tree of Integers where each node has two children:
left = 2*x and right = 2*x + 1, where x is the rootLabel of the node.
Stop when the values exceed 7.
let buildNode x = if 2*x + 1 > 7 then (x, []) else (x, [2*x, 2*x+1])
putStr $ drawTree $ fmap show $ unfoldTree buildNode 1
1
|
+- 2
| |
| +- 4
| |
| `- 5
|
`- 3
|
+- 6
|
`- 7
unfoldTreeM_BF :: Monad m => (b -> m (a, [b])) -> b -> m (Tree a)
Monadic tree builder, in breadth-first order.
See unfoldTree for more info.
Implemented using an algorithm adapted from
Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design,
by Chris Okasaki, ICFP'00.
unfoldForestM_BF :: Monad m => (b -> m (a, [b])) -> [b] -> m ([Tree a])
Monadic forest builder, in breadth-first order.
See unfoldForest for more info.
Implemented using an algorithm adapted from
Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design,
by Chris Okasaki, ICFP'00.
foldTree :: (a -> [b] -> b) -> Tree a -> b
Fold a tree into a "summary" value.
For each node in the tree, apply f to the rootLabel and the result
of applying f to each subForest.
This is also known as the catamorphism on trees.
Examples
Sum the values in a tree:
foldTree (\x xs -> sum (x:xs)) (Node 1 [Node 2 [], Node 3 []]) == 6
Find the maximum value in the tree:
foldTree (\x xs -> maximum (x:xs)) (Node 1 [Node 2 [], Node 3 []]) == 3
Count the number of leaves in the tree:
foldTree (\_ xs -> if null xs then 1 else sum xs) (Node 1 [Node 2 [], Node 3 []]) == 2
Find depth of the tree; i.e. the number of branches from the root of the tree to the furthest leaf:
foldTree (\_ xs -> if null xs then 0 else 1 + maximum xs) (Node 1 [Node 2 [], Node 3 []]) == 1
You can even implement traverse using foldTree:
traverse' f = foldTree (\x xs -> liftA2 Node (f x) (sequenceA xs))
levels :: Tree a -> [[a]]
Returns the list of nodes at each level of the tree.
a
/ \\ => [[a], [b,c]]
b c
Examples
levels (Node 1 [Node 2 [], Node 3 []]) == [[1],[2,3]]
leaves :: Tree a -> [a]
O(n). The leaves of the tree in left-to-right order.
A leaf is a node with no children.
Examples
>>> :{
leaves $
Node 1
[ Node 2
[ Node 4 []
, Node 5 []
]
, Node 3
[ Node 6 []
]
]
:}
[4,5,6]
>>> leaves (Node "root" [])
["root"]
edges :: Tree a -> [(a, a)]
O(n). The edges of the tree as parent-child pairs in pre-order.
A tree with n nodes has n-1 edges.
Examples
>>> :{
edges $
Node 1
[ Node 2
[ Node 4 []
, Node 5 []
]
, Node 3
[ Node 6 []
]
]
:}
[(1,2),(2,4),(2,5),(1,3),(3,6)]
>>> edges (Node "root" [])
[]
pathsToRoot :: Tree a -> Tree (NonEmpty a)
O(n). Labels on the paths from each node to the root.
Examples
>>> :{
pathsToRoot $
Node 1
[ Node 2 []
, Node 3 []
]
:}
Node {rootLabel = 1 :| [], subForest = [Node {rootLabel = 2 :| [1], subForest = []},Node {rootLabel = 3 :| [1], subForest = []}]}
>>> pathsToRoot (Node "root" [])
Node {rootLabel = "root" :| [], subForest = []}
pathsFromRoot :: Tree a -> Tree (NonEmpty a)
Labels on the paths from the root to each node.
If the path orientation is not important, consider using pathsToRoot
instead because it is more efficient.
Examples
>>> :{
pathsFromRoot $
Node 1
[ Node 2 []
, Node 3 []
]
:}
Node {rootLabel = 1 :| [], subForest = [Node {rootLabel = 1 :| [2], subForest = []},Node {rootLabel = 1 :| [3], subForest = []}]}
>>> pathsFromRoot (Node "root" [])
Node {rootLabel = "root" :| [], subForest = []}