Memoizing आईओ संगणना हास्केल

Question

में मैं एक समारोह

f :: MonadIO m => a -> m b 

जो कुछ इनपुट लेता है और एक आईओ गणना कि उत्पादन निकलेगा देता है। मैं f को "याद रखना" चाहता हूं ताकि मैं प्रत्येक इनपुट के लिए कभी-कभी इन गणनाओं को निष्पादित करूं। उदाहरण के लिए, यदि

f :: String -> IO String 
f s = putStrLn ("hello " ++ s) >> return s 

तो मैं एक समारोह चाहते हैं इस तरह के memoize कि

do 
    mf <- memoize f 
    s <- mf "world" 
    t <- mf "world" 
    return (s,t) 

प्रिंट "hello world" ठीक एक बार और ("world", "world") देता है। जो प्रोग्राम मैं लिख रहा हूं वह बहु-थ्रेडेड है, इसलिए इस प्रॉपर्टी को तब भी पकड़ना चाहिए जब विभिन्न धागे mf पर कॉल कर रहे हों।

नीचे (भयानक) समाधान है जो मैं अब तक आया हूं। मेरा सवाल यह है कि यह कैसे और कैसे सुधार किया जा सकता है।

1) cache टाइप TVar (Map a (TMVar (Maybe b))) है:

memoize :: (MonadIO m, Ord a) => (a -> m b) -> m (a -> m b) 
memoize f = do 
    cache <- liftIO $ newTVarIO Map.empty 
    return $ \a -> do 
       v <- liftIO $ atomically $ lookupInsert cache a 
       b <- maybe (f a) return =<< liftIO (atomically $ takeTMVar v) 
       liftIO $ atomically $ putTMVar v $ Just b 
       return b 
    where 
     lookupInsert :: Ord a => TVar (Map a (TMVar (Maybe b))) -> a -> STM (TMVar (Maybe b)) 
     lookupInsert cache a = do 
         mv <- Map.lookup a <$> readTVar cache 
         case mv of 
          Just v -> return v 
          Nothing -> do 
            v <- newTMVar Nothing 
            modifyTVar cache (Map.insert a v) 
            return v 

कुछ चीजें यहाँ पर जा रहे हैं। यह TMVar के इनपुट को मैप करता है जिसमें या तो गणना की गई मान, या Nothing (जो इंगित करता है कि एक मान अभी तक गणना नहीं किया गया है)। फ़ंक्शन lookupInsertcache का निरीक्षण करता है, और TMVar को Nothing में प्रारंभ किया गया है यदि कोई भी पहले से मौजूद नहीं है।

2) लौटे कार्रवाई पहले प्राप्त v :: TMVar (Maybe b)a से जुड़े हैं, तो यह लेता है, और या तो गणना f a करता है एक परिणाम प्राप्त करने के लिए या रिटर्न Maybe में जमा हो जाती है, तो यह उपलब्ध है मूल्य। यह take और put पैटर्न इतना है कि दो अलग-अलग धागे गणना के बाद f a गणना नहीं करते हैं, यह अभी तक नहीं चला है।

Answer 1

मैंने सोचा कि आप जो चाहते थे वह असंभव था, लेकिन यह पता चला है।

https://stackoverflow.com/a/9458721/1798971

मैं अभी भी समझ नहीं क्यों कि काम करता है!