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

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.

A TreeTreeBranch is returned by treeTreeBranch to indicate how two Bins relate to each other. Consider that A and B are the Bins whose Prefixes are given to treeTreeBranch as the first and second arguments respectively.

Show the tree that implements the map. The tree is shown in a compressed, hanging format.

The expression (showTreeWith hang wide map) shows the tree that implements the map. If hang is True, a hanging tree is shown otherwise a rotated tree is shown. If wide is True, an extra wide version is shown.

Show the tree that implements the set. The tree is shown in a compressed, hanging format.

The expression (showTreeWith hang wide map) shows the tree that implements the set. If hang is True, a hanging tree is shown otherwise a rotated tree is shown. If wide is True, an extra wide version is shown.

WARNING

This module is considered internal. The Package Versioning Policy does not apply. The contents of this module may change in any way whatsoever and without any warning between minor versions of this package. Authors importing this module are expected to track development closely.

Description

This module defines common constructs used by both Data.IntSet and Data.IntMap.

Show the tree that implements the map. The tree is shown in a compressed, hanging format. See showTreeWith.

The expression (showTreeWith showelem hang wide map) shows the tree that implements the map. Elements are shown using the showElem function. If hang is True, a hanging tree is shown otherwise a rotated tree is shown. If wide is True, an extra wide version is shown.

Map> let t = fromDistinctAscList [(x,()) | x <- [1..5]]
Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True False t
(4,())
+--(2,())
|  +--(1,())
|  +--(3,())
+--(5,())

Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True True t
(4,())
|
+--(2,())
|  |
|  +--(1,())
|  |
|  +--(3,())
|
+--(5,())

Map> putStrLn $ showTreeWith (\k x -> show (k,x)) False True t
+--(5,())
|
(4,())
|
|  +--(3,())
|  |
+--(2,())
|
+--(1,())

A foldMap-like function, specialized to the Option monoid, which takes advantage of the internal structure of Seq to avoid wrapping in Maybe at certain points.

A foldMapWithIndex-like function, specialized to the Option monoid, which takes advantage of the internal structure of Seq to avoid wrapping in Maybe at certain points.

Show the tree that implements the set. The tree is shown in a compressed, hanging format.

The expression (showTreeWith hang wide map) shows the tree that implements the set. If hang is True, a hanging tree is shown otherwise a rotated tree is shown. If wide is True, an extra wide version is shown.

Set> putStrLn $ showTreeWith True False $ fromDistinctAscList [1..5]
4
+--2
|  +--1
|  +--3
+--5

Set> putStrLn $ showTreeWith True True $ fromDistinctAscList [1..5]
4
|
+--2
|  |
|  +--1
|  |
|  +--3
|
+--5

Set> putStrLn $ showTreeWith False True $ fromDistinctAscList [1..5]
+--5
|
4
|
|  +--3
|  |
+--2
|
+--1

2-dimensional ASCII drawing of a tree.

Examples

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

1
|
+- 2
|
`- 3

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

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

Monadic tree 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.