हास्केल का डेटा क्यों नहीं है। समर्थन अनंत सेट का समर्थन करता है?

Question

निम्नलिखित स्निपेट में:

import qualified Data.Set as Set 

data Nat = Zero | Succ Nat deriving (Eq, Show, Ord) 

instance Enum Nat where 
    pred (Succ x)  = x 
    succ x   = Succ x 
    toEnum 0   = Zero 
    toEnum x   = Succ (toEnum (x-1)) 
    fromEnum Zero  = 0 
    fromEnum (Succ x) = 1 + (fromEnum x) 

nats :: [Nat] 
nats = [Zero ..] 

natSet :: Set.Set Nat 
natSet = Set.fromList nats 

क्यों:

• elem (toEnum 100) nats == True

लेकिन

• Set.member (toEnum 100) natSet कभी भी समाप्त नहीं?

Answer 1

Set.fromList आलसी नहीं है, इसलिए यदि आप इसे अनंत सूची पास करते हैं तो यह समाप्त नहीं होगा। लेकिन natSet इसकी आवश्यकता होने तक नहीं बनाया गया है, इसलिए आप इसे केवल Set.member चलाते समय देखते हैं।

उदाहरण के लिए, Set.null $ Set.fromList [0..] भी समाप्त नहीं होता है।

Answer 2

आपके पास अनंत सेट नहीं हो सकते हैं। यह Set.member को प्रभावित नहीं करता है, जब भी आप कुछ भी करते हैं जो natSet का मूल्यांकन करने के लिए एक चरण (यहां तक ​​कि Set.null) का मूल्यांकन करेगा, यह एक अनंत लूप में जाएगा।

Answer 3

मौजूदा उत्तर पर्याप्त हैं, लेकिन मैं Set के व्यवहार पर थोड़ा सा विस्तार करना चाहता हूं।

ऐसा लगता है कि आप सभी Nat एस के आलसी सेट की उम्मीद कर रहे हैं; आप सभी Nat एस की अनंत सूची लेते हैं और Set.toList पर इसका उपयोग करते हैं। वह अच्छा रहेगा; गणितज्ञ अक्सर "सभी प्राकृतिक संख्याओं के सेट" के संदर्भ में बात करते हैं। समस्या यह है कि Set का कार्यान्वयन आलस्य के रूप में आलस्य के अनुकूल नहीं है।

सेट के कार्यान्वयन आकार पर आधारित है संतुलित द्विआधारी पेड़ (या घिरे संतुलन की पेड़)

The docs for Data.Set

आप lazily एक सूची से एक द्विआधारी पेड़ का निर्माण करना चाहते हैं मान लीजिए । सूची से तत्व केवल पेड़ में डाले जाएंगे जब पेड़ का गहरा ट्रैवर्स आवश्यक था। तो फिर आप पूछते हैं कि पेड़ में 100 है या नहीं। यह पेड़ पर संख्या 1-99 जोड़ने के साथ-साथ एक समय में भी जाएगा। फिर अंत में यह पेड़ में 100 जोड़ देगा, और पता चलता है कि 100 पेड़ में वास्तव में एक तत्व है। लेकिन ध्यान दें कि हमने क्या किया। हमने अभी आलसी सूची में एक इन-ऑर्डर ट्रैवर्सल किया है! तो पहली बार, हमारे काल्पनिक LazyTree.containsList.find के रूप में लगभग एक ही जटिलता (एक ammortized हे (1) डालने, जो एक सरल द्विआधारी पेड़ के लिए एक बुरी धारणा है, जो होता है हे (लॉग एन) जटिलता है संभालने के लिए होता है)। और संतुलन के बिना, हमारा पेड़ बहुत लापता हो जाएगा (हमने क्रमशः 1 से 100 नंबर जोड़े हैं, इसलिए यह प्रत्येक शाखा के दाहिने बच्चे के नीचे एक बड़ी लिंक्ड सूची होगी)। लेकिन पेड़ संतुलन ट्रैवर्सल के दौरान, यह जानना मुश्किल होगा कि ट्रैवर्सल को फिर से कहां शुरू करना है; कम से कम यह निश्चित रूप से तुरंत सहज नहीं होगा।

