module Data.Tree.BranchLeaf where

import           Data.Traversable as Traversable(Traversable(traverse))
import           Control.Applicative (Applicative, (<*>), )
import qualified Control.Applicative as App
import qualified Control.Monad as Monad
import qualified Data.List     as List

import Prelude hiding (map, mapM, )


data T branch leaf =
     Branch branch [T branch leaf]
   | Leaf leaf
   deriving (Int -> T branch leaf -> ShowS
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall branch leaf.
(Show branch, Show leaf) =>
Int -> T branch leaf -> ShowS
forall branch leaf.
(Show branch, Show leaf) =>
[T branch leaf] -> ShowS
forall branch leaf.
(Show branch, Show leaf) =>
T branch leaf -> String
showList :: [T branch leaf] -> ShowS
$cshowList :: forall branch leaf.
(Show branch, Show leaf) =>
[T branch leaf] -> ShowS
show :: T branch leaf -> String
$cshow :: forall branch leaf.
(Show branch, Show leaf) =>
T branch leaf -> String
showsPrec :: Int -> T branch leaf -> ShowS
$cshowsPrec :: forall branch leaf.
(Show branch, Show leaf) =>
Int -> T branch leaf -> ShowS
Show)

map :: (branch0 -> branch1)
    -> (leaf0 -> leaf1)
    -> (T branch0 leaf0 -> T branch1 leaf1)
map :: forall branch0 branch1 leaf0 leaf1.
(branch0 -> branch1)
-> (leaf0 -> leaf1) -> T branch0 leaf0 -> T branch1 leaf1
map branch0 -> branch1
branchF leaf0 -> leaf1
leafF = forall branch a leaf.
(branch -> [a] -> a) -> (leaf -> a) -> T branch leaf -> a
fold (forall branch leaf. branch -> [T branch leaf] -> T branch leaf
Branch forall b c a. (b -> c) -> (a -> b) -> a -> c
. branch0 -> branch1
branchF) (forall branch leaf. leaf -> T branch leaf
Leaf forall b c a. (b -> c) -> (a -> b) -> a -> c
. leaf0 -> leaf1
leafF)

mapCond ::
       (branch -> Bool)
    -> (branch -> branch)
    -> (leaf -> leaf)
    -> (T branch leaf -> T branch leaf)
mapCond :: forall branch leaf.
(branch -> Bool)
-> (branch -> branch)
-> (leaf -> leaf)
-> T branch leaf
-> T branch leaf
mapCond branch -> Bool
descend branch -> branch
branchF leaf -> leaf
leafF =
   let recourse :: T branch leaf -> T branch leaf
recourse =
          forall branch leaf a.
(branch -> [T branch leaf] -> a)
-> (leaf -> a) -> T branch leaf -> a
switch
             (\branch
branch -> forall branch leaf. branch -> [T branch leaf] -> T branch leaf
Branch (branch -> branch
branchF branch
branch) forall b c a. (b -> c) -> (a -> b) -> a -> c
.
                if branch -> Bool
descend branch
branch
                   then forall a b. (a -> b) -> [a] -> [b]
List.map T branch leaf -> T branch leaf
recourse
                   else forall a. a -> a
id)
             (forall branch leaf. leaf -> T branch leaf
Leaf forall b c a. (b -> c) -> (a -> b) -> a -> c
. leaf -> leaf
leafF)
   in  T branch leaf -> T branch leaf
recourse

fold :: (branch -> [a] -> a)
     -> (leaf -> a)
     -> (T branch leaf -> a)
fold :: forall branch a leaf.
(branch -> [a] -> a) -> (leaf -> a) -> T branch leaf -> a
fold branch -> [a] -> a
branchF leaf -> a
leafF =
   let recourse :: T branch leaf -> a
recourse =
          forall branch leaf a.
(branch -> [T branch leaf] -> a)
-> (leaf -> a) -> T branch leaf -> a
switch (\branch
x -> branch -> [a] -> a
branchF branch
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
List.map T branch leaf -> a
recourse) leaf -> a
leafF
   in  T branch leaf -> a
recourse

switch ::
        (branch -> [T branch leaf] -> a)
     -> (leaf -> a)
     -> (T branch leaf -> a)
