Memoizing IO tính toán trong Haskell

Question

Tôi có một chức năng

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

mà mất một đầu vào và trả về một tính toán IO rằng sẽ mang lại kết quả. Tôi muốn "ghi nhớ" f để tôi chỉ thực hiện các tính toán này một lần cho mỗi đầu vào. Ví dụ, nếu

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

sau đó tôi muốn có một chức năng memoize mà

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

in "hello world" đúng một lần và trả ("world", "world"). Chương trình tôi đang viết là đa luồng, vì vậy thuộc tính này nên giữ ngay cả khi các luồng khác nhau đang gọi mf.

Dưới đây là giải pháp (khủng khiếp) mà tôi đã đưa ra cho đến thời điểm này. Câu hỏi của tôi là liệu nó có thể được cải thiện hay không.

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 

Có một vài điều xảy ra ở đây:

1) cache có kiểu TVar (Map a (TMVar (Maybe b))). Nó ánh xạ đầu vào của TMVar có chứa giá trị được tính hoặc Nothing (cho biết giá trị chưa được tính). Hàm lookupInsert kiểm tra cache và chèn TMVar mới được khởi tạo thành Nothing nếu chưa có mặt hàng nào.

2) Hành động trở lại lần đầu tiên có được những v :: TMVar (Maybe b) liên quan đến a, sau đó mất nó, và một trong hai thực hiện việc tính toán f a để có được kết quả hoặc trả về giá trị được lưu trữ trong Maybe nếu nó có sẵn. Mẫu take và put này sao cho hai luồng khác nhau không chạy cả tính toán f a sau khi thấy rằng nó chưa được chạy.

Answer 1

Tôi nghĩ những gì bạn muốn là không thể, nhưng hóa ra là vậy.

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

Tôi vẫn không thể hiểu tại sao lại hoạt động!