Memoizing một chức năng effectful

Question

tôi bắt đầu làm việc trên một dự án xác định một automaton di động như một chức năng chuyển tiếp địa phương:

newtype Cellular g a = Cellular { delta :: (g -> a) -> a } 

Bất cứ khi nào g là một Monoid, người ta có thể xác định một sự chuyển tiếp toàn cầu bằng cách chuyển trọng tâm trước khi áp dụng sự chuyển đổi cục bộ. Điều này cho phép chúng tôi sau step chức năng:

step :: Monoid g => Cellular g a -> (g -> a) -> (g -> a) 
step cell init g = delta cell $ init . (g <>) 

Bây giờ, chúng tôi chỉ đơn giản là có thể chạy các automaton bằng cách sử dụng iterate. Và chúng ta có thể tiết kiệm rất nhiều (và tôi có nghĩa là rất nhiều: nó theo nghĩa đen tiết kiệm giờ) tái tính toán bởi memo izing mỗi một trong những bước sau:

run :: (Monoid g, Memoizable g) => Cellular g a -> (g -> a) -> [g -> a] 
run cell = iterate (memo . step cell) 

Vấn đề của tôi là tôi khái quát hóa Cellular-CelluarT để tôi sẽ có thể sử dụng tác dụng phụ trong các quy tắc địa phương (ví dụ như sao chép một người hàng xóm ngẫu nhiên):

newtype CellularT m g a = Cellular { delta :: (g -> m a) -> m a } 

Tuy nhiên, tôi chỉ muốn các hiệu ứng để được chạy lần do đó nếu bạn hỏi một tế bào nhiều lần những gì giá trị của nó là, các câu trả lời đều nhất quán. memo không thành công ở đây vì nó tiết kiệm tính toán hiệu quả thay vì kết quả của nó.

Tôi không mong đợi điều này có thể đạt được mà không sử dụng các tính năng không an toàn. Tôi đã cố gắng để có một đi vào nó bằng cách sử unsafePerformIO, một IORef và Map g a để lưu trữ các giá trị đã tính toán:

memoM :: (Ord k, Monad m) => (k -> m v) -> (k -> m v) 
memoM = 
    let ref = unsafePerformIO (newIORef empty) in 
    ref `seq` loopM ref 

loopM :: (Monad m, Ord k) => IORef (Map k v) -> (k -> m v) -> (k -> m v) 
loopM ref f k = 
    let m = unsafePerformIO (readIORef ref) in 
    case Map.lookup k m of 
    Just v -> return v 
    Nothing -> do 
     v <- f k 
     let upd = unsafePerformIO (writeIORef ref $ insert k v m) 
     upd `seq` return v 

Nhưng nó hoạt động theo những cách không thể đoán trước: memoM putStrLn được memoized một cách chính xác trong khi memoM (\ str -> getLine) giữ dòng lấy bất chấp sự cùng một đối số được truyền cho nó.

Answer 1

Trước tiên, hãy ngừng sử dụng unsafePerformIO. Nó có tên đó vì một lý do.

Những gì bạn đang cố gắng làm không phải là ghi nhớ, nó thực sự kiểm soát các cuộc gọi đến đơn nguyên bên trong. Một phần của manh mối là Cellular không phải là một đơn nguyên, vì vậy CellularT không phải là một biến thể đơn nguyên.

Điều tôi nghĩ bạn cần làm là có hàm thuần túy tính toán hiệu ứng cần thiết cho mỗi ô, và sau đó lặp qua các ô để sắp xếp các hiệu ứng. Điều này tách cơ chế autometon di động của bạn (mà bạn đã có, và cái nhìn tốt) từ cơ học hiệu quả của bạn. Tại thời điểm này bạn dường như đang cố gắng để thực hiện các hiệu ứng cùng một lúc khi bạn tính toán chúng, đó là dẫn đến vấn đề của bạn.

Có thể là các hiệu ứng của bạn cần được chia thành giai đoạn đầu vào và giai đoạn đầu ra, hoặc điều gì đó tương tự. Hoặc có lẽ hiệu ứng của bạn thực sự giống như một máy trạng thái trong đó mỗi lần lặp của mỗi ô mang lại kết quả và mong đợi một đầu vào mới. Trong trường hợp đó, hãy xem my question here để biết một số ý tưởng về cách thực hiện việc này.

