Я могу легко определить тип данных для узла ориентированного графа.
data Node = Node String [Node] derving (Show, Read)
Я могу сохранить график в файл с помощью функции show, а затем восстановить его с помощью чтения. Однако с циклом шоу не справится. Есть ли тривиальный способ сохранить и восстановить график?
Насколько я знаю, нет. Вы должны написать функцию обхода графика.
Во-первых, решите, где разбить цикличность. В этом случае это тривиально: используйте имена узлов (при условии, что они уникальны в графе). Для более сложной структуры, такой как граф с узлами и ребрами как отдельными типами, вам придется решить, хранить ли ребра с узлами, узлы с ребрами или хранить узлы и ребра полностью отдельно.
Затем перечислите все узлы в графе. В этом случае очевидным способом является обход узлов графа по конечной карте (см. html" rel="nofollow noreferrer">Data.Map). Затем сохраните каждый узел как имя, за которым следует список имен других узлов.
Восстановить граф означает использовать шаблон «завязывание узла». Прочитайте сохраненный граф в структуру [(String, [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
Обратите внимание на взаимную рекурсию: table вызывает makeNode, который вызывает findNode, который вызывает table. Благодаря ленивой оценке это работает правильно.
Изменить: код протестирован и немного расширен.
И да и нет. Это можно сделать с помощью предметной области структуры вашего типа узла и определения некоторого понятия равенства, которое вы можете проверить, в сочетании со списком или картой узлов, которые вы видели до сих пор, чтобы восстановить совместное использование. В патологическом случае в GHC есть понятие StableName для построения такого понятия.
С другой стороны, Мэтт Морроу проделал некоторую работу по извлечению в виде файла .S на языке ассемблера произвольных циклических данных, используя свою удобную вакуумную библиотеку. Так что либо это, либо вакуум может удовлетворить ваши потребности.
В общем, отказ от узлов вуду и отслеживания, видимых до сих пор на карте, является, вероятно, наиболее рациональным и поддерживаемым решением.
