Использование Monad/ST для непараллельной передачи сообщений в изменчивом графе

Question

Я пытаюсь разработать структуру данных для следующей ситуации.

Структура графика

Я планирую иметь граф узлов с невзвешенными, направленными ребрами: Graph = [Node]

Каждый узел имеет:

1. Некоторые TBD внутреннего (постоянного) состояния
2. Очередь входящих сообщений
3. Тип сообщения, которое он может отправить, определяется функцией, которая принимает текущее состояние узла (с возможностью сбоя)
4. Список ребер

Node { nodeState :: NodeState, inbox :: Queue NodeMessage, nodeMessage :: (NodeState -> Maybe NodeMessage), connections::[NodeEdge] }

Каждое ребро является промежуточным этапом захвата ожидающих сообщений для целевого узла.

NodeEdge { pendingMessage:: Maybe NodeMessage, targetNode :: Node }

Передача сообщений

Передача сообщений происходит поэтапно и не является одновременной (хотя очереди могут обрабатываться параллельно для сокращения времени вычислений).

• Этап 1. Проверьте входящие сообщения каждого узла, обрабатывая любые сообщения и обновляя NodeState если актуально.
• Этап 2. Запустите каждый узел nodeMessage, если это приводит к Just NodeMessageотправьте NodeMessage для каждого соединения ([NodeEdge])
• Этап 3: Проверьте каждый край узла, если у него есть сообщение, добавьте его в очередь сообщений целевого узла.

Monat / ST

Мой первоначальный план состоял в том, чтобы назначить каждому узлу идентификатор (возможно, простое Int) и сохранить каждый узел в узле Map Int. Я не пробовал ST Monad раньше, но я решил, что могу использовать что-то вроде ST s (M.Map Int Node), Для любой заданной фазы активность отправки сообщения каждого узла может быть обработана в O(k log N).

С другой стороны, если узлы / ребра смогли обновить изменяемое состояние своих ребер / узлов, то любая O-очередь могла быть обработана в O(k).

В то время как метод ST/Map кажется довольно интуитивно понятным, иметь изменяемость всего графика мне не по силам.

Любые предложения / советы / рекомендуемое чтение?

Answer 1

Я не собираюсь отмечать этот ответ как правильный, потому что он не дает правильного ответа на вопрос. Однако это решение, с которым я иду.

Поскольку число узлов в моем графике никогда не изменится, я понял, что могу использовать массив. Я на самом деле пересматриваю использование изменяемого типа данных - хотя я получаю намного более простой рабочий процесс обновления массива, я получаю меньше преимуществ от лени, и в итоге я пишу тонну кода императивного стиля. Я на самом деле думаю об использовании Array и State Monad, а не ST.

Вот немного тестового кода, который я написал, используя STArray. "Правильный" ответ на этот вопрос будет подобным типом данных специально для Graphs - возможно, есть библиотека STGraph?

В любом случае - вот пример кода с использованием STArray:

import Control.Monad.ST
import Data.Array.ST
import Data.Array

import qualified Data.Dequeue as DQ

type Id = Int

data 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 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 = 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 arr

testSTarr' x = do a <- readArray x 0
                  return a

bp = testSTarr >>= testSTarr'

main = do
            print $ runST bp 
            return ()