Dlaczego wynik funkcji nie jest ponownie używany?

Question

Kiedy próbuję zakodować algorytm najkrótszej ścieżki, natknąłem się na dziwną rzecz. Po funkcji floydWarshall generuje macierz zależności w formie tablicowej, funkcja main próbuje wielokrotnie zapytać tablicę (w pętli replicateM_).

Okazało się, że mój kod jest strasznie powolny. Tak więc ustawiam traceShow "doing" na górze floydWarshall i ponownie uruchamiam, aby znaleźć, że każdy z nich res ! (start,end) dzwoni wielokrotnie.

Dlaczego tablica generuje ponownie za każdym razem?

Pełna źródło z wejścia próbki: 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 

run Próbka:

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

Answer 1

frustrująca, to wydaje się być spowodowane przez GHC emisji "Costly let binding gets duplicated in IO action value".

Używanie forM_ zamiast replicateM_ lub użycie BangPatterns rozwiązuje ten problem.