-- | Multi-way trees (also known as /rose trees/) and forests,
-- similar to @Data.Tree@ from the /containers/ library.
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
  { -- | The trees that constitute the forest.
    forall a. Forest a -> [Tree a]
trees :: [Tree a]
  }
  deriving (Forest a -> Forest a -> Bool
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
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, 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
<$ :: forall a b. a -> Forest b -> Forest a
$c<$ :: forall a b. a -> Forest b -> Forest a
fmap :: forall a b. (a -> b) -> Forest a -> Forest b
$cfmap :: forall a b. (a -> b) -> Forest a -> Forest b
Functor, 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 :: forall a. Num a => Forest a -> a
$cproduct :: forall a. Num a => Forest a -> a
sum :: forall a. Num a => Forest a -> a
$csum :: forall a. Num a => Forest a -> a
minimum :: forall a. Ord a => Forest a -> a
$cminimum :: forall a. Ord a => Forest a -> a
maximum :: forall a. Ord a => Forest a -> a
$cmaximum :: forall a. Ord a => Forest a -> a
elem :: forall a. Eq a => a -> Forest a -> Bool
$celem :: forall a. Eq a => a -> Forest a -> Bool
length :: forall a. Forest a -> Int
$clength :: forall a. Forest a -> Int
null :: forall a. Forest a -> Bool
$cnull :: forall a. Forest a -> Bool
toList :: forall a. Forest a -> [a]
$ctoList :: forall a. Forest a -> [a]
foldl1 :: forall a. (a -> a -> a) -> Forest a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> Forest a -> a
foldr1 :: forall a. (a -> a -> a) -> Forest a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> Forest a -> a
foldl' :: forall b a. (b -> a -> b) -> b -> Forest a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> Forest a -> b
foldl :: forall b a. (b -> a -> b) -> b -> Forest a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> Forest a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> Forest a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> Forest a -> b
foldr :: forall a b. (a -> b -> b) -> b -> Forest a -> b
$cfoldr :: forall a b. (a -> b -> b) -> b -> Forest a -> b
foldMap' :: forall m a. Monoid m => (a -> m) -> Forest a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> Forest a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> Forest a -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> Forest a -> m
fold :: forall m. Monoid m => Forest m -> m
$cfold :: forall m. Monoid m => Forest m -> m
Foldable, Functor Forest
Foldable Forest
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 :: forall (m :: * -> *) a. Monad m => Forest (m a) -> m (Forest a)
$csequence :: forall (m :: * -> *) a. Monad m => Forest (m a) -> m (Forest a)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Forest a -> m (Forest b)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Forest a -> m (Forest b)
sequenceA :: forall (f :: * -> *) a.
Applicative f =>
Forest (f a) -> f (Forest a)
$csequenceA :: forall (f :: * -> *) a.
Applicative f =>
Forest (f a) -> f (Forest a)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Forest a -> f (Forest b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Forest a -> f (Forest b)
Traversable, NonEmpty (Forest a) -> Forest a
Forest a -> Forest a -> 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 :: forall b. Integral b => 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, 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
Monoid)

-- | A tree is defined completely by its 'root' and its 'subforest'.
--
-- To construct a tree, use 'tree' or 'leaf'.
data Tree a = Tree
  { -- | The value at the root node of the tree.
    forall a. Tree a -> a
root :: a,
    -- | The forest containing all descendants
    --   of the tree's 'root'.
    forall a. Tree a -> Forest a
subforest :: Forest a
  }
  deriving (Tree a -> Tree a -> Bool
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
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, 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
<$ :: forall a b. a -> Tree b -> Tree a
$c<$ :: forall a b. a -> Tree b -> Tree a
fmap :: forall a b. (a -> b) -> Tree a -> Tree b
$cfmap :: forall a b. (a -> b) -> Tree a -> Tree b
Functor, 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 :: forall a. Num a => Tree a -> a
$cproduct :: forall a. Num a => Tree a -> a
sum :: forall a. Num a => Tree a -> a
$csum :: forall a. Num a => Tree a -> a
minimum :: forall a. Ord a => Tree a -> a
$cminimum :: forall a. Ord a => Tree a -> a
maximum :: forall a. Ord a => Tree a -> a
$cmaximum :: forall a. Ord a => Tree a -> a
elem :: forall a. Eq a => a -> Tree a -> Bool
$celem :: forall a. Eq a => a -> Tree a -> Bool
length :: forall a. Tree a -> Int
$clength :: forall a. Tree a -> Int
null :: forall a. Tree a -> Bool
$cnull :: forall a. Tree a -> Bool
toList :: forall a. Tree a -> [a]
$ctoList :: forall a. Tree a -> [a]
foldl1 :: forall a. (a -> a -> a) -> Tree a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> Tree a -> a
foldr1 :: forall a. (a -> a -> a) -> Tree a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> Tree a -> a
foldl' :: forall b a. (b -> a -> b) -> b -> Tree a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> Tree a -> b
foldl :: forall b a. (b -> a -> b) -> b -> Tree a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> Tree a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> Tree a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> Tree a -> b
foldr :: forall a b. (a -> b -> b) -> b -> Tree a -> b
$cfoldr :: forall a b. (a -> b -> b) -> b -> Tree a -> b
foldMap' :: forall m a. Monoid m => (a -> m) -> Tree a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> Tree a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> Tree a -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> Tree a -> m
fold :: forall m. Monoid m => Tree m -> m
$cfold :: forall m. Monoid m => Tree m -> m
Foldable, Functor Tree
Foldable Tree
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 :: forall (m :: * -> *) a. Monad m => Tree (m a) -> m (Tree a)
$csequence :: forall (m :: * -> *) a. Monad m => Tree (m a) -> m (Tree a)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Tree a -> m (Tree b)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Tree a -> m (Tree b)
sequenceA :: forall (f :: * -> *) a. Applicative f => Tree (f a) -> f (Tree a)
$csequenceA :: forall (f :: * -> *) a. Applicative f => Tree (f a) -> f (Tree a)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Tree a -> f (Tree b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Tree a -> f (Tree b)
Traversable)

-- | Construct a forest from a list of trees.
--
-- /@'forest' []@ is equivalent to 'mempty'./
forest :: [Tree a] -> Forest a
forest :: forall a. [Tree a] -> Forest a
forest = 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 :: forall a. a -> Tree a
leaf a
a = forall a. a -> Forest a -> Tree a
tree a
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 :: forall a. [a] -> Forest a
leaves [a]
xs =
  forall a. [Tree a] -> Forest a
forest (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. a -> Tree a
leaf [a]
xs)

-- | Construct a tree with a root and subforest.
tree :: a -> Forest a -> Tree a
tree :: forall a. a -> Forest a -> Tree a
tree = 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 :: forall a. Tree a -> [Tree a]
subtrees Tree a
t = forall a. Forest a -> [Tree a]
trees (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 :: forall a b. ([(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 forall a b. (a -> b) -> a -> b
$ (\Tree a
t -> (forall a. Tree a -> a
root Tree a
t, Forest a -> b
go (forall a. Tree a -> Forest a
subforest Tree a
t))) 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 :: forall a b. (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 (forall a. Tree a -> a
root Tree a
t) (Tree a -> b
go forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> 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"