haskell - Using Monad/ST for non-concurrent message passing in a mutable graph -

i trying work out data structure following situation.

graph structure

i plan have graph of nodes un-weighted, directed edges: graph = [node]

each node has:

1. some tbd internal (persistent) state
2. a queue of incoming messages
3. a type of message can send determined function accepts current node state (with possibility of failure)
4. a list of edges

node { nodestate :: nodestate, inbox :: queue nodemessage, nodemessage :: (nodestate -> maybe nodemessage), connections::[nodeedge] }

each edge intermediary step capturing pending messages target node

nodeedge { pendingmessage:: maybe nodemessage, targetnode :: node }

message passing

the message passing happens in phases , not-conccurent (though queues may processed in parallel reduce computation time).

• phase 1: check inbox of every node, processing messages , updating nodestate if relevant.
• phase 2: have every node run nodemessage, if results in just nodemessage, send nodemessage every connection ([nodeedge])
• phase 3: check every node edge, if has message, add target node's message queue.

monat/st

my original plan assign every node id (probably simple int) , store each node in map int node. haven't tried st monad before figured use st s (m.map int node). given phase each node's message send activity processed in o(k log n).

on other hand if nodes/edges able update mutable state of edges/nodes single queue processed in o(k).

while st/map method seems intuitive, having whole graph mutable beyond me.

any suggestions / tips / recommended reading?

i not going mark answer correct because not answer question. solution i'm going with.

because number of nodes in graph never going change realised use array. i'm reconsidering using mutable datatype - though simpler workflow updating array less benefits of laziness , end writing ton of imperative style code. i'm thinking using array , state monad, rather st.

here bit of test code wrote, using starray. "proper" answer question similar data type graphs - perhaps out there stgraph library?

anyway - here example code using starray:

import control.monad.st import data.array.st import data.array  import qualified data.dequeue dq  type id = int  data node = node {     nodeid :: id,     nodestate :: nodestate,     nodeinbox :: dq.bankersdequeue nodemessage,     nodemessage :: (nodestate -> maybe nodemessage),     connections :: [nodeedge] }  instance show node     show x = "node: " ++ (show . nodeid $ x) ++ " :: inbox: " ++ (show . nodeinbox $ x) ++ " :: " ++ (show . connections $ x)  data nodeedge = nodeedge { pendingmessage:: maybe nodemessage, targetnode :: id } deriving show  data nodestate = nodestate { statelevel :: int } deriving show  data nodemessage = nodemessage { value :: int } deriving show  es = [[nodeedge nothing 1,nodeedge nothing 2],[nodeedge nothing 0,nodeedge nothing 2],[nodeedge nothing 0,nodeedge nothing 1]] ns = take 3 $ map (\x -> node x (nodestate 0) (dq.fromlist []) (\_ -> nothing) (es !! x)) $ [0,1..]  testarray :: array int node testarray = listarray (0,2) ns  teststarr =  arr <- newlistarray (0,2) ns :: st s (starray s int node)                 <- readarray arr 1                 let = targetnode . head $ connections                 b <- readarray arr                 let m = nodemessage 2                     ms = dq.pushback (nodeinbox b) m                     b' = b { nodeinbox = ms }                 writearray arr (nodeid b) b'                 return arr  teststarr' x = <- readarray x 0                   return  bp = teststarr >>= teststarr'  main =             print $ runst bp              return ()