Warum wird das Ergebnis der Funktion nicht wiederverwendet?

Question

Wenn ich versuche, einen Algorithmus für den kürzesten Pfad zu programmieren, stoße ich auf eine seltsame Sache. Nach floydWarshall Funktion generiert Adjecency Matrix in Array-Form, main Funktion versucht, das Array mehrmals (in replicateM_ Schleife) abzufragen.

Was ich fand, ist, dass mein Code schrecklich langsam ist. Also setze ich traceShow "doing" an die Spitze von floydWarshall und wiederhole, dass jeder res ! (start,end) wiederholt floydWarshall aufruft.

Warum wird das Array jedes Mal neu generiert?

Volle Quelle mit Abtastwerteingang: 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 

Probelauf:

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

Answer 1

Frustrierend, scheint dies "Costly let binding gets duplicated in IO action value" durch das GHC Problem verursacht werden.

Verwenden Sie forM_ statt replicateM_ oder BangPatterns verwenden, löst dieses Problem.