{-# LANGUAGE DeriveFoldable, DeriveFunctor, DeriveTraversable,
GeneralizedNewtypeDeriving #-}
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
{ Forest a -> [Tree a]
trees :: [Tree a]
}
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)
data Tree a = Tree
{ Tree a -> a
root :: a
, Tree a -> Forest a
subforest :: Forest a
}
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)
forest :: [Tree a] -> Forest a
forest :: [Tree a] -> Forest a
forest = [Tree a] -> Forest a
forall a. [Tree a] -> Forest a
Forest
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
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)
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
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)
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
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)