Сохранение графиков в Haskell

Question

Я могу легко определить тип данных для узла ориентированного графа.

data Node = Node String [Node] derving (Show, Read)

Я могу сохранить график в файл с помощью функции show, а затем восстановить его с помощью read .Однако show не справится с циклом.Есть ли тривиальный способ сохранить и восстановить график?

Answer 1

Насколько я знаю, нет.Вы должны написать функцию обхода графика.

Сначала решите, где разорвать округлость.В данном случае это тривиально:используйте имена узлов (при условии, что они уникальны в пределах графика).Для более сложной структуры, такой как граф с узлами и ребрами в виде отдельных типов, вам пришлось бы решить, хранить ли ребра с узлами, узлы с ребрами или сохранять узлы и ребра полностью отдельными.

Затем перечислите все узлы графика.В этом случае очевидным способом является пересечение графика, собирающего узлы в конечную карту (см. Данные.Карта).Затем сохраните каждый узел в виде имени, за которым следует список других имен узлов.

Восстановление графика означает использование шаблона "завязывание узла".Считайте сохраненный график в структуру [(String, [Строка])].Затем исходный график может быть восстановлен с помощью следующего кода:

import qualified Data.Map as M

data Node = Node String [Node]

instance Show Node where
   show (Node name others) = "Node " ++ show name ++ 
         " " ++ show (map nodeName others)
      where nodeName (Node n _) = n

restoreGraph :: [(String, [String])] -> M.Map String Node
restoreGraph pairs = table
   where
      table = M.fromList $ map makeNode pairs
      makeNode (name, others) = (name, Node name $ map findNode others)
      findNode str = fromJust $ M.lookup str table

Обратите внимание на взаимную рекурсию:таблица вызывает makeNode, который вызывает findNode, который вызывает table. Благодаря ленивой оценке это делает правильные вещи.

Редактировать: код теперь протестирован и немного расширен.

Answer 2

Да и нет.Это может быть сделано с помощью знания предметной области о структуре вашего типа узла и определения некоторого понятия равенства, которое вы можете протестировать, в сочетании со списком или картой просмотренных на данный момент узлов для восстановления общего доступа.В патологическом случае в GHC есть понятие стабильного имени для построения такого понятия.

С другой стороны, Мэтт Морроу проделал некоторую работу по извлечению в форме языка ассемблера .Файл S, произвольные циклические данные, используя свою удобную библиотеку vacuum.Так что либо это, либо пылесос могут удовлетворить ваши потребности.

В целом, избегать вуду и отслеживать узлы, видимые до сих пор на карте, вероятно, является наиболее рациональным и ремонтопригодным решением.