| Copyright | (c) The University of Glasgow 2002 |
|---|---|
| License | BSD-style (see the file libraries/base/LICENSE) |
| Maintainer | [email protected] |
| Portability | portable |
| Safe Haskell | Trustworthy |
| Language | Haskell98 |
The Tree a type represents a lazy, possibly infinite, multi-way tree (also known as a rose tree).
Non-empty, possibly infinite, multi-way trees; also known as rose trees.
| Monad Tree | |
| Functor Tree | |
| MonadFix Tree | Since: containers-0.5.11 |
| Applicative Tree | |
| Foldable Tree | |
Defined in Data.Tree Methodsfold :: 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 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 | |
| Eq1 Tree | Since: containers-0.5.9 |
| Ord1 Tree | Since: containers-0.5.9 |
| Read1 Tree | Since: containers-0.5.9 |
Defined in Data.Tree MethodsliftReadsPrec :: (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 | Since: containers-0.5.9 |
| MonadZip Tree | |
| Eq a => Eq (Tree a) | |
| Data a => Data (Tree a) | |
Defined in Data.Tree Methodsgfoldl :: (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 | |
| Read a => Read (Tree a) | |
| Show a => Show (Tree a) | |
| Generic (Tree a) | Since: containers-0.5.8 |
| NFData a => NFData (Tree a) | |
| Generic1 Tree | Since: containers-0.5.8 |
| type Rep (Tree a) | |
Defined in Data.Tree type Rep (Tree a) = D1 ('MetaData "Tree" "Data.Tree" "containers-0.6.2.1" '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 | |
Defined in Data.Tree type Rep1 Tree = D1 ('MetaData "Tree" "Data.Tree" "containers-0.6.2.1" 'False) (C1 ('MetaCons "Node" 'PrefixI 'True) (S1 ('MetaSel ('Just "rootLabel") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1 :*: S1 ('MetaSel ('Just "subForest") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) ([] :.: Rec1 Tree))) | |
type Forest a = [Tree a] Source
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.
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] -> 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/.
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.
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
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
levels (Node 1 [Node 2 [], Node 3 []]) == [[1],[2,3]]
drawTree :: Tree String -> String Source
2-dimensional ASCII drawing of a tree.
putStr $ drawTree $ fmap show (Node 1 [Node 2 [], Node 3 []])
1 | +- 2 | `- 3
drawForest :: Forest String -> String Source
2-dimensional ASCII drawing of a forest.
putStr $ drawForest $ map (fmap show) [(Node 1 [Node 2 [], Node 3 []]), (Node 10 [Node 20 []])]
1 | +- 2 | `- 3 10 | `- 20
© The University of Glasgow and others
Licensed under a BSD-style license (see top of the page).
https://downloads.haskell.org/~ghc/8.8.3/docs/html/libraries/containers-0.6.2.1/Data-Tree.html