Copyright | (c) The University of Glasgow 2002 |
---|---|

License | BSD-style (see the file libraries/base/LICENSE) |

Maintainer | libraries@haskell.org |

Portability | portable |

Safe Haskell | Trustworthy |

Language | Haskell2010 |

## Synopsis

- data Tree a = Node {}
- type Forest a = [Tree a]
- unfoldTree :: (b -> (a, [b])) -> b -> Tree a
- unfoldForest :: (b -> (a, [b])) -> [b] -> [Tree a]
- unfoldTreeM :: Monad m => (b -> m (a, [b])) -> b -> m (Tree a)
- unfoldForestM :: Monad m => (b -> m (a, [b])) -> [b] -> m [Tree a]
- unfoldTreeM_BF :: Monad m => (b -> m (a, [b])) -> b -> m (Tree a)
- unfoldForestM_BF :: Monad m => (b -> m (a, [b])) -> [b] -> m [Tree a]
- foldTree :: (a -> [b] -> b) -> Tree a -> b
- flatten :: Tree a -> [a]
- levels :: Tree a -> [[a]]
- drawTree :: Tree String -> String
- drawForest :: [Tree String] -> String

# Trees and Forests

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

#### Instances

MonadZip Tree Source # |
| ||||

Foldable1 Tree Source # | Folds in preorder
| ||||

Defined in Data.Tree fold1 :: Semigroup m => Tree m -> m Source # foldMap1 :: Semigroup m => (a -> m) -> Tree a -> m Source # foldMap1' :: Semigroup m => (a -> m) -> Tree a -> m Source # toNonEmpty :: Tree a -> NonEmpty a Source # maximum :: Ord a => Tree a -> a Source # minimum :: Ord a => Tree a -> a Source # foldrMap1 :: (a -> b) -> (a -> b -> b) -> Tree a -> b Source # foldlMap1' :: (a -> b) -> (b -> a -> b) -> Tree a -> b Source # foldlMap1 :: (a -> b) -> (b -> a -> b) -> Tree a -> b Source # foldrMap1' :: (a -> b) -> (a -> b -> b) -> Tree a -> b Source # | |||||

Eq1 Tree Source # |
| ||||

Ord1 Tree Source # |
| ||||

Read1 Tree Source # |
| ||||

Defined in Data.Tree liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Tree a) Source # liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [Tree a] Source # liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (Tree a) Source # liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [Tree a] Source # | |||||

Show1 Tree Source # |
| ||||

Applicative Tree Source # | |||||

Functor Tree Source # | |||||

Monad Tree Source # | |||||

MonadFix Tree Source # |
| ||||

Foldable Tree Source # | Folds in preorder | ||||

Defined in Data.Tree fold :: Monoid m => Tree m -> m # foldMap :: Monoid m => (a -> m) -> Tree a -> m # foldMap' :: Monoid m => (a -> m) -> Tree a -> m # foldr :: (a -> b -> b) -> b -> Tree a -> b # foldr' :: (a -> b -> b) -> b -> Tree a -> b # foldl :: (b -> a -> b) -> b -> Tree a -> b # foldl' :: (b -> a -> b) -> b -> Tree a -> b # foldr1 :: (a -> a -> a) -> Tree a -> a # foldl1 :: (a -> a -> a) -> Tree a -> a # elem :: Eq a => a -> Tree a -> Bool # maximum :: Ord a => Tree a -> a # | |||||

Traversable Tree Source # | |||||

Generic1 Tree Source # | |||||

Defined in Data.Tree
| |||||

Lift a => Lift (Tree a :: Type) Source # |
| ||||

NFData a => NFData (Tree a) Source # | |||||

Data a => Data (Tree a) Source # | |||||

Defined in Data.Tree gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Tree a -> c (Tree a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Tree a) # toConstr :: Tree a -> Constr # dataTypeOf :: Tree a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Tree a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Tree a)) # gmapT :: (forall b. Data b => b -> b) -> Tree a -> Tree a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Tree a -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Tree a -> r # gmapQ :: (forall d. Data d => d -> u) -> Tree a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Tree a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Tree a -> m (Tree a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Tree a -> m (Tree a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Tree a -> m (Tree a) # | |||||

Generic (Tree a) Source # | |||||

Defined in Data.Tree
| |||||

Read a => Read (Tree a) Source # | |||||

Show a => Show (Tree a) Source # | |||||

Eq a => Eq (Tree a) Source # | |||||

Ord a => Ord (Tree a) Source # |
| ||||

type Rep1 Tree Source # |
| ||||

Defined in Data.Tree type Rep1 Tree = D1 ('MetaData "Tree" "Data.Tree" "containers-0.7-inplace" 'False) (C1 ('MetaCons "Node" 'PrefixI 'True) (S1 ('MetaSel ('Just "rootLabel") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1 :*: S1 ('MetaSel ('Just "subForest") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) ([] :.: Rec1 Tree))) | |||||

type Rep (Tree a) Source # |
| ||||

Defined in Data.Tree type Rep (Tree a) = D1 ('MetaData "Tree" "Data.Tree" "containers-0.7-inplace" 'False) (C1 ('MetaCons "Node" 'PrefixI 'True) (S1 ('MetaSel ('Just "rootLabel") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: S1 ('MetaSel ('Just "subForest") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [Tree a]))) |

# Construction

unfoldTree :: (b -> (a, [b])) -> b -> Tree a Source #

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 `Integer`

s 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] Source #

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`

.

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

Monadic tree builder, in depth-first order.

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

Monadic forest builder, in depth-first order

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

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

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 Source #

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

*Since: containers-0.5.8*

flatten :: Tree a -> [a] Source #

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]

levels :: Tree a -> [[a]] Source #

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