在LPath的Haskell实现中是否存在空间泄漏

Question

为了好玩，我正在尝试编写朴素最长路径算法的实现（用于查找循环图中最长非循环路径的长度）。我从命令式算法的直接端口开始，它工作和性能相当不错。

data Route = Route {dest:: !Int32, cost:: !Int32}
type Node = [Route]
lPathImperative :: V.Vector Node -> Int32 -> UMV.IOVector Bool -> IO (Int32)
lPathImperative !nodes !nodeID !visited = do
  UMV.write visited (fromIntegral nodeID) True
  max <- newIORef 0
  Prelude.mapM_  ( Route{dest, cost} -> do
         isVisited <- UMV.read visited (fromIntegral dest)
         case isVisited of
           True -> return ()
           False -> do
               dist <- fmap (+ cost) $ lPathImperative nodes dest visited
               maxVal <- readIORef max
               if dist > maxVal then writeIORef max dist else return ())
     (nodes V.! (fromIntegral nodeID))
  UMV.write visited (fromIntegral nodeID) False
  readIORef max

其中visited是一个未装箱的可变向量，表示图中的每个节点当前是否被访问过，全部初始化为false，节点是节点的向量。

然后，我尝试通过max作为折叠传递的值而不是 IORef 来使其更具功能性，如下所示：

lPathFun :: V.Vector Node -> Int32 -> UMV.IOVector Bool -> IO (Int32)
lPathFun !nodes !nodeID !visited = do
  UMV.write visited (fromIntegral nodeID) True
  let max = CM.foldM acc (0::Int32) (nodes V.! (fromIntegral nodeID))
  UMV.write visited (fromIntegral nodeID) False
  max
    where
      acc :: Int32 -> Route -> IO (Int32)
      acc maxDist Route{dest,cost}  = do
          isVisited <- UMV.read visited (fromIntegral dest)
          case isVisited of
            True -> return maxDist
            False -> do
              dist <- fmap (+ cost) $ lPathFun nodes dest visited
              return $ if dist > maxDist then dist else maxDist

然而，这个版本无法完成，运行了几分钟（另一个对于相同的输入需要几秒钟），然后out of memory (requested 1048576 bytes)死亡。如果有人可以查看我的代码lPathFun并了解我做错了什么，我将不胜感激。我试过让里面的所有东西都严格，但这没有帮助，也试着让一切都变得懒惰，没有改变。我什至尝试将type node更改为V.Vector route，并对其使用严格的foldM'，但无济于事。

我怀疑问题是空间泄漏。这是因为我尝试将lPathFun翻译成OCaml并且效果很好（OCaml版本使用手动递归的事实应该不会有什么区别：我的函数式Haskell版本最初也使用手动递归，但遇到了与使用foldM相同的问题）：

type route = {dest: int; cost: int}
type node = route array
let rec lPathFun (nodes: node array) nodeID visited =
  visited.(nodeID) <- true;
  let rec loop i maxDist =
    if i < 0 then maxDist
    else
      let neighbour = nodes.(nodeID).(i) in
      if (not visited.(neighbour.dest))
      then
        let dist = neighbour.cost + lPathFun nodes neighbour.dest visited in
        let newMax = if dist > maxDist then dist else maxDist in
        loop (i-1) newMax
      else
        loop (i-1) maxDist in
  let (max: int) = loop (Array.length nodes.(nodeID) - 1) 0 in
  visited.(nodeID) <- false;
  max;;

我使用的 GHC 版本是 7.8.3。

Answer 1

这里的let max = ...看起来很可疑：

lPathFun !nodes !nodeID !visited = do
  UMV.write visited (fromIntegral nodeID) True
  let max = CM.foldM acc (0::Int32) (nodes V.! (fromIntegral nodeID))
  UMV.write visited (fromIntegral nodeID) False
  max

您的代码等效于：

  UMV.write ... True
  UMV.write ... False
  CM.foldM acc ...

但我相信你想要：

  UMV.write visited ... True
  max <- CM.foldM ...
  UMV.write visited ... False
  return max