为什么函数的结果不能重用？

Question

当我尝试编写最短路径算法时,我遇到了一个奇怪的事情.后floydWarshall功能以阵列形式产生adjecency矩阵,main函数试图阵列多次查询(在replicateM_循环中).

我发现我的代码非常慢.所以我放在traceShow "doing"顶部floydWarshall并重新运行以发现每次res ! (start,end)调用都是floydWarshall重复的.

为什么每次重新生成数组？

完整源代码输入:https: //gist.github.com/cwyang/27ab81bee731e6d01bb3a7483fdb748e

floydWarshall :: AdjMatrix (Maybe Int) -> AdjMatrix (Maybe Int)
floydWarshall am = traceShow "doing" $ runST $ do
  arr <- thaw am :: ST s (STArray s (Vertex,Vertex) (Maybe Int))
  sequence_ [ go arr k i j | k <- r, i <- r, j <- r]
  freeze arr
  where ((minb,_), (maxb,_)) = bounds am
        r = [minb..maxb]
        go :: STArray s (Vertex,Vertex) (Maybe Int)
           -> Vertex -> Vertex -> Vertex -> ST s ()
        go arr k i j = do
          ij <- readArray arr (i,j)
          ik <- readArray arr (i,k)
          kj <- readArray arr (k,j)
          case (ik, kj) of
            (Nothing, _) -> return ()
            (_, Nothing) -> return ()
            (Just a, Just b) -> case ij of
              Nothing  -> do
                writeArray arr (i,j) $ Just (a+b)
              (Just c) -> when (c > a+b) $ do
                writeArray arr (i,j) $ Just (a+b)
readInt :: B.ByteString -> Int
readInt = fst . fromJust . B.readInt

main :: IO ()
main = do
  [n,m] <- rl
  edges <- replicateM m $ do
    [from,to,weight] <- rl
    return (from,to,weight)
  [q] <- rl
  let am = buildAdjMatrix (1,n) edges
      res= floydWarshall am
  replicateM_ q $ do
    [start,end] <- rl
    putStrLn . show $ maybe (-1) id (res ! (start,end))
  where rl = map readInt . B.words <$> B.getLine

样品运行:

$ graph < floyd3.txt hs
"doing"     <-- floydWarshall keeps calling
1395
"doing"
975
"doing"
1593
"doing"
1023
"doing"
1521
...

Answer 1

令人沮丧的是，这似乎是由 GHC 问题“代价高昂的让绑定在 IO 操作值中重复”引起的。

使用forM_而不是replicateM_或使用BangPatterns解决了这个问题。