फ़ंक्शन का परिणाम पुन: उपयोग क्यों नहीं किया जाता है?

Question

जब मैं सबसे कम पथ एल्गोरिदम को कोड करने का प्रयास करता हूं, तो मैं एक अजीब चीज में चला जाता हूं। floydWarshall फ़ंक्शन के बाद सरणी रूप में आसन्नता मैट्रिक्स उत्पन्न करता है, main फ़ंक्शन कई बार सरणी (replicateM_ लूप में) क्वेरी करने का प्रयास करता है।

मुझे जो मिला वह यह है कि मेरा कोड बहुत धीमा है। इसलिए मैंने traceShow "doing"floydWarshall के शीर्ष पर रखा और यह पता लगाने के लिए फिर से चलाया कि प्रत्येक 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

Frustratingly, इस GHC मुद्दा "Costly let binding gets duplicated in IO action value" की वजह से हो रहा है।

forM_ का उपयोग replicateM_ के बजाय या BangPatterns का उपयोग करके इस समस्या को हल करता है।