module Data.Forest
(
Forest,
Tree,
forest,
tree,
leaf,
leaves,
trees,
root,
subforest,
subtrees,
foldForest,
foldTree,
)
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)
newtype Forest a = 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)
data Tree a = Tree
{
forall a. Tree a -> a
root :: a,
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)
forest :: [Tree a] -> Forest a
forest :: forall a. [Tree a] -> Forest a
forest = forall a. [Tree a] -> Forest a
Forest
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
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)
tree :: a -> Forest a -> Tree a
tree :: forall a. a -> Forest a -> Tree a
tree = forall a. a -> Forest a -> Tree a
Tree
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)
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
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)