왜 함수의 결과가 재사용되지 않습니까?

Question

최단 경로 알고리즘을 코딩하려고하면 이상한 점이 있습니다. floydWarshall 함수가 배열 형식의 인접 행렬을 생성 한 후 main 함수는 배열을 여러 번 쿼리하려고 시도합니다 (replicateM_ 루프).

내가 발견 한 것은 코드가 너무 느리다는 것입니다. 그래서 floydWarshall의 상단에 traceShow "doing"을 넣고 다시 실행하여 각각 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"에 의한 것으로 보인다.

replicateM_ 대신 forM_을 사용하거나 BangPatterns을 사용하면이 문제가 해결됩니다.