module BishBosh.Data.RoseTree(
IsMatch,
countTerminalNodes,
drawTree,
drawForest,
traceRoute,
promote,
reduce,
mapForest
) where
import qualified Data.List
import qualified Data.Tree
countTerminalNodes :: Num nodes => Data.Tree.Tree a -> nodes
countTerminalNodes :: Tree a -> nodes
countTerminalNodes = nodes -> Tree a -> nodes
forall b a. Num b => b -> Tree a -> b
go nodes
0 where
go :: b -> Tree a -> b
go b
acc Data.Tree.Node { subForest :: forall a. Tree a -> Forest a
Data.Tree.subForest = [] } = b
acc b -> b -> b
forall a. Num a => a -> a -> a
+ b
1
go b
acc Data.Tree.Node { subForest :: forall a. Tree a -> Forest a
Data.Tree.subForest = [Tree a]
forest } = (b -> Tree a -> b) -> b -> [Tree a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Data.List.foldl' b -> Tree a -> b
go b
acc [Tree a]
forest
drawTree :: (a -> String) -> Data.Tree.Tree a -> String
drawTree :: (a -> String) -> Tree a -> String
drawTree a -> String
toString = Tree String -> String
Data.Tree.drawTree (Tree String -> String)
-> (Tree a -> Tree String) -> Tree a -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> String) -> Tree a -> Tree String
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> String
toString
drawForest :: (a -> String) -> Data.Tree.Forest a -> String
drawForest :: (a -> String) -> Forest a -> String
drawForest a -> String
toString = Forest String -> String
Data.Tree.drawForest (Forest String -> String)
-> (Forest a -> Forest String) -> Forest a -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Tree a -> Tree String) -> Forest a -> Forest String
forall a b. (a -> b) -> [a] -> [b]
map ((a -> String) -> Tree a -> Tree String
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> String
toString)
type IsMatch a = a -> Bool
traceRoute
:: (datum -> IsMatch a)
-> Data.Tree.Tree a
-> [datum]
-> Maybe [a]
traceRoute :: (datum -> IsMatch a) -> Tree a -> [datum] -> Maybe [a]
traceRoute datum -> IsMatch a
isMatch = Forest a -> [datum] -> Maybe [a]
slave (Forest a -> [datum] -> Maybe [a])
-> (Tree a -> Forest a) -> Tree a -> [datum] -> Maybe [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Tree a -> Forest a
forall a. Tree a -> Forest a
Data.Tree.subForest where
slave :: Forest a -> [datum] -> Maybe [a]
slave Forest a
forest (datum
datum : [datum]
remainingData) = (Tree a -> Bool) -> Forest a -> Maybe (Tree a)
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Maybe a
Data.List.find (
datum -> IsMatch a
isMatch datum
datum IsMatch a -> (Tree a -> a) -> Tree a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Tree a -> a
forall a. Tree a -> a
Data.Tree.rootLabel
) Forest a
forest Maybe (Tree a) -> (Tree a -> Maybe [a]) -> Maybe [a]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (
\Data.Tree.Node {
rootLabel :: forall a. Tree a -> a
Data.Tree.rootLabel = a
rootLabel,
subForest :: forall a. Tree a -> Forest a
Data.Tree.subForest = Forest a
subForest
} -> (a
rootLabel a -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([a] -> [a]) -> Maybe [a] -> Maybe [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` Forest a -> [datum] -> Maybe [a]
slave Forest a
subForest [datum]
remainingData
)
slave Forest a
_ [datum]
_ = [a] -> Maybe [a]
forall a. a -> Maybe a
Just []
promote
:: (datum -> IsMatch a)
-> [datum]
-> [Data.Tree.Tree a]
-> Maybe [Data.Tree.Tree a]
promote :: (datum -> IsMatch a) -> [datum] -> [Tree a] -> Maybe [Tree a]
promote datum -> IsMatch a
isMatch = [datum] -> [Tree a] -> Maybe [Tree a]
slave where
slave :: [datum] -> [Tree a] -> Maybe [Tree a]
slave (datum
datum : [datum]
remainingData) [Tree a]
forest = case (Tree a -> Bool) -> [Tree a] -> ([Tree a], [Tree a])
forall a. (a -> Bool) -> [a] -> ([a], [a])
break (datum -> IsMatch a
isMatch datum
datum IsMatch a -> (Tree a -> a) -> Tree a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Tree a -> a
forall a. Tree a -> a
Data.Tree.rootLabel) [Tree a]
forest of
([Tree a]
mismatches, match :: Tree a
match@Data.Tree.Node { subForest :: forall a. Tree a -> Forest a
Data.Tree.subForest = [Tree a]
forest' } : [Tree a]
remainingNodes) -> (
\[Tree a]
forest'' -> Tree a
match {
subForest :: [Tree a]
Data.Tree.subForest = [Tree a]
forest''
} Tree a -> [Tree a] -> [Tree a]
forall a. a -> [a] -> [a]
: [Tree a]
mismatches [Tree a] -> [Tree a] -> [Tree a]
forall a. [a] -> [a] -> [a]
++ [Tree a]
remainingNodes
) ([Tree a] -> [Tree a]) -> Maybe [Tree a] -> Maybe [Tree a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` [datum] -> [Tree a] -> Maybe [Tree a]
slave [datum]
remainingData [Tree a]
forest'
([Tree a], [Tree a])
_ -> Maybe [Tree a]
forall a. Maybe a
Nothing
slave [datum]
_ [Tree a]
forest = [Tree a] -> Maybe [Tree a]
forall a. a -> Maybe a
Just [Tree a]
forest
reduce
:: IsMatch a
-> Data.Tree.Tree a
-> Maybe (Data.Tree.Tree a)
reduce :: IsMatch a -> Tree a -> Maybe (Tree a)
reduce IsMatch a
isMatch Data.Tree.Node { subForest :: forall a. Tree a -> Forest a
Data.Tree.subForest = Forest a
subForest } = (Tree a -> Bool) -> Forest a -> Maybe (Tree a)
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Maybe a
Data.List.find (IsMatch a
isMatch IsMatch a -> (Tree a -> a) -> Tree a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Tree a -> a
forall a. Tree a -> a
Data.Tree.rootLabel) Forest a
subForest
type Transformation a = Data.Tree.Tree a -> Data.Tree.Tree a
mapForest :: (a -> Data.Tree.Forest a -> Data.Tree.Forest a) -> Transformation a
mapForest :: (a -> Forest a -> Forest a) -> Transformation a
mapForest a -> Forest a -> Forest a
f = Transformation a
slave where
slave :: Transformation a
slave node :: Tree a
node@Data.Tree.Node {
rootLabel :: forall a. Tree a -> a
Data.Tree.rootLabel = a
label,
subForest :: forall a. Tree a -> Forest a
Data.Tree.subForest = Forest a
forest
} = Tree a
node { subForest :: Forest a
Data.Tree.subForest = Transformation a -> Forest a -> Forest a
forall a b. (a -> b) -> [a] -> [b]
map Transformation a
slave (Forest a -> Forest a) -> Forest a -> Forest a
forall a b. (a -> b) -> a -> b
$ a -> Forest a -> Forest a
f a
label Forest a
forest }