HORIZON HASKELLDocslts/ghc-9.10.xc74966e2026-09-27Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · c74966e · 2026-09-27

Modulecontainers-0.7Haskell2010

Data.Tree

Multi-way Trees and Forests

The Tree a type represents a lazy, possibly infinite, multi-way tree (also known as a rose tree).

The Forest a type represents a forest of Tree as.

  • 2 types
  • 11 values
  • Packagecontainers-0.7
  • Exports13
  • LanguageHaskell2010
  • LicenceBSD-3-Clause
  • SourceTree.hs

Trees and Forests

2 declarations
datadata Tree a
#

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

Constructors

Instances23Monad, Functor, MonadFix, Applicative, Foldable, Traversable, …
typetype Forest a = [Tree a]
#

This type synonym exists primarily for historical reasons.

Construction

6 declarations
valueunfoldTree :: (b -> (a, [b])) -> b -> Tree a
#

Build a (possibly infinite) tree from a seed value in breadth-first order.

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_BF.

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
valueunfoldForest :: (b -> (a, [b])) -> [b] -> [Tree a]
#

Build a (possibly infinite) forest from a list of seed values in breadth-first order.

unfoldForest f seeds invokes unfoldTree on each seed value.

For a monadic version see unfoldForestM_BF.

valueunfoldTreeM :: Monad m => (b -> m (a, [b])) -> b -> m (Tree a)
#

Monadic tree builder, in depth-first order.

valueunfoldForestM :: Monad m => (b -> m (a, [b])) -> [b] -> m [Tree a]
#

Monadic forest builder, in depth-first order

valueunfoldTreeM_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.

valueunfoldForestM_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.

Elimination

3 declarations
valuefoldTree :: (a -> [b] -> b) -> Tree a -> b
#

Fold a tree into a "summary" value in depth-first order.

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))
valueflatten :: Tree a -> [a]
#

Returns the elements of a tree in pre-order.


  a
 / \    => [a,b,c]
b   c
Examples
flatten (Node 1 [Node 2 [], Node 3 []]) == [1,2,3]
valuelevels :: 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]]

Ascii Drawings

2 declarations
valuedrawTree :: Tree String -> String
#

2-dimensional ASCII drawing of a tree.

Examples
putStr $ drawTree $ fmap show (Node 1 [Node 2 [], Node 3 []])
1
|
+- 2
|
`- 3
valuedrawForest :: [Tree String] -> String
#

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