मैं जॉन ह्यूजेस के प्रसिद्ध "सामान्यीकरण तीर में "धाराओं के रूप में तीर" खंड को समझने की कोशिश कर रहा हूँ मोनाड्स के लिए"। अधिक सटीक होने के लिए, मुझे फिबोनाची धारा को लिखने में दिलचस्पी है।

मैंने ह्यूजेस की परिभाषा को थोड़ा बदल दिया:

data StreamProcessor a b = Get (a -> StreamProcessor a b) | 
                           Put b (StreamProcessor a b) |
                           Halt
put = Put
get = Get

सबसे पहले, मैं स्ट्रीम प्रोसेसर को सूचियों के रूप में मानता हूं जो अवरुद्ध हो सकते हैं (इनपुट की प्रतीक्षा कर रहे हैं)। अर्थात्:

  • Put :: b -> StreamProcessor a b -> StreamProcessor a b मैच (:) :: a -> [a] -> [a];
  • Halt :: StreamProcessor a b मैच [] :: [a];
  • Get :: (a -> StreamProcessor a b) -> StreamProcessor a b स्ट्रीम को ब्लॉक करने और इनपुट की प्रतीक्षा करने में हमारी मदद करता है।

इसलिए, यदि हम Get को छोड़ देते हैं तो हमें एक सूची जैसी संरचना प्राप्त होती है। अगर हम Halt को भी छोड़ देते हैं तो हमें एक अनंत-सूची जैसी संरचना मिलती है।

