Data.Tree

Multi-way Trees and Forests

The Tree a type represents a lazy, possibly infinite, multi-way tree (also known as a rose tree).

The Forest a type represents a forest of Tree as.

Trees and Forests

data Tree a

Non-empty, possibly infinite, multi-way trees; also known as rose trees.

Constructors

Node

Fields

• rootLabel :: a

  label value

• subForest :: [Tree a]

  zero or more child trees

Instances

MonadFix Tree

Since: 0.5.11

Defined in Data.Tree

Methods

mfix :: (a -> Tree a) -> Tree a

MonadZip Tree

Since: 0.5.10.1

Defined in Data.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)

Foldable Tree

Folds in pre-order.

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

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

Foldable1 Tree

Folds in pre-order.

Since: 0.6.7

Defined in Data.Tree

Methods

fold1 :: Semigroup m => Tree m -> m

foldMap1 :: Semigroup m => (a -> m) -> Tree a -> m

foldMap1' :: Semigroup m => (a -> m) -> Tree a -> m

toNonEmpty :: Tree a -> NonEmpty a

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

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

head :: Tree a -> a

last :: Tree a -> a

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

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

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

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

Eq1 Tree

Since: 0.5.9

Defined in Data.Tree

Methods

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

Ord1 Tree

Since: 0.5.9

Defined in Data.Tree

Methods

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

Read1 Tree

Since: 0.5.9

Defined in Data.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

Since: 0.5.9

Defined in Data.Tree

Methods

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

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

Traversable Tree

Traverses in pre-order.

Defined in Data.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)

Applicative Tree

Defined in Data.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

Functor Tree

Defined in Data.Tree

Methods

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

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

Monad Tree

Defined in Data.Tree

Methods

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

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

return :: a -> Tree a

NFData1 Tree

Since: 0.8

Defined in Data.Tree

Methods

liftRnf :: (a -> ()) -> Tree a -> ()

Generic1 Tree

Defined in Data.Tree

Associated Types

type Rep1 Tree :: k -> Type

Methods

from1 :: forall (a :: k). Tree a -> Rep1 Tree a

to1 :: forall (a :: k). Rep1 Tree a -> Tree a

Lift a => Lift (Tree a :: Type)

Since: 0.6.6

Defined in Data.Tree

Methods

lift :: Quote m => Tree a -> m Exp

liftTyped :: forall (m :: Type -> Type). Quote m => Tree a -> Code m (Tree a)

Data a => Data (Tree a)

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)

Defined in Data.Tree

Associated Types

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

Methods

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

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

Read a => Read (Tree a)

Defined in Data.Tree

Methods

readsPrec :: Int -> ReadS (Tree a)

readList :: ReadS [Tree a]

readPrec :: ReadPrec (Tree a)

readListPrec :: ReadPrec [Tree a]

Show a => Show (Tree a)

Defined in Data.Tree

Methods

showsPrec :: Int -> Tree a -> ShowS

show :: Tree a -> String

showList :: [Tree a] -> ShowS

NFData a => NFData (Tree a)

Defined in Data.Tree

Methods

rnf :: Tree a -> ()

Eq a => Eq (Tree a)

Defined in Data.Tree

Methods

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

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

Ord a => Ord (Tree a)

Since: 0.6.5

Defined in Data.Tree

Methods

compare :: Tree a -> Tree a -> Ordering

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

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

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

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

max :: Tree a -> Tree a -> Tree a

min :: Tree a -> Tree a -> Tree a

type Rep1 Tree

Since: 0.5.8

Defined in Data.Tree

