    -- (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
    -}