Answer 2

Điều này có thể đạt được một cách an toàn nếu bạn cho mình cơ hội phân bổ tham chiếu để giữ bản đồ.

import Control.Monad.IO.Class 

memoM :: (Ord k, MonadIO m) => (k -> m v) -> m (k -> m v) 
       |       | 
       |  opportunity to allocate the map 
       get to IO correctly 

tôi sẽ sử dụng một MVar thay vì một IORef để có được hầu hết đồng thời chính xác.Điều này là đúng đắn, trong trường hợp nó được sử dụng đồng thời, không phải cho hiệu suất. Đối với hiệu suất chúng tôi có thể fancier hơn này và sử dụng khóa kiểm tra đôi hoặc một bản đồ đồng thời với độ chi tiết khóa tốt hơn.

import Control.Concurrent  
import Control.Monad.IO.Class  
import qualified Data.Map as Map 

memoM :: (Ord k, Monad m, MonadIO m) => (k -> m v) -> m (k -> m v) 
memoM once = do 
    mapVar <- liftIO $ newMVar Map.empty  
    return (\k -> inMVar mapVar (lookupInsertM once k)) 

-- like withMVar, but isn't exception safe 
inMVar :: (MonadIO m) => MVar a -> (a -> m (a, b)) -> m b 
inMVar mvar step = do 
    (a, b) <- liftIO (takeMVar mvar) >>= step 
    liftIO $ putMVar mvar a 
    return b 

lookupInsertM :: (Ord k, Monad m) => (k -> m v) -> k -> Map.Map k v -> m (Map.Map k v, v) 
lookupInsertM once k map = 
    case Map.lookup k map of 
     Just v -> return (map, v) 
     Nothing -> do 
      v <- once k 
      return (Map.insert k v map, v) 

Chúng tôi không thực sự đang sử dụng IO, chúng tôi chỉ chuyển qua trạng thái. Bất kỳ đơn nguyên nào cũng có thể làm như vậy với một máy biến áp được áp dụng cho nó, vậy tại sao chúng ta lại nhét vào trong IO? Đó là bởi vì chúng tôi muốn có thể phân bổ các bản đồ đó để memoM có thể được sử dụng cho nhiều chức năng khác nhau. Nếu chúng ta chỉ quan tâm đến một chức năng có hiệu lực ghi nhớ duy nhất, chúng ta chỉ có thể sử dụng một biến trạng thái thay thế.

{-# LANGUAGE GeneralizedNewtypeDeriving #-} 

import Control.Applicative 
import Control.Monad.Trans.Class 
import Control.Monad.Trans.State 

newtype MemoT k v m a = MemoT {getMemoT :: StateT (k -> m v, Map.Map k v) m a} 
    deriving (Functor, Applicative, Monad, MonadIO) 

instance MonadTrans (MemoT k v) where 
    lift = MemoT . lift 

biến này cho biết thêm khả năng tra cứu một giá trị từ chức năng effectful memoized

lookupMemoT :: (Ord k, Monad m) => k -> MemoT k v m v 
lookupMemoT k = MemoT . StateT $ \(once, map) -> do 
                (map', v) <- lookupInsertM once k map 
                return (v, (once, map')) 

Để chạy nó và nhận được ít đơn nguyên cơ bản, chúng ta cần phải cung cấp các chức năng effectful chúng tôi muốn memoize.

runMemoT :: (Monad m) => MemoT k v m a -> (k -> m v) -> m a 
runMemoT memo once = evalStateT (getMemoT memo) (once, Map.empty) 

MemoT sử dụng Map cho mọi chức năng. Một số chức năng có thể được ghi nhớ theo một số cách khác. Gói monad-memo có lớp học mtl cho các đơn vị cung cấp tính năng ghi nhớ cho một chức năng cụ thể và một cơ chế phức tạp hơn để xây dựng chúng không nhất thiết phải sử dụng Map s.