将Monad / ST用于可变图中的非并发消息传递

本文介绍了将Monad / ST用于可变图中的非并发消息传递的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 我试图为以下情况制定数据结构。 图表结构 我计划使用未加权的有向边的节点图： Graph = [Node] 每个节点都有： 某些待定内部（持久）状态 传入消息队列 它可以发送的消息类型由接受当前节点状态（可能失败）的函数确定 边缘列表 节点{nodeState :: NodeState，inbox :: Queue NodeMessage， nodeMessage ::（NodeState-> Maybe NodeMessage），connections :: [NodeEdge]} 每个边是捕获未决消息的中间步骤对于目标节点 NodeEdge {pendingMessage :: Maybe NodeMessage，targetNode :: Node} 消息传递 消息传递分阶段发生并且不是concurednt（尽管可以并行处理队列以减少计算时间）。 阶段1：检查每个节点的收件箱，处理任何消息并更新 NodeState （如果相关）。 阶段2：让每个节点都运行，则将NodeMessage发送到每个连接（ [NodeEdge] 阶段3：检查每个节点边缘，如果它有消息，则将其添加到目标节点的消息队列中。 ul> Monat / ST 我的原始计划是为每个节点分配一个ID一个简单的Int）并将每个节点存储在一个Map Int节点中。我之前没有试过ST Monad，但我想我可以使用类似于 ST s（M.Map Int Node）的东西。对于任何给定的阶段，每个节点的消息发送活动可以在O（k log N）中处理。另一方面，如果节点/边缘能够更新可变状态他们的边缘/节点，那么任何单个队列都可以在O（k）中处理。 虽然ST / Map方法看起来相当直观，但整个图形可变是超出了我的范围。 任何建议/提示/推荐阅读？ 我不打算标记这个答案是正确的，因为它没有真正回答这个问题。然而，这是我的解决方案。 因为我图中的节点数永远不会改变，我意识到我可以使用一个数组。我实际上正在重新考虑使用可变数据类型 - 尽管我得到了一个更简单的工作流程来更新数组，我得到的懒惰的好处更少，并且我最终编写了大量的命令式样代码。我实际上正在考虑使用Array和State Monad，而不是ST。 以下是我使用STArray编写的一些测试代码。这个问题的适当的答案应该是一个专门用于Graph的类似数据类型 - 也许有一个STGraph库？ 无论如何 - 这里是使用STArray的示例代码： import Control.Monad.ST import Data.Array.ST import Data.Array 将限定的Data.Dequeue导入为DQ 类型Id = Int data Node = Node { nodeId :: Id， nodeState :: NodeState， nodeInbox :: DQ.BankersDequeue NodeMessage， nodeMessage ::（NodeState - >也许NodeMessage）， connections :: [NodeEdge]} 实例显示节点 show x =Node：++（show。nodeId $ x）++:: Inbox：++（show。nodeInbox $ x）++:: ++（show。connections $ x） data NodeEdge = NodeEdge {pendingMessage :: Maybe NodeMessage，targetNode :: Id}派生Show data NodeState = NodeState {stateLevel :: Int}派生Show data NodeMessage = NodeMessage {v alue :: Int}派生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 - >节点x（NodeState 0）（DQ.fromList []）（\_-&> Nothing）（es !! x））$ [0,1 ..] testArray :: Array Int节点 testArray = listArray（0,2）ns testSTarr = do arr a < - readArray arr 1 let i = targetNode。头$连接a b< - readArray arr i let m = NodeMessage 2 ms = DQ.pushBack（nodeInbox b）m b'= b {nodeInbox = ms} writeArray arr（nodeId b）b'返回arr testSTarr'x =做一个< - readArray x 0 返回a bp = testSTarr>> = testSTarr' main = do print $ runST bp return（） I am trying to work out a data structure for the following situation.Graph StructureI plan to have a graph of nodes with un-weighted, directed edges: Graph = [Node]Each node has:Some TBD internal (persistent) stateA queue of incoming messagesA type of message it can send determined by a function that acceptsthe current node state (with the possibility of failure)A list of edgesNode { nodeState :: NodeState, inbox :: Queue NodeMessage, nodeMessage :: (NodeState -> Maybe NodeMessage), connections::[NodeEdge] }Each edge is an intermediary step capturing pending messages for a target nodeNodeEdge { pendingMessage:: Maybe NodeMessage, targetNode :: Node }Message PassingThe message passing happens in phases and is not-conccurent (though the queues may be processed in parallel to reduce computation time).Phase 1: Check the inbox of every node, processing any messages and updating the NodeState if relevant.Phase 2: Have every node run nodeMessage, if this results in Just NodeMessage, send NodeMessage to every connection ([NodeEdge])Phase 3: Check every node edge, if it has a message, add it to the target node's message queue.Monat/STMy original plan was to assign every node an ID (probably a simple Int) and store each node in a Map Int Node. I haven't tried the ST Monad before but I figured I could use something like ST s (M.Map Int Node). For any given phase each node's message send activity could be processed in O(k log N).On the other hand if nodes/edges were able to update the mutable state of their edges/nodes then any single queue could be processed in O(k). While the ST/Map method seems fairly intuitive, having the whole graph mutable is beyond me.Any suggestions / tips / recommended reading? 解决方案 I am not going to mark this answer as correct because it does not truly answer the question. However it is the solution that I'm going with.Because the number of nodes in my graph is never going to change I realised I could use an array. I'm actually reconsidering using a mutable datatype - even though I get a much simpler workflow updating the array I get less benefits of laziness and I end up writing a ton of imperative style code. I'm actually thinking about using an Array and the State Monad, rather than ST.Here is a bit of test code I wrote, using STArray. A "proper" answer to this question would be a similar data type specifically for Graphs - perhaps out there is an STGraph library?Anyway - here is the example code using STArray:import Control.Monad.STimport Data.Array.STimport Data.Arrayimport qualified Data.Dequeue as DQtype Id = Intdata Node = Node { nodeId :: Id, nodeState :: NodeState, nodeInbox :: DQ.BankersDequeue NodeMessage, nodeMessage :: (NodeState -> Maybe NodeMessage), connections :: [NodeEdge] }instance Show Node where show x = "Node: " ++ (show . nodeId $ x) ++ " :: Inbox: " ++ (show . nodeInbox $ x) ++ " :: " ++ (show . connections $ x)data NodeEdge = NodeEdge { pendingMessage:: Maybe NodeMessage, targetNode :: Id } deriving Showdata NodeState = NodeState { stateLevel :: Int } deriving Showdata NodeMessage = NodeMessage { value :: Int } deriving Showes = [[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 NodetestArray = listArray (0,2) nstestSTarr = do arr <- newListArray (0,2) ns :: ST s (STArray s Int Node) a <- readArray arr 1 let i = targetNode . head $ connections a b <- readArray arr i let m = NodeMessage 2 ms = DQ.pushBack (nodeInbox b) m b' = b { nodeInbox = ms } writeArray arr (nodeId b) b' return arrtestSTarr' x = do a <- readArray x 0 return abp = testSTarr >>= testSTarr'main = do print $ runST bp return () 这篇关于将Monad / ST用于可变图中的非并发消息传递的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！