हास्केल परिवर्तनशील नक्शा/पेड़

Question

मैं एक परिवर्तनशील (संतुलित) पेड़/मानचित्र/हैश हास्केल में मेज या एक तरह से कैसे एक समारोह के अंदर यह अनुकरण करने के लिए देख रहा हूँ। अर्थात। जब मैं एक ही समारोह को कई बार बुलाता हूं, तो संरचना संरक्षित होती है। अब तक मैं Data.HashTable की कोशिश की है (जो ठीक है, लेकिन कुछ हद तक धीमी गति से) और Data.Array.Judy की कोशिश की लेकिन मैं इसे GHC 6.10.4 के साथ काम करने में असमर्थ था। क्या कोई अन्य विकल्प भी हैं?

Answer 1

आप परिवर्तनशील राज्य चाहते हैं, आप यह कर सकते हैं। बस अपडेट किए गए मानचित्र को चारों ओर पास रखें, या इसे एक राज्य मोनैड में रखें (जो एक ही चीज़ बन जाता है)।

import qualified Data.Map as Map 
import Control.Monad.ST 
import Data.STRef 
memoize :: Ord k => (k -> ST s a) -> ST s (k -> ST s a) 
memoize f = do 
    mc <- newSTRef Map.empty 
    return $ \k -> do 
     c <- readSTRef mc 
     case Map.lookup k c of 
      Just a -> return a 
      Nothing -> do a <- f k 
          writeSTRef mc (Map.insert k a c) >> return a 

आप इसका उपयोग इस तरह कर सकते हैं। अपने स्वयं के जोखिम पर (अभ्यास में, आप कैश से आइटम साफ़ करने के लिए एक रास्ता जोड़ने के लिए भी कर सकते हैं।)

import Control.Monad 
main :: IO() 
main = do 
    fib <- stToIO $ fixST $ \fib -> memoize $ \n -> 
     if n < 2 then return n else liftM2 (+) (fib (n-1)) (fib (n-2)) 
    mapM_ (print <=< stToIO . fib) [1..10000] 

, आप कर सकते हैं सब कुछ के माध्यम से राज्य सूत्रण की आवश्यकता से unsafely भागने कि इसकी जरूरत है

import System.IO.Unsafe 
unsafeMemoize :: Ord k => (k -> a) -> k -> a 
unsafeMemoize f = unsafePerformIO $ do 
    f' <- stToIO $ memoize $ return . f 
    return $ unsafePerformIO . stToIO . f' 

fib :: Integer -> Integer 
fib = unsafeMemoize $ \n -> if n < 2 then n else fib (n-1) + fib (n-2) 

main :: IO() 
main = mapM_ (print . fib) [1..1000] 

Answer 2

हालांकि आप एक परिवर्तनशील प्रकार के लिए पूछना, मुझे सुझाव है कि आप एक अपरिवर्तनीय डेटा संरचना का उपयोग करें और आप एक तर्क के रूप में अपने कार्यों के लिए लगातार संस्करणों पारित है कि करते हैं।

जो डेटा संरचना का उपयोग करने के बारे में,

• आप पूर्णांक कुंजी है, तो Data.IntMap अत्यंत कुशल है केंट

• में एक implementation of red-black trees नहीं है।

• आप स्ट्रिंग कुंजी है, तो bytestring-trie package from Hackage बहुत अच्छा लग रहा है।

समस्या यह है कि मैं का उपयोग नहीं कर सकते हैं (या मैं नहीं जानता कि कैसे करने के लिए) एक गैर परिवर्तनशील प्रकार का उपयोग करें।

यदि आप भाग्यशाली हैं, तो आप अपनी तालिका डेटा संरचना को प्रत्येक फ़ंक्शन के लिए अतिरिक्त पैरामीटर के रूप में पास कर सकते हैं। यदि, हालांकि, आपकी तालिका को व्यापक रूप से वितरित करने की आवश्यकता है, तो आप state monad का उपयोग करना चाहेंगे जहां राज्य आपकी तालिका की सामग्री है।