switch :: forall branch leaf a.
(branch -> [T branch leaf] -> a)
-> (leaf -> a) -> T branch leaf -> a
switch branch -> [T branch leaf] -> a
branchF leaf -> a
_ (Branch branch
x [T branch leaf]
subTrees) = branch -> [T branch leaf] -> a
branchF branch
x [T branch leaf]
subTrees
switch branch -> [T branch leaf] -> a
_ leaf -> a
leafF (Leaf leaf
x)          = leaf -> a
leafF leaf
x

allSubTrees :: T branch leaf -> [T branch leaf]
allSubTrees :: forall branch leaf. T branch leaf -> [T branch leaf]
allSubTrees T branch leaf
tree =
   T branch leaf
tree forall a. a -> [a] -> [a]
:
   forall branch leaf a.
(branch -> [T branch leaf] -> a)
-> (leaf -> a) -> T branch leaf -> a
switch (forall a b. a -> b -> a
const (forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap forall branch leaf. T branch leaf -> [T branch leaf]
allSubTrees)) (forall a b. a -> b -> a
const []) T branch leaf
tree



mapA :: Applicative m =>
       (branch0 -> m branch1)
    -> (leaf0 -> m leaf1)
    -> (T branch0 leaf0 -> m (T branch1 leaf1))
mapA :: forall (m :: * -> *) branch0 branch1 leaf0 leaf1.
Applicative m =>
(branch0 -> m branch1)
-> (leaf0 -> m leaf1) -> T branch0 leaf0 -> m (T branch1 leaf1)
mapA branch0 -> m branch1
branchF leaf0 -> m leaf1
leafF =
   forall (m :: * -> *) branch a leaf.
Applicative m =>
(branch -> m ([a] -> a)) -> (leaf -> m a) -> T branch leaf -> m a
foldA
      (forall (f :: * -> *) a b. Applicative f => (a -> b) -> f a -> f b
App.liftA forall branch leaf. branch -> [T branch leaf] -> T branch leaf
Branch forall b c a. (b -> c) -> (a -> b) -> a -> c
. branch0 -> m branch1
branchF)
      (forall (f :: * -> *) a b. Applicative f => (a -> b) -> f a -> f b
App.liftA forall branch leaf. leaf -> T branch leaf
Leaf forall b c a. (b -> c) -> (a -> b) -> a -> c
. leaf0 -> m leaf1
leafF)

foldA :: Applicative m =>
        (branch -> m ([a] -> a))
     -> (leaf -> m a)
     -> (T branch leaf -> m a)
foldA :: forall (m :: * -> *) branch a leaf.
Applicative m =>
(branch -> m ([a] -> a)) -> (leaf -> m a) -> T branch leaf -> m a
foldA branch -> m ([a] -> a)
branchF leaf -> m a
leafF =
   let recourse :: T branch leaf -> m a
recourse =
          forall branch leaf a.
(branch -> [T branch leaf] -> a)
-> (leaf -> a) -> T branch leaf -> a
switch (\branch
x [T branch leaf]
subTrees ->
                        branch -> m ([a] -> a)
branchF branch
x forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse T branch leaf -> m a
recourse [T branch leaf]
subTrees)
                   leaf -> m a
leafF
   in  T branch leaf -> m a
recourse

foldM :: Monad m =>
        (branch -> [a] -> m a)
     -> (leaf -> m a)
     -> (T branch leaf -> m a)
foldM :: forall (m :: * -> *) branch a leaf.
Monad m =>
(branch -> [a] -> m a) -> (leaf -> m a) -> T branch leaf -> m a
foldM branch -> [a] -> m a
branchF leaf -> m a
leafF =
   let recourse :: T branch leaf -> m a
recourse =
          forall branch leaf a.
(branch -> [T branch leaf] -> a)
-> (leaf -> a) -> T branch leaf -> a
switch (\branch
x [T branch leaf]
subTrees ->
                        branch -> [a] -> m a
branchF branch
x forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
Monad.mapM T branch leaf -> m a
recourse [T branch leaf]
subTrees)
                   leaf -> m a
leafF
   in  T branch leaf -> m a
recourse