我想在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 …我想计算一个大文件中每个字符的出现次数.虽然我知道计数应该在Haskell中严格实现(我试图使用foldl实现),但我仍然没有内存.作为比较:文件大小约为2GB,而计算机有100GB内存.该文件中没有很多不同的字符 - 也许是20.我做错了什么？
ins :: [(Char,Int)] -> Char -> [(Char,Int)]
ins [] c = [(c,1)]
ins ((c,i):cs) d
| c == d = (c,i+1):cs
| otherwise = (c,i) : ins cs d
main = do
[file] <- getArgs
txt <- readFile file
print $ foldl' ins [] txt