haskell - 在 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 树中的节点，该节点要么属于第一次访问的新顶点，要么属于已经访问过的旧顶点，因此由其唯一编号引用。请注意，解析过程工作正常并且消耗很少的内存。

我的目标是将“输出”转换为数据类型“图形”，其中包含顶点列表和关联列表。

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

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”，它接受一个字符串并返回数据类型“Output”。这个函数是惰性函数，所以当我调用它时我立即得到输出。但是，当我用转换函数“readTree”(显然是尾递归)组合它时，我根本没有得到任何输出，并且内存使用量照常增加。我做错了什么？

编辑4: Edit3 中的问题来自于我现在删除的一些限制。

Answer 1

这个问题没有指定关键要素 - 该图将如何在 Haskell 中表示？函数式程序需要经过深思熟虑的数据结构，以最大限度地共享和高效运行。通常，这意味着它们是从无到有递归构建的(归纳)。有一篇关于inductive graphs and functional graph algorithms‎的论文给出一种表示:

module Test where

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

也就是说，图要么是空的，要么是由一个节点扩展的(较小的)图。这正是在函数式语言中使用 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. 您的输入可以跟踪每个邻居列表中心的节点。这将避免邻居堆栈中的列表串联。或者，您可以使用功能出列来保存该堆栈。

如果你还没看过，我推荐冈崎的书purely functional data structures .