Data.Tree

Multi-way trees (aka rose trees) and forests.

Documentation

data Tree a

Multi-way trees, also known as rose trees.

Constructors

Node

Fields

• rootLabel :: a

  label value

• subForest :: Forest a

  zero or more child trees

Instances

Monad Tree

Methods

(>>=) :: Tree a -> (a -> Tree b) -> Tree b

(>>) :: Tree a -> Tree b -> Tree b

return :: a -> Tree a

fail :: String -> Tree a

Functor Tree

Methods

fmap :: (a -> b) -> Tree a -> Tree b

(<$) :: a -> Tree b -> Tree a

Applicative Tree

Methods

pure :: a -> Tree a

(<*>) :: Tree (a -> b) -> Tree a -> Tree b

liftA2 :: (a -> b -> c) -> Tree a -> Tree b -> Tree c

(*>) :: Tree a -> Tree b -> Tree b

(<*) :: Tree a -> Tree b -> Tree a

Foldable Tree

Methods

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

toList :: Tree a -> [a]

null :: Tree a -> Bool

length :: Tree a -> Int

elem :: Eq a => a -> Tree a -> Bool

maximum :: Ord a => Tree a -> a

minimum :: Ord a => Tree a -> a

sum :: Num a => Tree a -> a

product :: Num a => Tree a -> a

Traversable Tree

Methods

traverse :: Applicative f => (a -> f b) -> Tree a -> f (Tree b)

sequenceA :: Applicative f => Tree (f a) -> f (Tree a)

mapM :: Monad m => (a -> m b) -> Tree a -> m (Tree b)

sequence :: Monad m => Tree (m a) -> m (Tree a)

Eq1 Tree

Methods

liftEq :: (a -> b -> Bool) -> Tree a -> Tree b -> Bool

Ord1 Tree

Methods

liftCompare :: (a -> b -> Ordering) -> Tree a -> Tree b -> Ordering

Read1 Tree

Methods

liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Tree a)

liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [Tree a]

liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (Tree a)

liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [Tree a]

Show1 Tree

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Tree a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Tree a] -> ShowS

MonadZip Tree

Methods

mzip :: Tree a -> Tree b -> Tree (a, b)

mzipWith :: (a -> b -> c) -> Tree a -> Tree b -> Tree c

munzip :: Tree (a, b) -> (Tree a, Tree b)

Eq a => Eq (Tree a)

Methods

(==) :: Tree a -> Tree a -> Bool

(/=) :: Tree a -> Tree a -> Bool

Data a => Data (Tree a)

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 :: (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)

Methods

readsPrec :: Int -> ReadS (Tree a)

readList :: ReadS [Tree a]

readPrec :: ReadPrec (Tree a)

readListPrec :: ReadPrec [Tree a]

Show a => Show (Tree a)

Methods

showsPrec :: Int -> Tree a -> ShowS

show :: Tree a -> String

showList :: [Tree a] -> ShowS

Generic (Tree a)

Associated Types

type Rep (Tree a) :: * -> *

Methods

from :: Tree a -> Rep (Tree a) x

to :: Rep (Tree a) x -> Tree a

NFData a => NFData (Tree a)

Methods

rnf :: Tree a -> ()

Generic1 * Tree

Associated Types

type Rep1 Tree (f :: Tree -> *) :: k -> *

Methods

from1 :: f a -> Rep1 Tree f a

to1 :: Rep1 Tree f a -> f a

type Rep (Tree a)

type Rep (Tree a) = D1 * (MetaData "Tree" "Data.Tree" "containers-0.5.10.2-JOjc9xI4RgWIuwuFLwhvNw" False) (C1 * (MetaCons "Node" PrefixI True) ((:*:) * (S1 * (MetaSel (Just Symbol "rootLabel") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 * a)) (S1 * (MetaSel (Just Symbol "subForest") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 * (Forest a)))))

type Rep1 * Tree

type Rep1 * Tree = D1 * (MetaData "Tree" "Data.Tree" "containers-0.5.10.2-JOjc9xI4RgWIuwuFLwhvNw" False) (C1 * (MetaCons "Node" PrefixI True) ((:*:) * (S1 * (MetaSel (Just Symbol "rootLabel") NoSourceUnpackedness NoSourceStrictness DecidedLazy) Par1) (S1 * (MetaSel (Just Symbol "subForest") NoSourceUnpackedness NoSourceStrictness DecidedLazy) ((:.:) * * [] (Rec1 * Tree)))))

type Forest a = [Tree a]

Two-dimensional drawing

drawTree :: Tree String -> String

Neat 2-dimensional drawing of a tree.

drawForest :: Forest String -> String

Neat 2-dimensional drawing of a forest.

Extraction

flatten :: Tree a -> [a]

The elements of a tree in pre-order.

levels :: Tree a -> [[a]]

Lists of nodes at each level of the tree.

foldTree :: (a -> [b] -> b) -> Tree a -> b

Catamorphism on trees.

Building trees

unfoldTree :: (b -> (a, [b])) -> b -> Tree a

Build a tree from a seed value

unfoldForest :: (b -> (a, [b])) -> [b] -> Forest a

Build a forest from a list of seed values

unfoldTreeM :: Monad m => (b -> m (a, [b])) -> b -> m (Tree a)

Monadic tree builder, in depth-first order

unfoldForestM :: Monad m => (b -> m (a, [b])) -> [b] -> m (Forest a)

Monadic forest builder, in depth-first order

unfoldTreeM_BF :: Monad m => (b -> m (a, [b])) -> b -> m (Tree a)

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)

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.