Data.Forest

Multi-way trees (also known as rose trees) and forests, similar to Data.Tree from the popular containers library.

Importing

Recommended imports:

import Data.Forest (Forest, Tree)
import qualified Data.Forest as Forest

Types

data Forest a

A forest is defined completely by its trees.

To construct a forest, use forest or leaves.

Instances

Functor Forest

Methods

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

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

Foldable Forest

Methods

fold :: Monoid m => Forest m -> m

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

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

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

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

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

foldr1 :: (a -> a -> a) -> Forest a -> a

foldl1 :: (a -> a -> a) -> Forest a -> a

toList :: Forest a -> [a]

null :: Forest a -> Bool

length :: Forest a -> Int

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

maximum :: Ord a => Forest a -> a

minimum :: Ord a => Forest a -> a

sum :: Num a => Forest a -> a

product :: Num a => Forest a -> a

Eq a => Eq (Forest a)

Methods

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

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

Show a => Show (Forest a)

Methods

showsPrec :: Int -> Forest a -> ShowS

show :: Forest a -> String

showList :: [Forest a] -> ShowS

Semigroup (Forest a)

Methods

(<>) :: Forest a -> Forest a -> Forest a

sconcat :: NonEmpty (Forest a) -> Forest a

stimes :: Integral b => b -> Forest a -> Forest a

Monoid (Forest a)

Methods

mempty :: Forest a

mappend :: Forest a -> Forest a -> Forest a

mconcat :: [Forest a] -> Forest a

data Tree a

A tree is defined completely by its root and its subforest.

To construct a tree, use tree or leaf.

Instances

Functor Tree

Methods

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

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

Eq a => Eq (Tree a)

Methods

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

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

Show a => Show (Tree a)

Methods

showsPrec :: Int -> Tree a -> ShowS

show :: Tree a -> String

showList :: [Tree a] -> ShowS

Constructing

forest :: [Tree a] -> Forest a

Construct a forest from a list of trees.

forest [] is equivalent to mempty.

tree :: a -> Forest a -> Tree a

Construct a tree with a root and subforest.

leaf :: a -> Tree a

Construct a tree with a single root and no subforest.

leaf x is equivalent to tree x mempty.

leaves :: [a] -> Forest a

Construct a forest of depth 1, where each tree contains only a root.

leaves is equivalent to forest . fmap leaf

Deconstructing

trees :: Forest a -> [Tree a]

The trees that constitute the forest.

root :: Tree a -> a

The value at the root node of the tree.

subforest :: Tree a -> Forest a

The forest containing all descendants of the tree's root.

subtrees :: Tree a -> [Tree a]

The tree's immediate subtrees.

subtrees is equivalent to trees . subforest.

Forest functor

One notable difference of this Forest from that of the containers library is that this Forest is a newtype rather than a type alias, and so it provides a more appropriate Functor instance:

>>> 
:{
example :: Forest Char
example = forest
    [ tree 'a' $ leaves "bc"
    , tree 'd' $ forest
        [ leaf 'e'
        , tree 'f' $ leaves "g"
        ]
   ]
:}

>>> 
:{
printCharForest = putStrLn . showForest
  where
    showForest f = intercalate ", " (fmap showTree (trees f))
    showTree t = case trees (subforest t) of
        []   -> [root t]
        [t'] -> [root t] <> ": " <> showTree t'
        ts   -> [root t] <> ": (" <> showForest (subforest t) <> ")"
:}

>>> printCharForest example
a: (b, c), d: (e, f: g)

>>> printCharForest (fmap toUpper example)
A: (B, C), D: (E, F: G)

Likewise, Forest's Foldable instance folds over the elements of the forest.

>>> toList example
"abcdefg"