यहाँ दो तरीके हैं जिनसे मैं "फिबोनैचिस की एक धारा" को समझूंगा:

  • एक गैर-अवरुद्ध अनंत धारा (अनंत-सूची-जैसी):

    zipNonBlockedStreamsWith :: (a -> b -> c) 
                                -> StreamProcessor () a 
                                -> StreamProcessor () b
                                -> StreamProcessor () c
    zipNonBlockedStreamsWith f (Put x sp) (Put y sp') 
     = Put (f x y) (zipNonBlockedStreamsWith f sp sp')
    zipNonBlockedStreamsWith f Halt       sp          = Halt  
    zipNonBlockedStreamsWith f sp         Halt        = Halt
    
    fibs :: StreamProcessor () Int
    fibs = 
     put 0 (put 1 $ zipNonBlockedStreamsWith (+) fibs (tailNonBlockedStream fibs))
    
    -- matches a well-known definition of an infinite Fibonacci list.
    fibsList :: [Int]
    fibsList = 0 : 1 : (zipWith (+) fibsList (tail fibsList))
    
    -- with the 'fibsList', we can use folds to do the same thing.
    putStream :: [b] -> StreamProcessor a b -> StreamProcessor a b
    putStream bs sp = foldr Put sp bs
    
    fibs' :: StreamProcessor () Int
    fibs' = putStream fibsList Halt
    
  • एक अवरुद्ध स्ट्रीम n की प्रतीक्षा करती है, nवें फिबोनाची नंबर को आउटपुट करती है और फिर से ब्लॉक करती है। ह्यूजेस का Arrow इंटरफ़ेस हमें इसे काफी संक्षिप्त तरीके से व्यक्त करने में मदद करता है:

    instance Category StreamProcessor where
      ...
    
    instance Arrow StreamProcessor where
      arr f = Get $ \ a -> Put (f a) (arr f)
      ...
    
    fibsList :: [Int]
    fibsList = 0 : 1 : (zipWith (+) fibsList (tail fibsList))
    
    blockedFibs :: StreamProcessor Int Int
    blockedFibs = arr (fibsList !!)
    

फिर भी, मेरे द्वारा लिंक किए गए पेपर में जॉन ह्यूजेस एक और समाधान दिखाता है, Arrow इसके माध्यम से अपना रास्ता बनाना:

instance Category StreamProcessor where
  id = Get (\ x -> Put x id)
  
  Put c bc . ab = Put c (bc . ab)
  Get bbc . Put b ab = (bbc b) . ab
  Get bbc . Get aab = Get $ \ a -> (Get bbc) . (aab a)
  Get bbc . Halt = Halt
  Halt . ab = Halt

bypass :: [b] -> [d] -> StreamProcessor b c -> StreamProcessor (b, d) (c, d)
bypass [] ds (Get f)          = Get $ \ ~(b, d) -> bypass [] (ds ++ [d]) (f b)
bypass (b : bs) [] (Get f)    = bypass bs [] (f b)
bypass [] (d : ds) (Put c sp) = Put (c, d) $ bypass [] ds sp
bypass bs [] (Put c sp) =      
  Get $ \ ~(b, d) -> Put (c, d) (bypass (bs ++ [b]) [] sp)
bypass bs ds Halt             = Halt

instance Arrow StreamProcessor where
  arr f = Get $ \ a -> Put (f a) (arr f)
  first = bypass [] []

liftArr2 :: Arrow k => (a -> b -> c) -> k r a -> k r b -> k r c
liftArr2 f a b = a &&& b >>^ uncurry f

fibsHughes = let 
              fibsHughes' = put 1 (liftArr2 (+) fibsHughes fibsHughes')
             in put 0 fibsHughes'

लेकिन यह मेरी अपेक्षा के अनुरूप काम नहीं करता है। निम्न फ़ंक्शन हमें स्ट्रीम से मानों को तब तक लेने में मदद करेगा जब तक कि यह ब्लॉक या रुक न जाए (Data.List.unfoldr का उपयोग करके):

popToTheBlockOrHalt :: StreamProcessor a b -> [b]
popToTheBlockOrHalt = let
                         getOutput (Put x sp) = Just (x, sp)
                         getOutput getOrHalt  = Nothing
                      in unfoldr getOutput

तो, यहाँ हमें क्या मिलता है:

GHCi> popToTheBlockOrHalt fibsHughes
[0, 1]
GHCi> :t fibsHughes
fibsHughes :: StreamProcessor a Integer

यदि हम पैटर्न की जांच करते हैं, तो हम देखेंगे कि यह अवरुद्ध है (अर्थात हम Get में ठोकर खाते हैं)।

मैं नहीं बता सकता कि ऐसा होना चाहिए या नहीं। अगर हम यही चाहते हैं तो क्यों? यदि नहीं, तो समस्या क्या है? मैंने अपने द्वारा लिखे गए कोड की जाँच की और फिर से जाँच की और यह ह्यूजेस के लेख की परिभाषाओं से काफी मेल खाता है (ठीक है, मुझे id और Halt के लिए पैटर्न जोड़ना था - मैं नहीं देख सकता कि वे इस प्रक्रिया को कैसे गड़बड़ कर सकते थे यूपी)।


संपादित करें: जैसा कि टिप्पणियों में कहा गया है, बाद में पेपर का संस्करण bypass थोड़ा बदल गया था (हम उसका उपयोग करते हैं)। यह रोके गए bs और ds (जिसमें दो कतारें हैं) दोनों को जमा करने में सक्षम है, जबकि bypass मूल पेपर केवल ds (जो एक कतार है) जमा होता है।


#2 संपादित करें: मैं केवल एक फ़ंक्शन लिखना चाहता था जो fibsHughes से फाइबोनैचि संख्याओं को पॉप करेगा:

popToTheHaltThroughImproperBlocks :: StreamProcessor () b -> [b]
popToTheHaltThroughImproperBlocks = let
                                       getOutput (Put x sp) = Just (x, sp)
                                       getOutput (Get c)    = getOutput $ c ()
                                       getOutput Halt       = Nothing
                                    in unfoldr getOutput

और अब हम चले:

GHCi> (take 10 . popToTheHaltThroughImproperBlocks) fibsHughes 
[0,1,1,2,3,5,8,13,21,34]

8
Zhiltsoff Igor 9 अगस्त 2020, 00:25

2 जवाब

सबसे बढ़िया उत्तर

मामला कागज का है। जहां वास्तव में दोष निहित है वह काफी हद तक व्यक्तिपरक व्याख्या का विषय है। मुझे लगता है कि यह कागज में एक अनदेखी बग है क्योंकि StreamProcessor प्रकार के सहज ज्ञान युक्त नहीं होने के कारण यह लग सकता है।

पहले fibsHughes स्ट्रीम के ठोस उदाहरण पर ध्यान केंद्रित करने के लिए, इसमें वास्तव में Get शामिल हैं, लेकिन वे निरंतर कार्य हैं। बाकी स्ट्रीम तक पहुंचने के लिए आपको कुछ तर्कों को फीड करना होगा। एक तरह से, fibsHughes का "सही" प्रकार SP () b है, जबकि आप जो सहज रूप से चाहते हैं वह SP Void b Get की अनुपस्थिति को एन्कोड करने के लिए है (जो काफी काम नहीं करता है) इस तरह, और यह समस्या का स्रोत है), और इसे "खिला" इनपुट यह है कि आप एक से दूसरे में कैसे जाते हैं:

type SP = StreamProcessor

feed :: SP () b -> SP Void b
feed p = produceForever () >>> p

produceForever :: b -> SP Void b
produceForever b = Put b (produceForever b)

fibsHughes :: SP Void b
fibsHughes = feed (... {- rest of the definition -})

अब यह देखने के लिए कि हम इस स्थिति में कैसे आए, हमें first की परिभाषा पर वापस जाना होगा। मेरी राय यह है कि यह पहली जगह में परिभाषित करने के लिए धाराओं पर एक संदिग्ध ऑपरेशन है, क्योंकि इसे जोड़े के दूसरे घटक को आउटपुट के रूप में तैयार करने में सक्षम होने के लिए Get क्रियाओं को पेश करना होगा:

first ::: SP a b -> SP (a, c) (b, c)

समस्याग्रस्त हिस्सा bypass की परिभाषा में निम्नलिखित शाखा है, जो Get को तब Put में सक्षम होने के लिए पेश करती है:

bypass bs [] (Put c sp) =      
  Get $ \ ~(b, d) -> Put (c, d) (bypass (bs ++ [b]) [] sp)

यदि आप अपेक्षित प्रकार का कुछ लिखना चाहते हैं तो आपको यह करने की आवश्यकता है, लेकिन यकीनन ऐसा करना स्वाभाविक नहीं है।

परिभाषित करने के बाद first वह है जो (&&&) ऑपरेटर को परिभाषित करने और उपयोग करने की ओर ले जाता है, जिसमें अनपेक्षित शब्दार्थ है। यह देखने के लिए कि यह सहज क्यों नहीं है, स्ट्रीम इनपुट प्रकार के रूप में Void के साथ (&&&) विशेषज्ञ:

(&&&) :: SP Void b -> SP Void c -> SP Void (b, c)

जो कोई भी इसे देखता है वह सोचता है कि, निश्चित रूप से, परिणाम एक निर्माता होना चाहिए, जो कभी भी Get कुछ भी नहीं है, वह बेतुका होगा। सिवाय इसके कि (&&&) बेतुका काम करता है; इस प्रकार Void के लिए विशिष्ट, यह नैतिक रूप से निम्नलिखित के बराबर है (undefined के अस्तित्व को अनदेखा कर रहा है जिसे तकनीकी रूप से हास्केल में अलग बताने के लिए इस्तेमाल किया जा सकता है):

_ &&& _ = Get (absurd :: Void -> SP a c)

धाराओं पर रिकर्सन द्वारा (&&&) की एक और अधिक प्राकृतिक परिभाषा है जो उस मुद्दे से बचाती है: यदि दो तर्क कभी भी कोई Get नहीं करते हैं, तो परिणाम कभी भी कोई Get नहीं करता है।

जहां तक ​​मैं बता सकता हूं, इस "बेहतर" (&&&) को first, (>>>) और arr का उपयोग करके परिभाषित नहीं किया जा सकता है।

हालांकि, यह लागत पर आता है: यह तीरों की चित्रमय व्याख्या के दृष्टिकोण से सहज नहीं है, क्योंकि यह इस समीकरण को तोड़ता है (जिसे ग्राफिक रूप से "स्लाइडिंग" f में से &&& ):

f &&& g   =   (id &&& g) >>> first f

आप (&&&) की जो भी परिभाषा चुनेंगे, वह किसी को भ्रमित करने वाली है।