type Rep1 Tree = D1 ('MetaData "Tree" "Data.Tree" "containers-0.8-44IbzD8MRbs3faPqoGcann" 'False) (C1 ('MetaCons "Node" 'PrefixI 'True) (S1 ('MetaSel ('Just "rootLabel") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1 :*: S1 ('MetaSel ('Just "subForest") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (List :.: Rec1 Tree)))

type Rep (Tree a)

Since: 0.5.8

Defined in Data.Tree

type Rep (Tree a) = D1 ('MetaData "Tree" "Data.Tree" "containers-0.8-44IbzD8MRbs3faPqoGcann" '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])))

type Forest a = [Tree a]

This type synonym exists primarily for historical reasons.

newtype PostOrder a

A newtype over Tree that folds and traverses in post-order.

Since: 0.8

Constructors

PostOrder

Fields

• unPostOrder :: Tree a

Instances

Foldable PostOrder

Defined in Data.Tree

Methods

fold :: Monoid m => PostOrder m -> m

foldMap :: Monoid m => (a -> m) -> PostOrder a -> m

foldMap' :: Monoid m => (a -> m) -> PostOrder a -> m

foldr :: (a -> b -> b) -> b -> PostOrder a -> b

foldr' :: (a -> b -> b) -> b -> PostOrder a -> b

foldl :: (b -> a -> b) -> b -> PostOrder a -> b

foldl' :: (b -> a -> b) -> b -> PostOrder a -> b

foldr1 :: (a -> a -> a) -> PostOrder a -> a

foldl1 :: (a -> a -> a) -> PostOrder a -> a

toList :: PostOrder a -> [a]

null :: PostOrder a -> Bool

length :: PostOrder a -> Int

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

maximum :: Ord a => PostOrder a -> a

minimum :: Ord a => PostOrder a -> a

sum :: Num a => PostOrder a -> a

product :: Num a => PostOrder a -> a

Foldable1 PostOrder

Defined in Data.Tree

Methods

fold1 :: Semigroup m => PostOrder m -> m

foldMap1 :: Semigroup m => (a -> m) -> PostOrder a -> m

foldMap1' :: Semigroup m => (a -> m) -> PostOrder a -> m

toNonEmpty :: PostOrder a -> NonEmpty a

maximum :: Ord a => PostOrder a -> a

minimum :: Ord a => PostOrder a -> a

head :: PostOrder a -> a

last :: PostOrder a -> a

foldrMap1 :: (a -> b) -> (a -> b -> b) -> PostOrder a -> b

foldlMap1' :: (a -> b) -> (b -> a -> b) -> PostOrder a -> b

foldlMap1 :: (a -> b) -> (b -> a -> b) -> PostOrder a -> b

foldrMap1' :: (a -> b) -> (a -> b -> b) -> PostOrder a -> b

Traversable PostOrder

Defined in Data.Tree

Methods

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

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

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

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

Functor PostOrder

Defined in Data.Tree

Methods

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

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

Generic1 PostOrder

Defined in Data.Tree

Associated Types

type Rep1 PostOrder :: k -> Type

Methods

from1 :: forall (a :: k). PostOrder a -> Rep1 PostOrder a

to1 :: forall (a :: k). Rep1 PostOrder a -> PostOrder a

Lift a => Lift (PostOrder a :: Type)

Defined in Data.Tree

Methods

lift :: Quote m => PostOrder a -> m Exp

liftTyped :: forall (m :: Type -> Type). Quote m => PostOrder a -> Code m (PostOrder a)

Data a => Data (PostOrder a)

Defined in Data.Tree

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> PostOrder a -> c (PostOrder a)

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (PostOrder a)

toConstr :: PostOrder a -> Constr

dataTypeOf :: PostOrder a -> DataType

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (PostOrder a))

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (PostOrder a))

gmapT :: (forall b. Data b => b -> b) -> PostOrder a -> PostOrder a

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> PostOrder a -> r

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> PostOrder a -> r

gmapQ :: (forall d. Data d => d -> u) -> PostOrder a -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> PostOrder a -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> PostOrder a -> m (PostOrder a)

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> PostOrder a -> m (PostOrder a)

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> PostOrder a -> m (PostOrder a)

Generic (PostOrder a)

Defined in Data.Tree

Associated Types

type Rep (PostOrder a) :: Type -> Type

Methods

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

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

Read a => Read (PostOrder a)

Defined in Data.Tree

Methods

readsPrec :: Int -> ReadS (PostOrder a)

readList :: ReadS [PostOrder a]

readPrec :: ReadPrec (PostOrder a)

readListPrec :: ReadPrec [PostOrder a]

Show a => Show (PostOrder a)

Defined in Data.Tree

Methods

showsPrec :: Int -> PostOrder a -> ShowS

show :: PostOrder a -> String

showList :: [PostOrder a] -> ShowS

Eq a => Eq (PostOrder a)

Defined in Data.Tree

Methods

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

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

Ord a => Ord (PostOrder a)

Defined in Data.Tree

Methods

compare :: PostOrder a -> PostOrder a -> Ordering

(<) :: PostOrder a -> PostOrder a -> Bool

