{- |

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

-}

{-# LANGUAGE DeriveFoldable, DeriveFunctor, DeriveTraversable,
             GeneralizedNewtypeDeriving #-}

module Data.Forest
    (
    -- * Importing
    -- $imports

    -- * Types
      Forest
    , Tree

    -- * Constructing
    , forest
    , tree
    , leaf
    , leaves

    -- * Deconstructing
    , trees
    , root
    , subforest
    , subtrees

    -- * Folds
    , foldForest
    , foldTree

    -- * Forest functor
    -- $functor

    ) where

import Data.Eq (Eq)
import Data.Foldable (Foldable)
import Data.Function (($))
import Data.Functor (Functor, fmap, (<$>))
import Data.Monoid (Monoid, mempty)
import Data.Semigroup (Semigroup)
import Data.Traversable (Traversable)
import Prelude (Show)

--------------------------------------------------------------------------------

-- | A forest is defined completely by its 'trees'.
--
-- To construct a forest, use 'forest' or 'leaves'.

newtype Forest a = Forest
    { Forest a -> [Tree a]
trees :: [Tree a] -- ^ The trees that constitute the forest.
    }
    deriving (Forest a -> Forest a -> Bool
(Forest a -> Forest a -> Bool)
-> (Forest a -> Forest a -> Bool) -> Eq (Forest a)
forall a. Eq a => Forest a -> Forest a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Forest a -> Forest a -> Bool
$c/= :: forall a. Eq a => Forest a -> Forest a -> Bool
== :: Forest a -> Forest a -> Bool
$c== :: forall a. Eq a => Forest a -> Forest a -> Bool
Eq, Int -> Forest a -> ShowS
[Forest a] -> ShowS
Forest a -> String
(Int -> Forest a -> ShowS)
-> (Forest a -> String) -> ([Forest a] -> ShowS) -> Show (Forest a)
forall a. Show a => Int -> Forest a -> ShowS
forall a. Show a => [Forest a] -> ShowS
forall a. Show a => Forest a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Forest a] -> ShowS
$cshowList :: forall a. Show a => [Forest a] -> ShowS
show :: Forest a -> String
$cshow :: forall a. Show a => Forest a -> String
showsPrec :: Int -> Forest a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Forest a -> ShowS
Show, a -> Forest b -> Forest a
(a -> b) -> Forest a -> Forest b
(forall a b. (a -> b) -> Forest a -> Forest b)
-> (forall a b. a -> Forest b -> Forest a) -> Functor Forest
forall a b. a -> Forest b -> Forest a
forall a b. (a -> b) -> Forest a -> Forest b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> Forest b -> Forest a
$c<$ :: forall a b. a -> Forest b -> Forest a
fmap :: (a -> b) -> Forest a -> Forest b
$cfmap :: forall a b. (a -> b) -> Forest a -> Forest b
Functor, Forest a -> Bool
(a -> m) -> Forest a -> m
(a -> b -> b) -> b -> Forest a -> b
(forall m. Monoid m => Forest m -> m)
-> (forall m a. Monoid m => (a -> m) -> Forest a -> m)
-> (forall m a. Monoid m => (a -> m) -> Forest a -> m)
-> (forall a b. (a -> b -> b) -> b -> Forest a -> b)
-> (forall a b. (a -> b -> b) -> b -> Forest a -> b)
-> (forall b a. (b -> a -> b) -> b -> Forest a -> b)
-> (forall b a. (b -> a -> b) -> b -> Forest a -> b)
-> (forall a. (a -> a -> a) -> Forest a -> a)
-> (forall a. (a -> a -> a) -> Forest a -> a)
-> (forall a. Forest a -> [a])
-> (forall a. Forest a -> Bool)
-> (forall a. Forest a -> Int)
-> (forall a. Eq a => a -> Forest a -> Bool)
-> (forall a. Ord a => Forest a -> a)
-> (forall a. Ord a => Forest a -> a)
-> (forall a. Num a => Forest a -> a)
-> (forall a. Num a => Forest a -> a)
-> Foldable Forest
forall a. Eq a => a -> Forest a -> Bool
forall a. Num a => Forest a -> a
forall a. Ord a => Forest a -> a
forall m. Monoid m => Forest m -> m
forall a. Forest a -> Bool
forall a. Forest a -> Int
forall a. Forest a -> [a]
forall a. (a -> a -> a) -> Forest a -> a
forall m a. Monoid m => (a -> m) -> Forest a -> m
forall b a. (b -> a -> b) -> b -> Forest a -> b
forall a b. (a -> b -> b) -> b -> Forest a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: Forest a -> a
$cproduct :: forall a. Num a => Forest a -> a
sum :: Forest a -> a
$csum :: forall a. Num a => Forest a -> a
minimum :: Forest a -> a
$cminimum :: forall a. Ord a => Forest a -> a
maximum :: Forest a -> a
$cmaximum :: forall a. Ord a => Forest a -> a
elem :: a -> Forest a -> Bool
$celem :: forall a. Eq a => a -> Forest a -> Bool
length :: Forest a -> Int
$clength :: forall a. Forest a -> Int
null :: Forest a -> Bool
$cnull :: forall a. Forest a -> Bool
toList :: Forest a -> [a]
$ctoList :: forall a. Forest a -> [a]
foldl1 :: (a -> a -> a) -> Forest a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> Forest a -> a
foldr1 :: (a -> a -> a) -> Forest a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> Forest a -> a
foldl' :: (b -> a -> b) -> b -> Forest a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> Forest a -> b
foldl :: (b -> a -> b) -> b -> Forest a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> Forest a -> b
foldr' :: (a -> b -> b) -> b -> Forest a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> Forest a -> b
foldr :: (a -> b -> b) -> b -> Forest a -> b
$cfoldr :: forall a b. (a -> b -> b) -> b -> Forest a -> b
foldMap' :: (a -> m) -> Forest a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> Forest a -> m
foldMap :: (a -> m) -> Forest a -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> Forest a -> m
fold :: Forest m -> m
$cfold :: forall m. Monoid m => Forest m -> m
Foldable, Functor Forest
Foldable Forest
Functor Forest
-> Foldable Forest
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Forest a -> f (Forest b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    Forest (f a) -> f (Forest a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Forest a -> m (Forest b))
-> (forall (m :: * -> *) a.
    Monad m =>
    Forest (m a) -> m (Forest a))
-> Traversable Forest
(a -> f b) -> Forest a -> f (Forest b)
forall (t :: * -> *).
Functor t
-> Foldable t
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a. Monad m => Forest (m a) -> m (Forest a)
forall (f :: * -> *) a.
Applicative f =>
Forest (f a) -> f (Forest a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Forest a -> m (Forest b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Forest a -> f (Forest b)
sequence :: Forest (m a) -> m (Forest a)
$csequence :: forall (m :: * -> *) a. Monad m => Forest (m a) -> m (Forest a)
mapM :: (a -> m b) -> Forest a -> m (Forest b)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Forest a -> m (Forest b)
sequenceA :: Forest (f a) -> f (Forest a)
$csequenceA :: forall (f :: * -> *) a.
Applicative f =>
Forest (f a) -> f (Forest a)
traverse :: (a -> f b) -> Forest a -> f (Forest b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Forest a -> f (Forest b)
$cp2Traversable :: Foldable Forest
$cp1Traversable :: Functor Forest
Traversable, b -> Forest a -> Forest a
NonEmpty (Forest a) -> Forest a
Forest a -> Forest a -> Forest a
(Forest a -> Forest a -> Forest a)
-> (NonEmpty (Forest a) -> Forest a)
-> (forall b. Integral b => b -> Forest a -> Forest a)
-> Semigroup (Forest a)
forall b. Integral b => b -> Forest a -> Forest a
forall a. NonEmpty (Forest a) -> Forest a
forall a. Forest a -> Forest a -> Forest a
forall a.
(a -> a -> a)
-> (NonEmpty a -> a)
-> (forall b. Integral b => b -> a -> a)
-> Semigroup a
forall a b. Integral b => b -> Forest a -> Forest a
stimes :: b -> Forest a -> Forest a
$cstimes :: forall a b. Integral b => b -> Forest a -> Forest a
sconcat :: NonEmpty (Forest a) -> Forest a
$csconcat :: forall a. NonEmpty (Forest a) -> Forest a
<> :: Forest a -> Forest a -> Forest a
$c<> :: forall a. Forest a -> Forest a -> Forest a
Semigroup, Semigroup (Forest a)
Forest a
Semigroup (Forest a)
-> Forest a
-> (Forest a -> Forest a -> Forest a)
-> ([Forest a] -> Forest a)
-> Monoid (Forest a)
[Forest a] -> Forest a
Forest a -> Forest a -> Forest a
forall a. Semigroup (Forest a)
forall a. Forest a
forall a.
Semigroup a -> a -> (a -> a -> a) -> ([a] -> a) -> Monoid a
forall a. [Forest a] -> Forest a
forall a. Forest a -> Forest a -> Forest a
mconcat :: [Forest a] -> Forest a
$cmconcat :: forall a. [Forest a] -> Forest a
mappend :: Forest a -> Forest a -> Forest a
$cmappend :: forall a. Forest a -> Forest a -> Forest a
mempty :: Forest a
$cmempty :: forall a. Forest a
$cp1Monoid :: forall a. Semigroup (Forest a)
Monoid)

-- | A tree is defined completely by its 'root' and its 'subforest'.
--
-- To construct a tree, use 'tree' or 'leaf'.

data Tree a = Tree
    { Tree a -> a
root :: a             -- ^ The value at the root node of the tree.
    , Tree a -> Forest a
subforest :: Forest a -- ^ The forest containing all descendants
                            --   of the tree's 'root'.
    }
    deriving (Tree a -> Tree a -> Bool
(Tree a -> Tree a -> Bool)
-> (Tree a -> Tree a -> Bool) -> Eq (Tree a)
forall a. Eq a => Tree a -> Tree a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Tree a -> Tree a -> Bool
$c/= :: forall a. Eq a => Tree a -> Tree a -> Bool
== :: Tree a -> Tree a -> Bool
$c== :: forall a. Eq a => Tree a -> Tree a -> Bool
Eq, Int -> Tree a -> ShowS
[Tree a] -> ShowS
Tree a -> String
(Int -> Tree a -> ShowS)
-> (Tree a -> String) -> ([Tree a] -> ShowS) -> Show (Tree a)
forall a. Show a => Int -> Tree a -> ShowS
forall a. Show a => [Tree a] -> ShowS
forall a. Show a => Tree a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Tree a] -> ShowS
$cshowList :: forall a. Show a => [Tree a] -> ShowS
show :: Tree a -> String
$cshow :: forall a. Show a => Tree a -> String
showsPrec :: Int -> Tree a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Tree a -> ShowS
Show, a -> Tree b -> Tree a
(a -> b) -> Tree a -> Tree b
(forall a b. (a -> b) -> Tree a -> Tree b)
-> (forall a b. a -> Tree b -> Tree a) -> Functor Tree
forall a b. a -> Tree b -> Tree a
forall a b. (a -> b) -> Tree a -> Tree b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> Tree b -> Tree a
$c<$ :: forall a b. a -> Tree b -> Tree a
fmap :: (a -> b) -> Tree a -> Tree b
$cfmap :: forall a b. (a -> b) -> Tree a -> Tree b
Functor, Tree a -> Bool
(a -> m) -> Tree a -> m
(a -> b -> b) -> b -> Tree a -> b
(forall m. Monoid m => Tree m -> m)
-> (forall m a. Monoid m => (a -> m) -> Tree a -> m)
-> (forall m a. Monoid m => (a -> m) -> Tree a -> m)
-> (forall a b. (a -> b -> b) -> b -> Tree a -> b)
-> (forall a b. (a -> b -> b) -> b -> Tree a -> b)
-> (forall b a. (b -> a -> b) -> b -> Tree a -> b)
-> (forall b a. (b -> a -> b) -> b -> Tree a -> b)
-> (forall a. (a -> a -> a) -> Tree a -> a)
-> (forall a. (a -> a -> a) -> Tree a -> a)
-> (forall a. Tree a -> [a])
-> (forall a. Tree a -> Bool)
-> (forall a. Tree a -> Int)
-> (forall a. Eq a => a -> Tree a -> Bool)
-> (forall a. Ord a => Tree a -> a)
-> (forall a. Ord a => Tree a -> a)
-> (forall a. Num a => Tree a -> a)
-> (forall a. Num a => Tree a -> a)
-> Foldable Tree
forall a. Eq a => a -> Tree a -> Bool
forall a. Num a => Tree a -> a
forall a. Ord a => Tree a -> a
forall m. Monoid m => Tree m -> m
forall a. Tree a -> Bool
forall a. Tree a -> Int
forall a. Tree a -> [a]
forall a. (a -> a -> a) -> Tree a -> a
forall m a. Monoid m => (a -> m) -> Tree a -> m
forall b a. (b -> a -> b) -> b -> Tree a -> b
forall a b. (a -> b -> b) -> b -> Tree a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: Tree a -> a
$cproduct :: forall a. Num a => Tree a -> a
sum :: Tree a -> a
$csum :: forall a. Num a => Tree a -> a
minimum :: Tree a -> a
$cminimum :: forall a. Ord a => Tree a -> a
maximum :: Tree a -> a
$cmaximum :: forall a. Ord a => Tree a -> a
elem :: a -> Tree a -> Bool
$celem :: forall a. Eq a => a -> Tree a -> Bool
length :: Tree a -> Int
$clength :: forall a. Tree a -> Int
null :: Tree a -> Bool
$cnull :: forall a. Tree a -> Bool
toList :: Tree a -> [a]
$ctoList :: forall a. Tree a -> [a]
foldl1 :: (a -> a -> a) -> Tree a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> Tree a -> a
foldr1 :: (a -> a -> a) -> Tree a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> Tree a -> a
foldl' :: (b -> a -> b) -> b -> Tree a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> Tree a -> b
foldl :: (b -> a -> b) -> b -> Tree a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> Tree a -> b
foldr' :: (a -> b -> b) -> b -> Tree a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> Tree a -> b
foldr :: (a -> b -> b) -> b -> Tree a -> b
$cfoldr :: forall a b. (a -> b -> b) -> b -> Tree a -> b
foldMap' :: (a -> m) -> Tree a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> Tree a -> m
foldMap :: (a -> m) -> Tree a -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> Tree a -> m
fold :: Tree m -> m
$cfold :: forall m. Monoid m => Tree m -> m
Foldable, Functor Tree
Foldable Tree
Functor Tree
-> Foldable Tree
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Tree a -> f (Tree b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    Tree (f a) -> f (Tree a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Tree a -> m (Tree b))
-> (forall (m :: * -> *) a. Monad m => Tree (m a) -> m (Tree a))
-> Traversable Tree
(a -> f b) -> Tree a -> f (Tree b)
forall (t :: * -> *).
Functor t
-> Foldable t
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a. Monad m => Tree (m a) -> m (Tree a)
forall (f :: * -> *) a. Applicative f => Tree (f a) -> f (Tree a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Tree a -> m (Tree b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Tree a -> f (Tree b)
sequence :: Tree (m a) -> m (Tree a)
$csequence :: forall (m :: * -> *) a. Monad m => Tree (m a) -> m (Tree a)
mapM :: (a -> m b) -> Tree a -> m (Tree b)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Tree a -> m (Tree b)
sequenceA :: Tree (f a) -> f (Tree a)
$csequenceA :: forall (f :: * -> *) a. Applicative f => Tree (f a) -> f (Tree a)
traverse :: (a -> f b) -> Tree a -> f (Tree b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Tree a -> f (Tree b)
$cp2Traversable :: Foldable Tree
$cp1Traversable :: Functor Tree
Traversable)

--------------------------------------------------------------------------------

-- | Construct a forest from a list of trees.
--
-- /@'forest' []@ is equivalent to 'mempty'./
forest :: [Tree a] -> Forest a
forest :: [Tree a] -> Forest a
forest = [Tree a] -> Forest a
forall a. [Tree a] -> Forest a
Forest

-- | Construct a tree with a single root and no subforest.
--
--   /@'leaf' x@ is equivalent to @'tree' x 'mempty'@./
leaf :: a -> Tree a
leaf :: a -> Tree a
leaf a
a = a -> Forest a -> Tree a
forall a. a -> Forest a -> Tree a
tree a
a Forest a
forall a. Monoid a => a
mempty

-- | Construct a forest of depth 1, where each tree contains only a root.
--
-- /'leaves' is equivalent to @'forest' . fmap 'leaf'@/
leaves :: [a] -> Forest a
leaves :: [a] -> Forest a
leaves [a]
xs =
  [Tree a] -> Forest a
forall a. [Tree a] -> Forest a
forest ((a -> Tree a) -> [a] -> [Tree a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> Tree a
forall a. a -> Tree a
leaf [a]
xs)

-- | Construct a tree with a root and subforest.
tree :: a -> Forest a -> Tree a
tree :: a -> Forest a -> Tree a
tree = a -> Forest a -> Tree a
forall a. a -> Forest a -> Tree a
Tree

-- | The tree's immediate subtrees.
--
-- /'subtrees' is equivalent to @'trees' . 'subforest'@./
subtrees :: Tree a -> [Tree a]
subtrees :: Tree a -> [Tree a]
subtrees Tree a
t = Forest a -> [Tree a]
forall a. Forest a -> [Tree a]
trees (Tree a -> Forest a
forall a. Tree a -> Forest a
subforest Tree a
t)

{- | Catamorphism on forests.

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

>>> foldForest (intercalate ", " . fmap (\(a, b) -> [a] <> " [" <> b <> "]")) example
"a [b [], c []], d [e [], f [g []]]"

-}
foldForest :: ([(a, b)] -> b) -> Forest a -> b
foldForest :: ([(a, b)] -> b) -> Forest a -> b
foldForest [(a, b)] -> b
f =
    Forest a -> b
go
  where
    go :: Forest a -> b
go (Forest [Tree a]
ts) = [(a, b)] -> b
f ([(a, b)] -> b) -> [(a, b)] -> b
forall a b. (a -> b) -> a -> b
$ (\Tree a
t -> (Tree a -> a
forall a. Tree a -> a
root Tree a
t, Forest a -> b
go (Tree a -> Forest a
forall a. Tree a -> Forest a
subforest Tree a
t))) (Tree a -> (a, b)) -> [Tree a] -> [(a, b)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [Tree a]
ts

{- | Catamorphism on trees.

>>>
:{
example :: Tree Char
example = tree 'a' $ forest
    [ tree 'b' $ leaves "cd"
    , tree 'e' $ forest
        [ leaf 'f'
        , tree 'g' $ leaves "h"
        ]
   ]
:}

>>> foldTree (\a bs -> [a] <> " [" <> intercalate ", " bs <> "]") example
"a [b [c [], d []], e [f [], g [h []]]]"

-}
foldTree :: (a -> [b] -> b) -> Tree a -> b
foldTree :: (a -> [b] -> b) -> Tree a -> b
foldTree a -> [b] -> b
f =
    Tree a -> b
go
  where
    go :: Tree a -> b
go Tree a
t = a -> [b] -> b
f (Tree a -> a
forall a. Tree a -> a
root Tree a
t) (Tree a -> b
go (Tree a -> b) -> [Tree a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Tree a -> [Tree a]
forall a. Tree a -> [Tree a]
subtrees Tree a
t)


--------------------------------------------------------------------------------

{- $setup

>>> import Prelude
>>> import Data.Char
>>> import Data.Foldable
>>> import Data.Function
>>> import Data.List
>>> import Data.Semigroup

-}

--------------------------------------------------------------------------------

{- $imports

Recommended imports:

> import Data.Forest (Forest, Tree)
> import qualified Data.Forest as 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"
        ]
   ]
:}

>>>
:{
showCharForest f =
    intercalate ", " (showCharTree <$> trees f)
  where
    showCharTree t = case trees (subforest t) of
      []   -> [root t]
      [t'] -> [root t] <> ": " <> showCharTree t'
      _    -> [root t] <> ": (" <> showCharForest (subforest t) <> ")"
:}

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

>>> showCharForest (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"

-}