Types/Data/Graph.hs

   1 {-# LANGUAGE
   2   EmptyDataDecls,
   3   TypeFamilies,
   4   UndecidableInstances
   5   #-}
   6 module Types.Data.Graph
   7     ( Context
   8     , Decomp
   9     , LNode
  10     , LPath
  11     , Graph
  12
  13     , Empty
  14     , IsEmpty
  15
  16     , Match
  17     )
  18     where
  19
  20 import qualified Types.Data.List     as L
  21 import qualified Types.Data.List.Ops as L
  22 import qualified Types.Data.Map      as M
  23
  24 import Types.Data.Bool
  25 import Types.Data.Maybe
  26
  27
  28 -- preNodes, sucNodes: map from node ID to edge label
  29 data Context preNodes nodeID nodeLabel sucNodes
  30
  31 -- nodeMap: map from node ID to context
  32 data Graph nodeMap
  33
  34 -- mContext: Maybe Context
  35 data Decomp mContext graph
  36
  37 -- nodeID: natural number
  38 data LNode nodeID nodeLabel
  39
  40 -- lNodes: list of LNode
  41 data LPath lNodes
  42
  43 -- Empty
  44 type Empty = Graph M.Empty
  45
  46 -- IsEmpty
  47 type family   IsEmpty g
  48 type instance IsEmpty (Graph m) = M.Null m
  49
  50 -- Match
  51 type Match node g = Match' (M.Lookup node g) node g
  52
  53 type family   Match' mContext node g
  54 type instance Match' Nothing                          node g = Decomp Nothing g
  55 type instance Match' (Just (Context p node' label s)) node g
  56     = Decomp (Just (Context (M.Delete node p)
  57                             node
  58                             label
  59                             (M.Delete node s)))
  60              (ClearSucc (ClearPred (M.Delete node g)
  61                                    node
  62                                    (M.Keys (M.Delete node s)))
  63                         node
  64                         (M.Keys (M.Delete node p)))
  65
  66 -- ClearSucc
  67 type family   ClearSucc g n ns
  68 type instance ClearSucc g n L.Null        = g
  69 type instance ClearSucc g n (L.Cons s ss)
  70     = ClearSucc (M.Adjust (ClearSucc' n) s g) n ss
  71
  72 data ClearSucc' n
  73 type instance L.App (ClearSucc' n) (Context ps n' l ss)
  74     = Context ps n' l (M.Delete n ss)
  75
  76 -- ClearPred
  77 type family   ClearPred g n ns
  78 type instance ClearPred g n L.Null        = g
  79 type instance ClearPred g n (L.Cons p ps)
  80     = ClearPred (M.Adjust (ClearPred' n) p g) n ps
  81
  82 data ClearPred' n
  83 type instance L.App (ClearPred' n) (Context ps n' l ss)
  84     = Context (M.Delete n ps) n' l ss