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 | Haskell98 |
Synopsis
- data Tree a = Node {}
- type Forest a = [Tree a]
- unfoldTree :: (b -> (a, [b])) -> b -> Tree a
- unfoldForest :: (b -> (a, [b])) -> [b] -> Forest a
- unfoldTreeM :: Monad m => (b -> m (a, [b])) -> b -> m (Tree a)
- unfoldForestM :: Monad m => (b -> m (a, [b])) -> [b] -> m (Forest a)
- unfoldTreeM_BF :: Monad m => (b -> m (a, [b])) -> b -> m (Tree a)
- unfoldForestM_BF :: Monad m => (b -> m (a, [b])) -> [b] -> m (Forest a)
- foldTree :: (a -> [b] -> b) -> Tree a -> b
- flatten :: Tree a -> [a]
- levels :: Tree a -> [[a]]
- drawTree :: Tree String -> String
- drawForest :: Forest 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 fold :: Monoid m => Tree m -> 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 # | |
Eq1 Tree Source # | Since: 0.5.9 |
Ord1 Tree Source # | Since: 0.5.9 |
Read1 Tree Source # | Since: 0.5.9 |
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 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 :: (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) # | |
Read a => Read (Tree a) Source # | |
Show a => Show (Tree a) Source # | |
Generic (Tree a) Source # | |
NFData a => NFData (Tree a) Source # | |
Generic1 Tree Source # | |
type Rep (Tree a) Source # | Since: 0.5.8 |
Defined in Data.Tree type Rep (Tree a) = D1 (MetaData "Tree" "Data.Tree" "containers-0.6.2.1-ChagGP7vch8FhOClSM0wYR" False) (C1 (MetaCons "Node" PrefixI True) (S1 (MetaSel (Just "rootLabel") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a) :*: S1 (MetaSel (Just "subForest") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Forest a)))) | |
type Rep1 Tree Source # | Since: 0.5.8 |
Defined in Data.Tree type Rep1 Tree = D1 (MetaData "Tree" "Data.Tree" "containers-0.6.2.1-ChagGP7vch8FhOClSM0wYR" 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] -> Forest 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 (Forest 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 (Forest 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]]