(<=) :: PostOrder a -> PostOrder a -> Bool

(>) :: PostOrder a -> PostOrder a -> Bool

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

max :: PostOrder a -> PostOrder a -> PostOrder a

min :: PostOrder a -> PostOrder a -> PostOrder a

type Rep1 PostOrder

Defined in Data.Tree

type Rep1 PostOrder = D1 ('MetaData "PostOrder" "Data.Tree" "containers-0.8-44IbzD8MRbs3faPqoGcann" 'True) (C1 ('MetaCons "PostOrder" 'PrefixI 'True) (S1 ('MetaSel ('Just "unPostOrder") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec1 Tree)))

type Rep (PostOrder a)

Defined in Data.Tree

type Rep (PostOrder a) = D1 ('MetaData "PostOrder" "Data.Tree" "containers-0.8-44IbzD8MRbs3faPqoGcann" 'True) (C1 ('MetaCons "PostOrder" 'PrefixI 'True) (S1 ('MetaSel ('Just "unPostOrder") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Tree a))))

Construction

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

Build a (possibly infinite) tree from a seed value.

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 (depth-first) and unfoldTreeM_BF (breadth-first).

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]

Build a (possibly infinite) forest from a list of seed values.

unfoldForest f seeds invokes unfoldTree on each seed value.

For a monadic version, see unfoldForestM (depth-first) and unfoldForestM_BF (breadth-first).

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 [Tree 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.

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]

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

Fold a tree into a "summary" value.

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]

Returns the elements of a tree in pre-order.

flatten == Data.Foldable.toList

  a
 / \    => [a,b,c]
b   c

Examples

flatten (Node 1 [Node 2 [], Node 3 []]) == [1,2,3]

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

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]]

leaves :: Tree a -> [a]

\(O(n)\). The leaves of the tree in left-to-right order.

A leaf is a node with no children.

Examples

>>> :{
leaves $
  Node 1
    [ Node 2
        [ Node 4 []
        , Node 5 []
        ]
    , Node 3
        [ Node 6 []
        ]
    ]
:}
[4,5,6]
>>> leaves (Node "root" [])
["root"]

Since: 0.8

edges :: Tree a -> [(a, a)]

\(O(n)\). The edges of the tree as parent-child pairs in pre-order.

A tree with \(n\) nodes has \(n-1\) edges.

Examples

>>> :{
edges $
  Node 1
    [ Node 2
        [ Node 4 []
        , Node 5 []
        ]
    , Node 3
        [ Node 6 []
        ]
    ]
:}
[(1,2),(2,4),(2,5),(1,3),(3,6)]
>>> edges (Node "root" [])
[]

Since: 0.8

pathsToRoot :: Tree a -> Tree (NonEmpty a)

\(O(n)\). Labels on the paths from each node to the root.

Examples

>>> :{
pathsToRoot $
  Node 1
    [ Node 2 []
    , Node 3 []
    ]
:}
Node {rootLabel = 1 :| [], subForest = [Node {rootLabel = 2 :| [1], subForest = []},Node {rootLabel = 3 :| [1], subForest = []}]}
>>> pathsToRoot (Node "root" [])
Node {rootLabel = "root" :| [], subForest = []}

Since: 0.8

pathsFromRoot :: Tree a -> Tree (NonEmpty a)

Labels on the paths from the root to each node.

If the path orientation is not important, consider using pathsToRoot instead because it is more efficient.

Examples

>>> :{
pathsFromRoot $
  Node 1
    [ Node 2 []
    , Node 3 []
    ]
:}
Node {rootLabel = 1 :| [], subForest = [Node {rootLabel = 1 :| [2], subForest = []},Node {rootLabel = 1 :| [3], subForest = []}]}
>>> pathsFromRoot (Node "root" [])
Node {rootLabel = "root" :| [], subForest = []}

Since: 0.8

Ascii Drawings

drawTree :: Tree String -> String

2-dimensional ASCII drawing of a tree.

Examples

putStr $ drawTree $ fmap show (Node 1 [Node 2 [], Node 3 []])

1
|
+- 2
|
`- 3

drawForest :: [Tree String] -> String

2-dimensional ASCII drawing of a forest.

Examples

putStr $ drawForest $ map (fmap show) [(Node 1 [Node 2 [], Node 3 []]), (Node 10 [Node 20 []])]

1
|
+- 2
|
`- 3

10
|
`- 20