-- (c) 1999 by Martin Erwig
-- | Threading Combinators.
module Data.Graph.Inductive.Internal.Thread(
-- * Types
Split, SplitM, Thread, Collect,
-- * Operations
threadList', threadList, threadMaybe', threadMaybe, splitPar, splitParM
) where
-- import Graph
-- import GraphData
-- import qualified Diet as D
-- import ADT
----------------------------------------------------------------------
-- CLASSES AND TYPES
----------------------------------------------------------------------
{-
class Thread t a b where
split :: a -> t -> (b,t)
instance Thread (Graph a b) Node (MContext a b) where
split = match
instance (D.Discrete a) => Thread (D.Diet a) a a where
split x s = (x,D.delete x s)
-}
{-
Make clear different notions:
"thread" = data structure + split operation
... = threadable data structure
... = split operation
-}
----------------------------------------------------------------------
-- THREAD COMBINATORS
----------------------------------------------------------------------
-- (A) split along a list of indexes and thread data structure
--
-- there are different ways to consume the returned elements:
{-
-- (1) simple collect in a list
--
foldT1' ys [] d = ys
foldT1' ys (x:xs) d = foldT1' (y:ys) xs d' where (y,d') = split x d
foldT1 xs d = foldT1' [] xs d
-- (2) combine by a function
--
foldT2' f ys [] d = ys
foldT2' f ys (x:xs) d = foldT2' f (f y ys) xs d' where (y,d') = split x d
foldT2 f u xs d = foldT2' f u xs d
-}
-- Mnemonics:
--
-- t : thread type
-- i : index type
-- r : result type
-- c : collection type
--
type Split t i r = i -> t -> (r,t)
type Thread t i r = (t,Split t i r)
type Collect r c = (r -> c -> c,c)
-- (3) abstract from split
--
threadList' :: Collect r c -> Split t i r -> [i] -> t -> (c,t)
threadList' (_,c) _ [] t = (c,t)
threadList' (f,c) split (i:is) t = threadList' (f,f r c) split is t'
where (r,t') = split i t
{-
Note: threadList' works top-down (or, from left),
whereas dfs,gfold,... have been defined bottom-up (or from right).
==> therefore, we define a correpsonding operator for folding
bottom-up/from right.
-}
threadList :: Collect r c -> Split t i r -> [i] -> t -> (c,t)
threadList (_,c) _ [] t = (c,t)
threadList (f,c) split (i:is) t = (f r c',t'')
where (r,t') = split i t
(c',t'') = threadList (f,c) split is t'
-- (B) thread "maybes", ie, apply f to Just-values and continue
-- threading with "continuation" c, and ignore Nothing-values, ie,
-- stop threading and return current data structure.
--
-- threadMaybe' :: (r -> b) -> Split t i r -> (e -> f -> (Maybe i,t))
-- -> e -> f -> (Maybe b,t)
type SplitM t i r = Split t i (Maybe r)
threadMaybe' :: (r->a)->Split t i r->Split t j (Maybe i)->Split t j (Maybe a)
threadMaybe' f cont split j t =
case mi of Just i -> (Just (f r),t'') where (r,t'') = cont i t'
Nothing -> (Nothing,t')
where (mi,t') = split j t
-- extension: grant f access also to y, the result of split.
--
-- threadMaybe :: (a -> b -> c) -> (a -> d -> (b,d)) -> (e -> f -> (Maybe a,d))
-- -> e -> f -> (Maybe c,d)
-- threadMaybe :: (i->r->a)->Split t i r->Split t j (Maybe i)->Split t j (Maybe a)
threadMaybe :: (i -> r -> a) -> Split t i r -> SplitM t j i -> SplitM t j a
threadMaybe f cont split j t =
case mi of Just i -> (Just (f i r),t'') where (r,t'') = cont i t'
Nothing -> (Nothing,t')
where (mi,t') = split j t
-- (C) compose splits in parallel (is a kind of generalized zip)
--
-- splitPar :: (a -> b -> (c,d)) -> (e -> f -> (g,h))
-- -> (a,e) -> (b,f) -> ((c,g),(d,h))
splitPar :: Split t i r -> Split u j s -> Split (t,u) (i,j) (r,s)
splitPar split split' (i,j) (t,u) = ((r,s),(t',u'))
where (r,t') = split i t
(s,u') = split' j u
splitParM :: SplitM t i r -> Split u j s -> SplitM (t,u) (i,j) (r,s)
splitParM splitm split (i,j) (t,u) =
case mr of Just r -> (Just (r,s),(t',u'))
Nothing -> (Nothing,(t',u)) -- ignore 2nd split
where (mr,t') = splitm i t
(s,u') = split j u
-- (D) merge a thread with/into a computation
--
{-
Example: assign consecutive numbers to the nodes of a tree
Input: type d, thread (t,split), fold operation on d
-}