असीमित आलसी बिटमैप

Question

मैं एक आलसी डेटा संरचना बनाने की कोशिश कर रहा हूं जिसमें अनंत बिटमैप है। मैं निम्नलिखित कार्यों का समर्थन करना चाहते हैं:

1. true :: InfBitMap

   यह सच है, अर्थात सभी पदों की एक अनंत बिटमैप मूल्य यह सच होना चाहिए देता है।

2. falsify :: InfBitMap -> [Int] -> InfBitMap

   गलत पर सूची में सभी पदों पर सेट करें। सूची संभव अनंत है। उदाहरण के लिए, सत्य गलत साबित करें [0,2 ..] एक सूची वापस कर देगा जहां सभी (और केवल) विषम स्थिति सही हैं।

3. check :: InfBitMap -> Int -> Bool

   सूचकांक के मूल्य की जाँच करें।

यहां तक ​​कि मैं अब तक क्या कर सकता हूं।

-- InfBitMap will look like [(@), (@, @), (@, @, @, @)..] 
type InfBitMap = [Seq Bool] 

true :: InfBitMap 
true = iterate (\x -> x >< x) $ singleton True 

-- O(L * log N) where N is the biggest index in the list checked for later 
-- and L is the length of the index list. It is assumed that the list is 
-- sorted and unique. 
falsify :: InfBitMap -> [Int] -> InfBitMap 
falsify ls is = map (falsify' is) ls 
    where 
     -- Update each sequence with all indices within its length 
     -- Basically composes a list of (update pos False) for all positions 
     -- within the length of the sequence and then applies it. 
     falsify' is l = foldl' (.) id 
           (map ((flip update) False) 
            (takeWhile (< length l) is)) 
         $ l 
-- O(log N) where N is the index. 
check :: InfBitMap -> Int -> Bool 
check ls i = index (fromJust $ find ((> i) . length) ls) i 

अगर कोई Haskellish अवधारणा/डेटा संरचना है कि मुझे लगता है कि मेरी कोड और अधिक सुरुचिपूर्ण/अधिक कुशल (स्थिरांक मुझे कोई फर्क नहीं है, बस आदेश) बनाना होगा याद आ रही है मैं सोच रहा हूँ। मैंने ज़िप्पर और लेंस को देखने की कोशिश की लेकिन वे मदद नहीं कर रहे हैं। मैं अद्यतनों की जटिलताओं को रखना चाहता हूं और लॉगरिदमिक जांच सकता हूं (शायद केवल अमूर्त लॉगरिदमिक)।

नोट: किसी को संदेह होने से पहले, यह कोई होमवर्क समस्या नहीं है!

अद्यतन:

-- O(log N) where N is the index. 
-- Returns "collapsed" bitmap for later more efficient checks. 
check :: InfBitMap -> Int -> (Bool, InfBitMap) 
check ls i = (index l i, ls') 
    where 
     ls'@(l:_) = dropWhile ((<= i) . length) ls 

जो एक इकाई में कोड सफाई के लिए दिया जा सकता है:

यह सिर्फ मेरे लिए हुआ है कि जांच करने के लिए सुधार किया जा सकता।

Answer 1

प्रसिद्ध integer trie पर मामूली बदलाव यहां लागू होता प्रतीत होता है।

{-# LANGUAGE DeriveFunctor #-} 

data Trie a = Trie a (Trie a) (Trie a) deriving (Functor) 

true :: Trie Bool 
true = Trie True true true 

-- O(log(index)) 
check :: Trie a -> Int -> a 
check t i | i < 0 = error "negative index" 
check t i = go t (i + 1) where 
    go (Trie a _ _) 1 = a 
    go (Trie _ l r) i = go (if even i then l else r) (div i 2) 

--O(log(index)) 
modify :: Trie a -> Int -> (a -> a) -> Trie a 
modify t i f | i < 0 = error "negative index" 
modify t i f = go t (i + 1) where 
    go (Trie a l r) 1 = Trie (f a) l r 
    go (Trie a l r) i | even i = Trie a (go l (div i 2)) r 
    go (Trie a l r) i = Trie a l (go r (div i 2)) 

दुर्भाग्य से हम modify उपयोग कर सकते हैं नहीं falsify लागू करने के लिए है क्योंकि हम सूचकांक कि जिस तरह से की अनंत सूचियों संभाल सकते हैं (सभी संशोधन trie का एक तत्व का निरीक्षण किया जा सकता है से पहले किया जाना है)। के बाद से अन्यथा हम check (falsify t (repeat 0)) 1 में trie में स्थानों को छोड़ या यहां तक ​​कि गैर समाप्ति मिलेगा, उदाहरण के लिए

ascIndexModify :: Trie a -> [(Int, a -> a)] -> Trie a 
ascIndexModify t is = go 1 t is where 
    go _ t [] = t 
    go i t@(Trie a l r) ((i', f):is) = case compare i (i' + 1) of 
     LT -> Trie a (go (2*i) l ((i', f):is)) (go (2*i+1) r ((i', f):is)) 
     GT -> go i t is 
     EQ -> Trie (f a) (go (2*i) l is) (go (2*i+1) r is) 

falsify :: Trie Bool -> [Int] -> Trie Bool 
falsify t is = ascIndexModify t [(i, const False) | i <- is] 

हम कड़ाई से is में सूचकांक आरोही यह मानें कि,: इसके बजाय, हम किसी मर्ज की तरह अधिक कुछ करना चाहिए।

समय जटिलताओं आलस्य से थोड़ा जटिल हैं। check (falsify t is) index में, हम तुलनात्मक रूप से log 2 index तुलना की एक अतिरिक्त लागत का भुगतान करते हैं, और length (filter (<index) is) तुलना की संख्या (i। ई। जो हम देख रहे हैं उससे कम सभी सूचकांक पर कदम उठाने की लागत)। आप कह सकते हैं कि यह O(max(log(index), length(filter (<index) is)) है। वैसे भी, यह O(length is * log (index)) से निश्चित रूप से बेहतर है कि का उपयोग करके is -s के लिए लागू falsify के लिए हमें प्राप्त होगा।

हमें यह ध्यान में रखना चाहिए कि पेड़ नोड्स का मूल्यांकन एक बार किया जाता है, और बाद में check -s उसी सूचकांक के लिए पहले checkfalsify के लिए कोई अतिरिक्त लागत नहीं दे रहे हैं। फिर, आलस्य इसे थोड़ा जटिल बनाता है।

यह falsify भी बहुत अच्छी तरह से व्यवहार किया जाता है जब हम एक त्रिभुज के उपसर्ग को पार करना चाहते हैं। इस toList समारोह लें:

trieToList :: Trie a -> [a] 
trieToList t = go [t] where 
    go ts = [a | Trie a _ _ <- ts] 
      ++ go (do {Trie _ l r <- ts; [l, r]}) 

यह एक मानक चौड़ाई-पहले ट्रेवर्सल, रैखिक समय में है। जब हम अधिक तुलना में 2 * n पर अधिक तुलना करते हैं, तो is सख्ती से बढ़ते हुए, अतिरिक्त तुलना में take n $ trieToList (falsify t is) की गणना करते समय ट्रैवर्सल समय रैखिक बना रहता है।

(साइड नोट: चौड़ाई-पहले ट्रैवर्सल की अंतरिक्ष आवश्यकता बल्कि दर्दनाक है, लेकिन मुझे इसकी मदद करने का एक आसान तरीका नहीं दिख रहा है, क्योंकि पुनरावृत्ति गहराई यहां और भी बदतर है, क्योंकि पूरे पेड़ में होना चाहिए स्मृति, जबकि बीएफएस को केवल पेड़ के निचले स्तर को याद रखना है)।

Answer 2

इसका प्रतिनिधित्व करने का एक तरीका एक समारोह के रूप में है।

true = const True 

falsify ls is = \i -> not (i `elem` is) && ls i 

check ls i = ls i 

सत्य और गलत कार्य अच्छे और कुशल हैं। चेक फ़ंक्शन रैखिक के रूप में खराब हो सकता है। एक ही बुनियादी विचार की दक्षता में सुधार करना संभव है। मुझे इसकी लालित्य पसंद है।