Data.Tree

Non-empty, possibly infinite, multi-way trees; also known as rose trees.

This type synonym exists primarily for historical reasons.

A newtype over Tree that folds and traverses in post-order.

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

Build a (possibly infinite) forest from a list of seed values.

unfoldForest f seeds invokes unfoldTree on each seed value.

For a monadic version, see unfoldForestM (depth-first) and unfoldForestM_BF (breadth-first).

Monadic tree builder, in depth-first order.

Monadic forest builder, in depth-first order.

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.

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.

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))

Returns the elements of a tree in pre-order.

flatten == Data.Foldable.toList

  a
 / \    => [a,b,c]
b   c

Examples

flatten (Node 1 [Node 2 [], Node 3 []]) == [1,2,3]

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]]

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"]

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" [])[]

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 = []}

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 = []}

2-dimensional ASCII drawing of a tree.

Examples

putStr $ drawTree $ fmap show (Node 1 [Node 2 [], Node 3 []])

1
|
+- 2
|
`- 3

2-dimensional ASCII drawing of a forest.

Examples

putStr $ drawForest $ map (fmap show) [(Node 1 [Node 2 [], Node 3 []]), (Node 10 [Node 20 []])]

1
|
+- 2
|
`- 3

10
|
`- 20