Why is the result of the function not reused?

Question

When I try to code a shortest path algorithm, I run across a strange thing. After floydWarshall function generates adjecency matrix in array form, main function tries to query the array multiple times (in replicateM_ loop).

What I found is that my code is terribly slow. So I put traceShow "doing" at the top of floydWarshall and re-run to find that each res ! (start,end) calls floydWarshall repeatedly.

Why does the array re-generates each time?

Full source with sample input: 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

Sample run:

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

Answer 1

Frustratingly, this seems to be caused by the GHC issue "Costly let binding gets duplicated in IO action value".

Using forM_ rather than replicateM_ or using BangPatterns solves this issue.