| 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 |
Data.Tree
Description
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
| Monad Tree Source # | |
| Functor Tree Source # | |
| MonadFix Tree Source # |
Since: 0.5.11 |
| Applicative Tree Source # | |
| Foldable Tree Source # | |
|
Defined in Data.Tree Methods fold :: Monoid m => Tree m -> m Source # foldMap :: Monoid m => (a -> m) -> Tree a -> m Source # foldMap' :: Monoid m => (a -> m) -> Tree a -> m Source # foldr :: (a -> b -> b) -> b -> Tree a -> b Source # foldr' :: (a -> b -> b) -> b -> Tree a -> b Source # foldl :: (b -> a -> b) -> b -> Tree a -> b Source # foldl' :: (b -> a -> b) -> b -> Tree a -> b Source # foldr1 :: (a -> a -> a) -> Tree a -> a Source # foldl1 :: (a -> a -> a) -> Tree a -> a Source # toList :: Tree a -> [a] Source # null :: Tree a -> Bool Source # length :: Tree a -> Int Source # elem :: Eq a => a -> Tree a -> Bool Source # maximum :: Ord a => Tree a -> a Source # minimum :: Ord a => Tree a -> a Source # |
|
| Traversable Tree Source # | |
| Eq1 Tree Source # |
Since: 0.5.9 |
| Ord1 Tree Source # |
Since: 0.5.9 |
| Read1 Tree Source # |
Since: 0.5.9 |
|
Defined in Data.Tree Methods 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 # |
Since: 0.5.9 |
| MonadZip Tree Source # | |
| Eq a => Eq ( Tree a) Source # | |
| Data a => Data ( Tree a) Source # | |
|
Defined in Data.Tree Methods gfoldl :: ( forall d b. Data d => c (d -> b) -> d -> c b) -> ( forall g. g -> c g) -> Tree a -> c ( Tree a) Source # gunfold :: ( forall b r. Data b => c (b -> r) -> c r) -> ( forall r. r -> c r) -> Constr -> c ( Tree a) Source # toConstr :: Tree a -> Constr Source # dataTypeOf :: Tree a -> DataType Source # dataCast1 :: Typeable t => ( forall d. Data d => c (t d)) -> Maybe (c ( Tree a)) Source # dataCast2 :: Typeable t => ( forall d e. ( Data d, Data e) => c (t d e)) -> Maybe (c ( Tree a)) Source # gmapT :: ( forall b. Data b => b -> b) -> Tree a -> Tree a Source # gmapQl :: (r -> r' -> r) -> r -> ( forall d. Data d => d -> r') -> Tree a -> r Source # gmapQr :: forall r r'. (r' -> r -> r) -> r -> ( forall d. Data d => d -> r') -> Tree a -> r Source # gmapQ :: ( forall d. Data d => d -> u) -> Tree a -> [u] Source # gmapQi :: Int -> ( forall d. Data d => d -> u) -> Tree a -> u Source # gmapM :: Monad m => ( forall d. Data d => d -> m d) -> Tree a -> m ( Tree a) Source # gmapMp :: MonadPlus m => ( forall d. Data d => d -> m d) -> Tree a -> m ( Tree a) Source # gmapMo :: MonadPlus m => ( forall d. Data d => d -> m d) -> Tree a -> m ( Tree a) Source # |
|
| Ord a => Ord ( Tree a) Source # |
Since: 0.6.5 |
| Read a => Read ( Tree a) Source # | |
| Show a => Show ( Tree a) Source # | |
| Generic ( Tree a) Source # |
Since: 0.5.8 |
| NFData a => NFData ( Tree a) Source # | |
| Generic1 Tree Source # |
Since: 0.5.8 |
| type Rep ( Tree a) Source # | |
|
Defined in Data.Tree
type
Rep
(
Tree
a) =
D1
('
MetaData
"Tree" "Data.Tree" "containers-0.6.5.1-EiES0HFUZ8PBGNrpVjoYRF" '
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])))
|
|
| type Rep1 Tree Source # | |
|
Defined in Data.Tree
type
Rep1
Tree
=
D1
('
MetaData
"Tree" "Data.Tree" "containers-0.6.5.1-EiES0HFUZ8PBGNrpVjoYRF" '
False
) (
C1
('
MetaCons
"Node" '
PrefixI
'
True
) (
S1
('
MetaSel
('
Just
"rootLabel") '
NoSourceUnpackedness
'
NoSourceStrictness
'
DecidedLazy
)
Par1
:*:
S1
('
MetaSel
('
Just
"subForest") '
NoSourceUnpackedness
'
NoSourceStrictness
'
DecidedLazy
) ([]
:.:
Rec1
Tree
)))
|
|
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: 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]]