从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])]

数据类型"Output"包含已解析的BFS输出，该输出由根顶点和邻域列表组成。BFSNode对应于BFS树中的节点，该节点属于第一次访问的新顶点，或者属于已经访问过并且因此由其唯一编号引用的旧顶点。请注意，解析过程运行良好，占用的内存很少。

我的目标是将"Output"转换为数据类型"Graph"，它由顶点列表和关联列表组成。

以下是我的实现的简化版本：

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"中打开一个新的顶点。

第2版：我想我现在把问题本地化了。也许这与我实现转换过程无关。我的失败是使用内置函数"read"从文件中读取数据类型"Output"。我现在意识到Haskell在读取大文件方面有问题。即使只是读取整数列表，例如

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

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

第3版：现在我实现了一个基于流的解析函数"readOutput"，它接受一个String并返回数据类型"Output"。这个函数是惰性的，所以当我调用它时，我会立即得到一个输出。但当我用转换函数"readTree"（它显然是尾部递归的）编写它时，它根本没有输出，内存使用量也像往常一样增加。我做错了什么？

第4版：第三版的问题来自于我现在删除的一些限制。

Answer 1

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

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

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

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

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

使用这种结构，很容易为BFS树定义递归解析算法。

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

测试一下，

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

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

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

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

如果你还没看过，我推荐冈崎关于纯函数数据结构的书。