एक effectful समारोह Memoizing

Question

मैं एक परियोजना एक स्थानीय संक्रमण समारोह के रूप में एक सेलुलर automaton को परिभाषित करने पर काम शुरू:

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

जब भी g एक Monoid है, यह लागू करने से पहले ध्यान देने के स्थानांतरण से एक वैश्विक संक्रमण परिभाषित करना संभव है स्थानीय संक्रमण। यह हमें निम्नलिखित step समारोह देता है:

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

अब, हम बस iterate का उपयोग करके आटोमैटिक मशीन चला सकते हैं। चरणों में से हर एक के अनुरूप बनाएं memo द्वारा फिर से संगणना की: और हम एक बहुत बचा सकता है (यह सचमुच घंटे की बचत होती है और मैं एक बहुत मतलब है):

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

मेरे समस्या यह है कि मैं इतना है कि CelluarT करने के लिए Cellular सामान्यीकृत है मैं स्थानीय नियमों में साइड इफेक्ट का उपयोग करने में सक्षम होगा (जैसे एक यादृच्छिक पड़ोसी को कॉपी):

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

हालांकि, मैं केवल प्रभाव चलाने के लिए चाहते हैं एक बार तो यह है कि अगर आप एक सेल पूछना कई बार क्या इसका मूल्य है, जवाब सभी संगत हैं। memo हमें यहां विफल कर देता है क्योंकि यह इसके परिणाम के बजाय प्रभावशाली गणना बचाता है।

मुझे उम्मीद नहीं है कि यह असुरक्षित सुविधाओं का उपयोग किए बिना प्राप्त करने योग्य नहीं है। मैंने इसे एक जाना है करने के लिए मूल्यों को पहले से ही गणना की स्टोर करने के लिए unsafePerformIO, एक IORef और एक Map g a का उपयोग कर की कोशिश की है:

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 

लेकिन यह अप्रत्याशित तरीके से व्यवहार करती है: memoM putStrLn सही ढंग से memoized है, जबकि memoM (\ str -> getLine) के बावजूद प्राप्त करने में कठिनाई लाइनों रहता है उसी तर्क को पारित किया जा रहा है।

Answer 1

सबसे पहले, unsafePerformIO का उपयोग करने का प्रयास करना बंद करें। इसे एक कारण के लिए मिला है।

जो आप करने की कोशिश कर रहे हैं वह याद नहीं है, यह वास्तव में आंतरिक मोनैड को कॉल को नियंत्रित करता है। सुराग का एक हिस्सा यह है कि सेलुलर एक मोनड नहीं है, इसलिए सेलुलर टी एक मोनड ट्रांसफार्मर नहीं है।

मुझे लगता है कि आपको एक शुद्ध कार्य करने की आवश्यकता है जो प्रति सेल आवश्यक प्रभाव की गणना करता है, और उसके बाद प्रभावों को अनुक्रमित करने के लिए कोशिकाओं पर पुन: सक्रिय होता है। यह आपके प्रभावशाली यांत्रिकी से आपके सेलुलर ऑटोमेटोन यांत्रिकी (जो आपके पास पहले से है, और जो अच्छा दिखता है) को अलग करता है। फिलहाल आप एक ही समय में प्रभावों को निष्पादित करने की कोशिश कर रहे हैं जैसे आप उनकी गणना करते हैं, जो आपकी समस्याओं का कारण बन रहा है।

यह हो सकता है कि आपके प्रभाव को इनपुट चरण और आउटपुट चरण में विभाजित करने की आवश्यकता हो, या ऐसा कुछ। या शायद आपके प्रभाव वास्तव में एक राज्य मशीन की तरह हैं जिसमें प्रत्येक सेल का प्रत्येक पुनरावृत्ति परिणाम उत्पन्न करता है और एक नया इनपुट की अपेक्षा करता है। इस मामले में यह कैसे करें इसके बारे में कुछ विचारों के लिए my question here देखें।

Answer 2

यदि आप मानचित्र को पकड़ने के संदर्भ को आवंटित करने का अवसर देते हैं तो इसे सुरक्षित रूप से हासिल किया जा सकता है।

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 

मैं संगामिति सही से अधिकतम लाभ उठाने के लिए एक IORef के बजाय एक MVar उपयोग करने के लिए जा रहा हूँ।यह शुद्धता के लिए है, यदि यह एक साथ प्रयोग किया जाता है, प्रदर्शन के लिए नहीं। प्रदर्शन के लिए हम इससे अधिक प्रशंसक हो सकते हैं और फाइनल लॉक ग्रैन्युलरिटी के साथ डबल-चेक लॉक या एक समवर्ती मानचित्र का उपयोग कर सकते हैं।

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) 

हम वास्तव में IO उपयोग नहीं कर रहे, हम बस राज्य भर गुजर रहे हैं। किसी भी मोनड को ट्रांसफॉर्मर के साथ ऐसा करने में सक्षम होना चाहिए, तो हम IO में क्यों मजाक कर रहे हैं? ऐसा इसलिए है क्योंकि हम उन मानचित्रों को आवंटित करने में सक्षम होना चाहते हैं ताकि memoM एक से अधिक अलग-अलग फ़ंक्शन के लिए उपयोग किया जा सके। अगर हम केवल एक ही ज्ञापन प्रभावशाली फ़ंक्शन के बारे में परवाह करते हैं, तो हम इसके बजाय केवल एक राज्य ट्रांसफॉर्मर का उपयोग कर सकते हैं।

{-# 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 

इस ट्रांसफार्मर memoized effectful समारोह

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')) 

इसे चलाने और अंतर्निहित इकाई पर प्राप्त करने के लिए से एक मूल्य देखने के लिए योग्यता प्रदान करती है, हम effectful समारोह हम memoize करना चाहते हैं प्रदान करने के लिए की जरूरत है।

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

हमारे MemoT हर कार्य के लिए एक Map उपयोग करता है। कुछ कार्यों को किसी अन्य तरीके से याद किया जा सकता है। monad-memo पैकेज monads है कि एक विशेष समारोह के लिए Memoization प्रदान के लिए एक mtl शैली वर्ग, और उन्हें निर्माण जरूरी है कि Map रों उपयोग नहीं करता है के लिए एक अधिक विस्तृत तंत्र है।