İşlev neden tekrar kullanılmıyor?

Question

En kısa yol algoritmasını kodlamaya çalıştığımda garip bir şeyle karşılaşıyorum. floydWarshall işlevi, dizi formunda bitişik matris oluşturduktan sonra, main işlevi, diziyi birden çok kez sorgulamaya çalışır (replicateM_ döngüsünde).

Bulduğum şey kodumun oldukça yavaş olmasıdır. Bu yüzden traceShow "doing"'u floydWarshall'un üstüne koydum ve her res ! (start,end)'un tekrar tekrar floydWarshall numarasını aradığını bulmak için yeniden çalıştırın.

Diziler neden her seferinde yeniden üretiliyor? Numune girişi ile

Tam kaynak: 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 

Numune çalışma:

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

Answer 1

Frustratingly, bu GHC konuyla "Costly let binding gets duplicated in IO action value" neden gibi görünüyor. Bu sorunu gidermek veya replicateM_ yerine forM_ kullanmak veya BangPatterns kullanmak bu sorunu çözmektedir.