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