| 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
| MonadZip Tree Source # | Since: containers-0.5.10.1 | ||||
| Foldable1 Tree Source # | Folds in preorder Since: containers-0.6.7 | ||||
Defined in Data.Tree Methods 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 # | Since: containers-0.5.9 | ||||
| Ord1 Tree Source # | Since: containers-0.5.9 | ||||
| Read1 Tree Source # | Since: containers-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: containers-0.5.9 | ||||
| Applicative Tree Source # | |||||
| Functor Tree Source # | |||||
| Monad Tree Source # | |||||
| MonadFix Tree Source # | Since: containers-0.5.11 | ||||
| Foldable Tree Source # | Folds in preorder | ||||
Defined in Data.Tree Methods 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 Associated Types
| |||||
| Lift a => Lift (Tree a :: Type) Source # | Since: containers-0.6.6 | ||||
| NFData a => NFData (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) # 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 Associated Types
| |||||
| Read a => Read (Tree a) Source # | |||||
| Show a => Show (Tree a) Source # | |||||
| Eq a => Eq (Tree a) Source # | |||||
| Ord a => Ord (Tree a) Source # | Since: containers-0.6.5 | ||||
| type Rep1 Tree Source # | Since: containers-0.5.8 | ||||
Defined in Data.Tree type Rep1 Tree = D1 ('MetaData "Tree" "Data.Tree" "containers-0.7-f4ec" '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 # | Since: containers-0.5.8 | ||||
Defined in Data.Tree type Rep (Tree a) = D1 ('MetaData "Tree" "Data.Tree" "containers-0.7-f4ec" '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 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] 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]]