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

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

visitedbobox的未装箱可变向量在哪里表示图中的每个节点当前是否已被访问,所有都初始化为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