haskell - 为什么函数的结果没有被重用？

Question

当我尝试编写最短路径算法时，我遇到了一件奇怪的事情。在floydWarshall函数生成数组形式的邻接矩阵后，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 问题引起的 "Costly let binding gets duplicated in IO action value" .

使用 forM_ 而不是 replicateM_ 或使用 BangPatterns 可以解决此问题。