从Haskell中的BFS输出重建图形

我想在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中 的问题来自我现在删除的一些严格要求.