एक सूची जिसका "नील" एक मूल्य रखता है?

Question

कुछ मानक हास्केल पुस्तकालय इस

data ListWithEnd e a = Cons a (ListWithEnd e a) 
        | End e 

एक सूची जिसका समाप्त तत्व एक निर्दिष्ट प्रकार का एक मूल्य वहन करती है यही कारण है कि जैसे एक डेटा प्रकार को परिभाषित करता है?

तो ListWithEnd()[] और ListWithEnd Void पर isomorphic है अनंत धाराओं के लिए isomorphic है। या, अलग तरह से देखा जाता है, ListWithEnd e a बहुत ConduitM() a Identity e के करीब है ..

Answer 1

हम ListWithEnd इस प्रकार परिभाषित कर सकते हैं:

import Control.Monad.Free 

type LWE a e = Free ((,) a) e 

हम आम तौर पर एक उम्मीद है कि अमूर्त या सामान्य अभ्यावेदन बॉयलरप्लेट की एक समग्र कमी के साथ हमें इनाम चाहिए । चलो देखते हैं कि यह प्रतिनिधित्व हमें क्या प्रदान करता है।

किसी भी मामले में, हम विपक्ष मामले के लिए एक पैटर्न पर्याय को परिभाषित करेगा:

{-# LANGUAGE PatternSynonyms #-} 

pattern x :> xs = Free (x, xs) 
infixr 5 :> 

हम मैप कर सकते हैं गुना और अंत तत्व पर पार:

fmap (+1) (0 :> Pure 0) == (0 :> Pure 1) 
traverse print (0 :> Pure 1) -- prints 1 

Applicative उदाहरण हमें देता है बहुत साफ संगतता:

xs = 1 :> 2 :> Pure 10 
ys = 3 :> 4 :> Pure 20 

xs *> ys   == 1 :> 2 :> 3 :> 4 :> Pure 20 -- use right end 
xs <* ys   == 1 :> 2 :> 3 :> 4 :> Pure 10 -- use left end 
(+) <$> xs <*> ys == 1 :> 2 :> 3 :> 4 :> Pure 30 -- combine ends 

हम सूची elem पर नक्शा कर सकते हैं दस्तावेजों, अगर थोड़ा tortuously:

import Data.Bifunctor -- included in base-4.8! 

hoistFree (first (+10)) xs == 11 :> 12 :> Pure 10 

और हम iter के उपयोग, निश्चित रूप से कर सकते हैं।

iter (uncurry (+)) (0 <$ xs) == 3 -- sum list elements 

यह अच्छा होगा अगर LWE हो सकता है एक Bitraversable (और Bifunctor और Bifoldable), क्योंकि तब हम एक अधिक सामान्य और सैद्धांतिक रास्ते में सूची तत्वों का उपयोग कर सकते हैं। इसके लिए हमें निश्चित रूप से एक newtype की जरूरत है:

newtype LWE a e = LWE (Free ((,) a) e) deriving (lots of things) 

instance Bifunctor LWE where bimap = bimapDefault 
instance Bifoldable LWE where bifoldMap = bifoldMapDefault 
instance Bitraversable LWE where bitraverse = ... 

लेकिन इस बिंदु पर हम सिर्फ सादा एडीटी बाहर लेखन और कोड की लाइनों के एक जोड़े में Applicative, Monad और Bitraversable उदाहरणों लिखने के बारे में सोच सकते हैं। वैकल्पिक रूप से, हम lens का उपयोग करें और सूची तत्वों के लिए एक Traversal लिख सकते हैं:

import Control.Lens 

elems :: Traversal (LWE a e) (LWE b e) a b 
elems f (Pure e) = pure (Pure e) 
elems f (x :> xs) = (:>) <$> f x <*> elems f xs 

इस रेखा के साथ आगे सोच रही थी, हम अंत तत्व के लिए एक Lens बनाना चाहिए। यह जेनेरिक Free इंटरफ़ेस पर बोनस का थोड़ा सा है, क्योंकि हम जानते हैं कि प्रत्येक परिमित LWE में बिल्कुल एक अंत तत्व होना चाहिए, और हम इसके लिए Lens (Traversal या Prism के बजाय) को स्पष्ट कर सकते हैं।

end :: Lens (LWE a e) (LWE a e') e e' 
end f (Pure e) = Pure <$> f e 
end f (x :> xs) = (x :>) <$> end f xs