टीएल; डॉ: कोई भी नहीं (afaik) ने अभी तक एक अच्छा आलसी सेट किया है। इसलिए अनंत समूह को अब अनंत सूची के रूप में अधिक आसानी से दर्शाया जाता है।

Answer 4

देखते हैं जब हम GHC's Set code अनुकूलन अनंत सेट समायोजित करने के लिए क्या होता है:

module InfSet where 

data InfSet a = Bin a (InfSet a) (InfSet a) 

-- create an infinite set by unfolding a value 
ofUnfold :: (x -> (x, a, x)) -> x -> InfSet a 
ofUnfold f x = 
    let (lx,a,rx) = f x 
     l = ofUnfold f lx 
     r = ofUnfold f rx 
    in Bin a l r 

-- check for membership in the infinite set 
member :: Ord a => a -> InfSet a -> Bool 
member x (Bin y l r) = case compare x y of 
         LT -> member x l 
         GT -> member x r 
         EQ -> True  

-- construct an infinite set representing a range of numbers 
range :: Fractional a => (a, a) -> InfSet a 
range = ofUnfold $ \(lo,hi) -> 
      let mid = (hi+lo)/2 
      in ((lo, mid), mid, (mid, hi)) 

नोट कैसे, बजाय एक अनंत सूची से अनंत सेट के निर्माण की, मैं बजाय एक समारोह ofUnfold एकल मान प्रकट करना परिभाषित एक अनंत सूची में। यह हमें समानांतर में दोनों शाखाओं को आलसी बनाने की अनुमति देता है (हमें किसी अन्य निर्माण से पहले एक शाखा को समाप्त करने की आवश्यकता नहीं है)।

की यह एक बार आज़माएंगे करते हैं:

ghci> :l InfSet 
[1 of 1] Compiling InfSet   (InfSet.hs, interpreted) 
Ok, modules loaded: InfSet. 
ghci> let r = range (0,128) 
ghci> member 64 r 
True 
ghci> member 63 r 
True 
ghci> member 62 r 
True 
ghci> member (1/2) r 
True 
ghci> member (3/4) r 
True 

ठीक है, वह काम करने लगता है। क्या होगा यदि हम सेट के बाहर एक मूल्य का प्रयास करें?

ghci> member 129 r 
^CInterrupted. 

यह सिर्फ दौड़ने और चलाने और कभी नहीं छोड़ेगा। असीमित सेट, में कोई रोक शाखा नहीं है, इसलिए खोज कभी नहीं निकलती है। हम किसी भी तरह मूल सीमा की जांच कर सकता है, लेकिन यह है कि असतत तत्वों की अनंत सेट के लिए व्यावहारिक नहीं है:

ghci> let ex = ofUnfold (\f -> (f . (LT:), f [EQ], f . (GT:))) id 
ghci> :t ex 
ex :: InfSet [Ordering] 
ghci> member [EQ] ex 
True 
ghci> member [LT,EQ] ex 
True 
ghci> member [EQ,LT] ex 
^CInterrupted. 

तो अनंत सेट संभव रहे हैं, लेकिन मुझे यकीन है कि वे उपयोगी रहे नहीं हूँ।

Answer 5

मुझे वैसे ही लगा जैसे मैंने एक सेट जोड़ा जो अनंत सूचियों के साथ काम करता है। हालांकि उन्हें सॉर्ट करने की आवश्यकता है, इसलिए मेरा एल्गोरिदम जानता है कि अधिक खोजना बंद करना कब है।

Prelude> import Data.Set.Lazy 
Prelude Data.Set.Lazy> natset = fromList [1..] 
Prelude Data.Set.Lazy> 100 `member` natset 
True 
Prelude Data.Set.Lazy> (-10) `member` natset 
False 

इसकी हैकेज पर। http://hackage.haskell.org/package/lazyset-0.1.0.0/docs/Data-Set-Lazy.html