Haskell内存使用和IO

Question

我刚刚写了一段Haskell代码，为了调试我的代码，在我的代码中放入了一堆打印语句（因此，我的最重要的函数返回IO t，而它只需要返回t），我发现这个函数在成功运行时会占用大量内存（大约1.2GB）。一旦我看到程序正常工作，我就从函数中删除了所有的打印语句并运行它，结果发现它给我报错：

Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

尽管代码完全相同，但由于打印语句的存在，它却无视了堆栈溢出。有人能告诉我为什么会发生这种情况吗？

我知道我没有提供代码，这可能会使回答这个问题更难，但我已经把很多东西拼凑在一起，它看起来不太美观，所以我怀疑它并没有什么用处，而且我相当确定唯一的区别就是打印语句。

编辑：

因为人们真的想看到代码，这里是相关部分：

linkCallers :: ([Int], Int, Int, I.IntDisjointSet, IntMap Int) -> ([Int], Int, Int, I.IntDisjointSet, IntMap Int)
linkCallers ([], x, y, us, im) = ([], x, y, us, im) 
linkCallers ((a:b:r), x, y, us, im) = if a == b
    then (r, x, y+1, us, im) 
    else if sameRep
        then (r, x+1, y+1, us, im) 
        else (r, x+1, y+1, us', im')
        where
            ar = fst $ I.lookup a us
            br = fst $ I.lookup b us  
            sameRep = case ar of
                Nothing -> False
                _ -> ar == br
            as' = ar >>= flip lookup im
            bs' = br >>= flip lookup im
            totalSize = do
                asize <- as' 
                bsize <- bs' 
                return $ asize + bsize
            maxSize = (convertMaybe as') + (convertMaybe bs')
            us' = I.union a b $ I.insert a $ I.insert b $ us
            newRep = fromJust $ fst $ I.lookup a us' 
            newRep' = fromJust $ fst $ I.lookup b us' 
            im'' = case ar of
                Nothing -> case br of
                    Nothing -> im
                    Just bk -> delete bk im
                Just ak -> delete ak $ case br of
                    Nothing -> im
                    Just bk -> delete bk im
            im' = case totalSize of  
                Nothing -> insert newRep maxSize im''
                Just t -> insert newRep t im''

startLinkingAux' (c,x,y,us,im) = let t@(_,x',_,us',im') = linkCallers (c,x,y,us,im) in
    case (fst $ I.lookup primeMinister us') >>= flip lookup im' >>= return . (>=990000) of
        Just True -> x'
        _ -> startLinkingAux' t

"startLinkingAux' 曾经长这样："

startLinkingAux' (c,x,y,us,im) = do
    print (c,x,y,us,im)
    let t@(_,x',_,us',im') = linkCallers (c,x,y,us,im) in
    case (fst $ I.lookup primeMinister us') >>= flip lookup im' >>= return . (>=990000) of
        Just True -> return x'
        _ -> startLinkingAux' t

- Emil

---

您应该展示至少一个函数，在这个函数中您已经取消了打印功能。 - Zeta

只是一种直觉：尝试在您以前打印这些值的地方强制（评估）它们，并查看是否有所不同。 - fjh

只是猜测 - print 语句强制评估了一个惰性计算的 thunk，没有它，thunk 累积直到溢出堆栈。请参阅此文章以了解如何构建 thunks：http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl' - ErikR

尝试使用 Debug.Trace.trace 进行调试。 - augustss

由于程序在打印时消耗了大量（堆）内存，我猜测存在内存泄漏问题（无论是IO版本还是纯版本），但在纯版本中编译器会优化使用栈而不是堆，因此会出现溢出异常。 - Petr

Answer 1

可能存在一个参数中的内存泄漏。我建议首先尝试联系disjoint-set的作者，让他为IntDisjointSet添加一个RFData实例（或者您可以自己查看源代码进行添加，这很容易）。然后尝试在所有由linkCallers返回的值上调用force，看看是否有所帮助。

其次，您没有正确使用disjoint-set。该算法的主要思想是在集合中压缩路径以提高性能！因此，每次查找时，都应该用新的集合替换旧的集合。但在函数式语言中使用不相交集会变得非常笨拙。我建议在linkCallers内部使用State单子，在一个大的do块中而不是where中使用它，只需传递起始集合并提取最终集合。并定义如下函数：

insertS :: (MonadState IntDisjointSet m) => Int -> m ()
insertS x = modify (insert x)

lookupS :: (MonadState IntDisjointSet m) => Int -> m (Maybe Int)
lookupS x = state (lookup x)

-- etc

用于State内部。（也许它们会成为库的一个好贡献，因为这可能是一个常见的问题。）

最后，有很多小的改进可以使代码更易读：

很多时候，您会将单个函数应用于两个值。我建议定义类似以下的内容：

onPair :: (a -> b) -> (a, a) -> (b, b)
onPair f (x, y) = (f x, f y)
-- and use it like:
(ar, br) = onPair (fst . flip I.lookup us) (a, b)

同时使用 Applicative 函数可以让代码更加简洁：

sameRep = fromMaybe False $ (==) <$> ar <*> br
totalSize = (+) <$> as' <*> bs' 

然后也

im'' = maybe id delete ar . maybe id delete br $ im
im' = insert newRep (fromJust maxSize totalSize) im''

希望它有所帮助。

- Petr