IMO यह StreamProcessor प्रकार के नीचे आता है जो Get के उपयोग को खारिज करने में सक्षम नहीं है। भले ही इनपुट प्रकार Void हो, फिर भी एक स्ट्रीम एक खाली Get कर सकती है।

ऐसे निश्चित मुद्दों के बिना एक बेहतर प्रकार का स्ट्रीम प्रोसेसर है पाइप लाइब्रेरी (जिसे <कहा जाता है) a href="https://hackage.haskell.org/package/pipes-4.3.14/docs/Pipes-Internal.html#t:Proxy" rel="nofollow noreferrer">Proxy ) विशेष रूप से, यह SP से भिन्न है क्योंकि यह Get के उपयोग को मना कर सकता है, और यह वास्तविक "उत्पादकों" जैसे कि फिबोनाची स्ट्रीम का एक विश्वसनीय एन्कोडिंग प्रदान करता है।

3
Li-yao Xia 10 अगस्त 2020, 19:10

मुझे लगता है कि आपके पास एक भ्रम हो सकता है कि, जब आप स्ट्रीम प्रोसेसर और सूचियों के बीच एक सहसंबंध पा सकते हैं जो अवरुद्ध हो सकते हैं, वे बिल्कुल समान नहीं हैं। नैतिक रूप से, एक StreamProcessor a b, a की एक धारा का उपभोग करता है और b की एक धारा उत्पन्न करता है। (ह्यूजेस के पेपर के बारे में एक अजीब बात यह है कि वह स्पष्ट रूप से परिभाषित नहीं करता है कि एक धारा क्या है।) इसका मुख्य कारण यह है कि आपका popToTheBlockOrHalt फ़ंक्शन वास्तव में कभी भी इनपुट स्ट्रीम प्रदान नहीं करता है, लेकिन यह अभी भी दी गई स्ट्रीम की अपेक्षा करता है। आउटपुट स्ट्रीम का उत्पादन करने के लिए प्रोसेसर।

ध्यान में रखने वाली एक और बात यह है कि ह्यूजेस के पेपर में कोई Halt नहीं है - स्ट्रीम प्रोसेसर अनंत हैं और अनंत धाराओं पर काम करते हैं। तो, एक तथाकथित "निर्माता" जैसे fibsHughes (अर्थात, एक स्ट्रीम प्रोसेसर जिसका इनपुट स्ट्रीम मनमाना है), वास्तव में कोई "अवरुद्ध" नहीं चल रहा है, भले ही Get छिपे हों आंतरिक रूप से क्योंकि इनपुट स्ट्रीम से हमेशा अधिक इनपुट होता है - यह अनंत है!

तो, आपको इन स्ट्रीम प्रोसेसर के साथ काम करने के लिए उन्हें चलाने का एक तरीका चाहिए, या StreamProcessor a b के किसी फ़ॉर्म को a की स्ट्रीम से फ़ंक्शन में बदलना b की एक धारा। चूंकि आपका संस्करण धाराओं को सीमित होने की अनुमति देता है, इसलिए नियमित रूप से पुरानी सूचियों को अपने "स्ट्रीम" प्रकार के रूप में उपयोग करना समझ में आता है। इस प्रकार, आप एक प्रकार के साथ एक फ़ंक्शन चाहते हैं जैसे:

runStreamProcessor :: StreamProcessor a b -> [a] -> [b]

इसके लिए एक प्राकृतिक परिभाषा है:

runStreamProcessor Halt _ = []
runStreamProcessor (Put x s) xs = x : runStreamProcessor s xs
runStreamProcessor _ [] = []
runStreamProcessor (Get f) (x:xs) = runStreamProcessor (f x) xs

अब, आप runStreamProcessor fibsHughes :: [a] -> [Integer] के प्रकार पर विचार कर सकते हैं और महसूस कर सकते हैं कि, स्वाभाविक रूप से, आपको अनंत आउटपुट स्ट्रीम की गारंटी के लिए, जैसे repeat () की आपूर्ति करनी होगी। यह सही है:

> take 10 $ runStreamProcessor fibsHughes (repeat ())
[0,1,1,2,3,5,8,13,21,34]
1
DDub 16 जिंदा 2021, 03:31