Community
Modules 31

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.

1 generation diagnostics
  • unattached documentation comment at 934:1

Trees and Forests

data Tree a

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

Node :: a -> [Tree a] -> Tree a

subForest :: Tree a -> [Tree a]

zero or more child trees

type Forest a = [Tree a]

This type synonym exists primarily for historical reasons.

newtype PostOrder a

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]

Construction

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

unfoldForest :: (b -> (a, [b])) -> [b] -> [Tree a]

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

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

Monadic tree builder, in depth-first order.

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

Monadic forest builder, in depth-first order.

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.

Elimination

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

flatten :: Tree a -> [a]

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]

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

Ascii Drawings

drawTree :: Tree String -> String

2-dimensional ASCII drawing of a tree.

Examples

putStr $ drawTree $ fmap show (Node 1 [Node 2 [], Node 3 []])
1
|
+- 2
|
`- 3

drawForest :: [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

Instances

34
  • instance Eq a => Eq (Tree a)
  • instance Ord a => Ord (Tree a)
  • instance Read a => Read (Tree a)
  • instance Show a => Show (Tree a)
  • instance Data a => Data (Tree a)
  • instance Generic a => Generic (Tree a)
  • instance Generic1 a => Generic1 (Tree a)
  • instance Lift a => Lift (Tree a)
  • instance Eq1 Tree
  • instance Ord1 Tree
  • instance Show1 Tree
  • instance Read1 Tree
  • instance Functor Tree
  • instance Applicative Tree
  • instance Monad Tree
  • instance MonadFix Tree
  • instance Traversable Tree

    Traverses in pre-order.

  • instance Foldable Tree

    Folds in pre-order.

  • instance Foldable1.Foldable1 Tree

    Folds in pre-order.

  • instance NFData a => NFData (Tree a)
  • instance NFData1 Tree
  • instance MonadZip Tree
  • instance Eq a => Eq (PostOrder a)
  • instance Ord a => Ord (PostOrder a)
  • instance Read a => Read (PostOrder a)
  • instance Show a => Show (PostOrder a)
  • instance Data a => Data (PostOrder a)
  • instance Generic a => Generic (PostOrder a)
  • instance Generic1 a => Generic1 (PostOrder a)
  • instance Lift a => Lift (PostOrder a)
  • instance Functor PostOrder
  • instance Foldable PostOrder
  • instance Traversable PostOrder
  • instance Foldable1.Foldable1 PostOrder
Maintainer
libraries@haskell.org
Portability
portable
Copyright
(c) The University of Glasgow 2002
License
BSD-style (see the file libraries/base/LICENSE)
Build record and source files

Community contribution. The service has not verified this documentation. The generator reported 15 diagnostics.

Target: Linux on x86-64. Some inferred types and resolved links are not available.

Generator: aihc-haddock-aa6debbd-web-3

Metadata snapshot: 634f718c0d8cd970c4e2c511d2345d8fd36c6dc32b06343c2b4e914ffccbce7f

Open the dependency plan · Download the documentation model

Import a package

Enter a package name and an exact version from Hackage. The site contains imported versions only.