从Haskell中的BFS输出重建图形

Question

我想在Haskell中重建一个图的发生率结构,它是由它的广度优先遍历的输出给出的.显式地,输出由根顶点和邻域列表组成(邻域是标记为新的或旧的顶点列表(=已经访问过)),其中每个邻域对应于尚未分配给邻域的最小顶点然而.

在任何命令式语言中,我都会通过使用队列来解决问题:

Input: root vertex r, list of neighborhoods L
(1) Put r into the empty queue Q
(2) if Q is empty then STOP
(3) extract the first vertex v of Q
(4) extract the first neighborhood N of L
(5) append the unvisited vertices of N to Q
(6) remove the markings (new/old) of the nodes of N and assign v to N
(7) goto (2)

我试图在Haskell中实现这种天真的算法(通过使用列表或使用Data.Sequence作为队列),但ghci总是耗尽内存.这不应该发生,因为虽然输入包含300MB数据,但16GB RAM应该足够了.

因此,天真的实现似乎导致内存泄漏.你如何在Haskell中实现这个算法？

编辑: 以下是(略微简化的)数据类型,我使用:

data Output = Out !Vertex ![[BFSNode]]
data Vertex = Vertex Integer SomeMoreComplexData
data BFSNode = New Vertex | Old Integer

data Graph = ![Vertex] ![(Integer,[Integer])]

数据类型"输出"包含已经解析的BFS输出,包括根顶点和邻域列表.BFSNode对应于BFS树中的节点,该节点属于第一次访问的新顶点,或者属于已经访问过的旧顶点,因此由其唯一编号引用.请注意,解析过程工作正常,占用的内存非常少.

我的目标是将"输出"转换为数据类型"图形",其中包括顶点列表和事件列表.

这是我的实现的简化版本:

readTree :: [[BFSNode]] -> Seq Integer -> Graph
readTree [] _ = Graph [] []
readTree (nb:nbs) qs =
    let (i :< qs') = viewl qs
        newVs = fromList $! map nodeNr . filter isNew $ nb
        (Graph vs adj) = readTree nbs $ qs' >< newVs
    in  Graph (map unNew (filter isNew nb) ++ vs) ((i,nub $ map nodeNr nb):adj)

"nbs"是邻域列表,"qs"是队列.函数"nodeNr"从顶点提取唯一标识号,"isNew"测试顶点是否为新,"unNew"从数据类型"BFSNode"解包新顶点.

Edit2: 我想我现在已经解决了这个问题.也许它与我的转换过程的实现无关.我的失败是使用build in function"read"从文件中读取数据类型"Output".我现在意识到Haskell在读取大文件时遇到了问题.即使它只是读取整数列表,例如

main = do 
    txt <- readFile "test"
    writeFile "test2" . show $ (read txt :: [Integer]) }

如果文件"test"足够大,程序将耗尽内存.我现在明白了,以这种方式解析数据并不是一个好主意,因为"read"会在显示任何输出之前将所有数据加载到内存中,但我仍然不明白为什么它填充16GB的RAM虽然文件不是甚至500MB.你知道"阅读"有什么问题吗？Haskell在您的计算机上显示相同的行为吗？

Edit3: 现在我实现了一个基于流的解析函数"readOutput",它接受一个String并返回数据类型"Output".这个函数很懒,所以当我调用它时我会立即得到一个输出.但是当我用我的转换函数"readTree"(显然是尾递归)组合它时,我根本没有输出,并且内存使用量像往常一样增加.我究竟做错了什么？

编辑4:Edit3中 的问题来自我现在删除的一些严格要求.

Answer 1

这个问题没有指定关键要素 - 该图将如何在 Haskell 中表示？函数式程序需要经过深思熟虑的数据结构，以最大限度地共享和高效运行。通常，这意味着它们是从无到有递归构建的（归纳）。有一篇关于归纳图和函数图算法的论文\xe2\x80\x8e给出了一种表示：

\n\n

module Test where\n\ndata Graph a = Empty | Extension (Graph a) [Int] (Int, a)\n               deriving Show\n

\n\n

也就是说，图可以是Empty、 或由一个节点扩展的（较小的）图。这正是在函数式语言中使用 Cons 构建列表的方式，只不过附加节点必须指定较小的图、前驱链接 ([Int]) 以及新节点编号和数据 (Int,a)。请注意，出于效率原因，他们还将其实现为抽象类型。\'\'

\n\n

通过扩展空图可以生成具有一个节点的图。

\n\n

singleton :: (Int,a) -> Graph a\nsingleton x = Extension Empty [] x\n

\n\n

使用此结构，可以轻松地为 BFS 树定义递归解析算法。

\n\n

data Mark a = Visited Int | New (Int,a) deriving Show\n\nparse :: (Int,a) -> [[Mark a]] -> Graph a\nparse x nbrs = extend Empty [x] nbrs\n\nextend :: Graph a -> [(Int,a)] -> [[Mark a]] -> Graph a\nextend g [] [] = g\nextend g _  [] = Empty -- leftover nodes, really an error.\nextend g [] _  = Empty -- leftover neighborhoods, really an error.\nextend g (x : tl) (nbr : nbrs) =\n  extend (Extension g (seen nbr) x) (news tl nbr) nbrs\n\nnews :: [(Int,a)] -> [Mark a] -> [(Int,a)]\nnews l (New x : tl) = news (uniq l x) tl\nnews l (_ : tl) = news l tl\nnews l [] = l\n\nuniq :: [(Int,a)] -> (Int,a) -> [(Int,a)]\nuniq (x:tl) y = x : if (fst x == fst y) then tl else uniq tl y\nuniq [] y = [y]\n\nseen :: [Mark a] -> [Int]\nseen (Visited i : tl) = i : seen tl\nseen (_ : tl) = seen tl\nseen [] = []\n\nm0 = [New (1,())]\nm1 = [Visited 0, New (2,()), New (3,())]\nm2 = [Visited 1, New (3,())]\nm3 = [Visited 1, Visited 2]    \nnbrs = [m0,m1,m2,m3]\n

\n\n

测试一下，

\n\n

$ ghci\nGHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help\nLoading package ghc-prim ... linking ... done.\nLoading package integer-gmp ... linking ... done.\nLoading package base ... linking ... done.\nPrelude> :load Test\n[1 of 1] Compiling Test             ( Test.hs, interpreted )\nOk, modules loaded: Test.\n*Test> parse (0,()) nbrs\nExtension (Extension (Extension (Extension Empty [] (0,())) [0] (1,())) [1] (2,())) [1,2] (3,())\n

\n\n

为了提高效率，您可以执行以下操作：

\n\n

\n

1. 和函数可以组合起来news并进行尾递归（传递部分构造的列表并立即返回）以提高效率。seenlet (ns,sn) = newseen nbr ([],[])

\n

2. 您的输入可以跟踪每个邻居列表中心的节点。这将避免邻居堆栈中的列表串联。或者，您可以使用功能出队来保存该堆栈。

\n

\n\n

如果您还没有看过，我推荐冈崎的《纯函数数据结构》一书。

\n