आप memoize की कोशिश कर रहे हैं, तो आप Conal एलियट के ब्लॉग से आलसी Memoization चाल से कुछ की कोशिश कर सकते हैं, लेकिन जैसे ही आप पूर्णांक तर्क से परे जाना, आलसी Memoization बहुत संदिग्ध — कुछ नहीं मैं सिफारिश करेंगे आप एक के रूप में की कोशिश हो जाता है शुरुआत। हो सकता है कि आप उस व्यापक समस्या के बारे में कोई प्रश्न पोस्ट कर सकें जिसे आप हल करने की कोशिश कर रहे हैं? अक्सर हास्केल और उत्परिवर्तन के साथ समस्या यह है कि किसी प्रकार के दायरे में उत्परिवर्तन या अपडेट कैसे शामिल करें।

यह इतना आसान सीखने किसी भी वैश्विक परिवर्तनशील चर के बिना कार्यक्रम नहीं है।

Answer 3

@ रैमसे के जवाब पर बिल्डिंग

, मैं भी आप अपने समारोह reconceive एक नक्शा लेने के लिए और एक संशोधित एक वापस जाने के लिए सुझाव देते हैं। फिर अच्छा ol 'Data.Map का उपयोग करके कोड, जो संशोधनों में बहुत ही कुशल है।

import qualified Data.Map as Map 

-- | takes input and a map, and returns a result and a modified map 
myFunc :: a -> Map.Map k v -> (r, Map.Map k v) 
myFunc a m = … -- put your function here 

-- | run myFunc over a list of inputs, gathering the outputs 
mapFuncWithMap :: [a] -> Map.Map k v -> ([r], Map.Map k v) 
mapFuncWithMap as m0 = foldr step ([], m0) as 
    where step a (rs, m) = let (r, m') = myFunc a m in (r:rs, m') 
    -- this starts with an initial map, uses successive versions of the map 
    -- on each iteration, and returns a tuple of the results, and the final map 

-- | run myFunc over a list of inputs, gathering the outputs 
mapFunc :: [a] -> [r] 
mapFunc as = fst $ mapFuncWithMap as Map.empty 
    -- same as above, but starts with an empty map, and ignores the final map 

यह सार इस पैटर्न के लिए आसान है और mapFuncWithMap कार्यों कि इस तरह से नक्शे का उपयोग अधिक सामान्य बनाने: यहाँ एक पैटर्न है।

Answer 4

यदि मैं आपकी टिप्पणियां सही पढ़ता हूं, तो आपके पास गणना करने के लिए संभावित रूप से ~ 500k कुल मानों के साथ संरचना है। गणना महंगे हैं, इसलिए आप उन्हें केवल एक बार करना चाहते हैं, और बाद में पहुंच पर, आप केवल बिना किसी प्रतिकृति के मूल्य चाहते हैं।

इस मामले में, अपने लाभ के लिए हास्केल की आलस्य का उपयोग करें! ~ 500k इतना बड़ा नहीं है: बस सभी उत्तरों का नक्शा बनाएं, और फिर आवश्यकतानुसार लाएं। पहला fetch गणना को मजबूर करेगा, उसी उत्तर के बाद के fetches एक ही परिणाम का पुन: उपयोग करेंगे, और यदि आप कभी भी एक विशेष गणना नहीं लेते - यह कभी नहीं होता!

आप PointCloud.hs फ़ाइल में गणना के रूप में 3 डी बिंदु दूरी का उपयोग करके इस विचार का एक छोटा सा कार्यान्वयन पा सकते हैं।यही कारण है कि फ़ाइल Debug.Trace उपयोग करता है जब गणना वास्तव में किया जाता है लॉग इन करने की:

> ghc --make PointCloud.hs 
[1 of 1] Compiling Main    (PointCloud.hs, PointCloud.o) 
Linking PointCloud ... 

> ./PointCloud 
(1,2) 
(<calc (1,2)>) 
Just 1.0 
(1,2) 
Just 1.0 
(1,5) 
(<calc (1,5)>) 
Just 1.0 
(1,2) 
Just 1.0 

Answer 5

वहाँ किसी भी अन्य विकल्प हैं?

Data.Map जैसे एक पूरी तरह कार्यात्मक शब्दकोश के लिए एक परिवर्तनीय संदर्भ।