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 |
Data.Tree
Description
Multi-way trees (aka rose trees) and forests.
Synopsis
- data Tree a = Node {}
- type Forest a = [Tree a]
- drawTree :: Tree String -> String
- drawForest :: Forest String -> String
- flatten :: Tree a -> [a]
- levels :: Tree a -> [[a]]
- foldTree :: (a -> [b] -> b) -> Tree a -> b
- 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)
Documentation
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 # | |
Methods fold :: Monoid m => Tree m -> 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 |
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 # | |
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 :: (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) 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 |
type Rep (Tree a) = D1 (MetaData "Tree" "Data.Tree" "containers-0.5.11.0" 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 |
type Rep1 Tree = D1 (MetaData "Tree" "Data.Tree" "containers-0.5.11.0" False) (C1 (MetaCons "Node" PrefixI True) (S1 (MetaSel (Just "rootLabel") NoSourceUnpackedness NoSourceStrictness DecidedLazy) Par1 :*: S1 (MetaSel (Just "subForest") NoSourceUnpackedness NoSourceStrictness DecidedLazy) ([] :.: Rec1 Tree))) |
Two-dimensional drawing
Extraction
Building trees
unfoldTree :: (b -> (a, [b])) -> b -> Tree a Source #
Build a tree from a seed value
unfoldForest :: (b -> (a, [b])) -> [b] -> Forest a Source #
Build a forest from a list of seed values
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, 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, using an algorithm adapted from Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design, by Chris Okasaki, ICFP'00.