क्या कोई हास्केल

Question

में ट्रैवर्स फ़ंक्शन को समझा सकता है मैं हास्केल के लिए नौसिखिया हूं। मैं Data.Traversable मॉड्यूल से traverse फ़ंक्शन को पकड़ने की कोशिश कर रहा हूं और विफल रहा हूं। मैं इसके बिंदु को देखने में असमर्थ हूं। चूंकि मैं एक अनिवार्य पृष्ठभूमि से आया हूं, क्या कोई इसे अनिवार्य पाश के संदर्भ में मुझे समझा सकता है? एक छद्म कोड की सराहना की जाएगी। धन्यवाद।

Answer 1

मुझे लगता है कि यह sequenceA के संदर्भ में समझने के लिए, के रूप में के रूप में traverse इस प्रकार परिभाषित किया जा सकता सबसे आसान है।

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b) 
traverse f = sequenceA . fmap f 

sequenceA दृश्यों को एक साथ एक संरचना के तत्वों बाएं से दाएं, एक ही आकार परिणाम रखने वाले के साथ एक संरचना लौटने।

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a) 
sequenceA = traverse id 

तुम भी दो functors के आदेश को पलटने के रूप में sequenceA के बारे में सोच सकती है, उदा परिणामों की एक सूची लौटने वाली कार्रवाई में कार्रवाइयों की एक सूची से जा रहा है।

तो traverse कुछ संरचना लेता है, और f लागू होता है कुछ अनुप्रयोगी में संरचना में हर तत्व को बदलने के लिए, यह तो उन applicatives बाएं से दाएं, एक ही आकार परिणाम रखने वाले के साथ एक संरचना लौटने के दुष्प्रभाव ऊपर अनुक्रम।

आप इसकी तुलना Foldable से भी कर सकते हैं, जो संबंधित फ़ंक्शन traverse_ को परिभाषित करता है।

traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f() 

तो आप देख सकते है कि Foldable और Traversable के बीच मुख्य अंतर यह है कि बाद के हैं, जबकि पूर्व कुछ अन्य मूल्य में परिणाम मोड़ें करने की आवश्यकता है आप संरचना के आकार को बनाए रखने के लिए अनुमति देता है।

---

इसके उपयोग के एक साधारण उदाहरण traversable संरचना के रूप में एक सूची का उपयोग कर रहा है, और IO अनुप्रयोगी के रूप में:

λ> import Data.Traversable 
λ> let qs = ["name", "quest", "favorite color"] 
λ> traverse (\thing -> putStrLn ("What is your " ++ thing ++ "?") *> getLine) qs 
What is your name? 
Sir Lancelot 
What is your quest? 
to seek the holy grail 
What is your favorite color? 
blue 
["Sir Lancelot","to seek the holy grail","blue"] 

बेशक

, इस मामले में यह mapM प्रस्तावना से के बराबर है। अन्य प्रकार के कंटेनरों पर या अन्य आवेदकों का उपयोग करते समय यह अधिक दिलचस्प हो जाता है।

Answer 2

traversefmap जैसा ही है, सिवाय इसके कि यह आपको डेटा संरचना के पुनर्निर्माण के दौरान प्रभाव चलाने की अनुमति देता है।

Data.Traversable दस्तावेज़ीकरण से उदाहरण देखें।

data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a) 

Tree की Functor उदाहरण होगा:

instance Functor Tree where 
    fmap f Empty  = Empty 
    fmap f (Leaf x)  = Leaf (f x) 
    fmap f (Node l k r) = Node (fmap f l) (f k) (fmap f r) 

यह पूरे पेड़ पुनर्निर्माण, हर मूल्य को f लागू करने। सिवाय कंस्ट्रक्टर्स अनुप्रयोगी शैली में कहा जाता है

instance Traversable Tree where 
    traverse f Empty  = pure Empty 
    traverse f (Leaf x)  = Leaf <$> f x 
    traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r 

Traversable उदाहरण, लगभग एक ही है। इसका मतलब है कि पेड़ के पुनर्निर्माण के दौरान हम (दुष्प्रभाव) प्रभाव डाल सकते हैं।आवेदक मोनाद के समान ही है, सिवाय इसके कि प्रभाव पिछले परिणामों पर निर्भर नहीं हो सकते हैं। इस उदाहरण में इसका मतलब है कि उदाहरण के लिए बाएं शाखा के पुनर्निर्माण के परिणामों के आधार पर आप नोड की दाहिनी शाखा से कुछ अलग नहीं कर सके।

Traversable कक्षा में एक monadic संस्करण mapM भी शामिल है जहां सिद्धांत, सिद्धांत रूप में, पिछले परिणामों पर निर्भर कर सकते हैं। (आप निश्चित रूप से है कि क्या करना चाहिए नहीं कर रहे हैं हालांकि।) उदाहरण के लिए, f का असर ऐसा दो बार करता है, तो बाईं शाखा Empty है:

mapM f (Node l k r) = do 
    l' <- mapM f l 
    k' <- case l' of 
    Empty -> do _ <- f k; f k 
    _  -> f k 
    r' <- mapM f r 
    return $ Node l' k' r' 

आप एक अशुद्ध भाषा में इसे लागू करेंगे, तो fmap और traverse होगा mapM जैसा ही हो, क्योंकि दुष्प्रभावों को रोकने के लिए कोई रास्ता नहीं है। आप इसे लूप के रूप में कार्यान्वित नहीं कर सकते हैं, क्योंकि आपको अपनी डेटा संरचना को बार-बार पार करना होगा। यहाँ एक छोटा सा उदाहरण है कि कैसे मैं जावास्क्रिप्ट में यह करना होगा:

Node.prototype.traverse = function (f) { 
    return new Node(this.l.traverse(f), f(this.k), this.r.traverse(f)); 
} 

यह लागू करने के लिए इस प्रभाव है कि भाषा हालांकि अनुमति देता है के लिए आप को सीमित करता है। यदि आप f.e. गैर-निर्धारणा (जो आवेदक मॉडल की सूची उदाहरण) चाहते हैं और आपकी भाषा में यह अंतर्निहित नहीं है, आप भाग्य से बाहर हैं।

Answer 3

traverse चीजों के एक Traversable "अंदर" एक Applicative में एक Traversable अंदर चीजें बदल जाता है, एक समारोह है कि चीजों में से बाहर Applicative रों बनाता दिया।

चलिए MaybeApplicative के रूप में उपयोग करें और Traversable के रूप में सूचीबद्ध करें। पहले हम परिवर्तन समारोह की जरूरत है:

half x = if even x then Just (x `div` 2) else Nothing 

तो अगर एक नंबर भी है, हम इसके बारे में आधे से अधिक (एक Just अंदर) मिलता है, वरना हम Nothing मिलता है। सब कुछ "ठीक" हो जाता है, यह इस तरह दिखता है:

traverse half [2,4..10] 
--Just [1,2,3,4,5] 

लेकिन ...

traverse half [1..10] 
-- Nothing 

कारण यह है कि <*> समारोह परिणाम का निर्माण करने के लिए किया जाता है, और जब तर्क में से एक Nothing है, हमें Nothing वापस मिल गया है।

एक और उदाहरण:

rep x = replicate x x 

इस समारोह सामग्री x, उदा लंबाई x की एक सूची उत्पन्न rep 3 = [3,3,3]। traverse rep [1..3] का नतीजा क्या है?

हमें [1], [2,2] और [3,3,3] का आंशिक परिणाम rep का उपयोग करके मिलता है। अब Applicatives के रूप में सूचियों के अर्थशास्त्र "सभी संयोजन लेते हैं", उदा। (+) <$> [10,20] <*> [3,4][13,14,23,24] है।

[1] और [2,2] के "सभी संयोजन" दो बार [1,2] हैं। दो बार [1,2] और [3,3,3] के सभी संयोजन छह गुना [1,2,3] हैं।तो हमने:

traverse rep [1..3] 
--[[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3]] 

Answer 4

traverse पाश है। इसका कार्यान्वयन ट्रैवर्स होने के लिए डेटा संरचना पर निर्भर करता है। यह एक सूची, वृक्ष, शायद, सेक (ence), या कुछ भी हो सकता है जिसमें sth के माध्यम से घुमावदार मधुमक्खी का एक सामान्य तरीका है। फॉर-लूप या रिकर्सिव फ़ंक्शन की तरह। एक ऐरे के लिए एक लूप होगा, एक सूची एक समय-लूप, एक पेड़ या तो sth होगा। रिकर्सिव या थोड़ी देर के साथ एक ढेर का संयोजन; लेकिन कार्यात्मक भाषाओं में आपको इन बोझिल लूप कमांड की आवश्यकता नहीं है: आप लूप के आंतरिक हिस्से को एक फ़ंक्शन के आकार में जोड़ते हैं, डेटा संरचना के साथ अधिक सीधे तरीके से और कम वर्बोज़ में।

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

Answer 5

यह fmap जैसा है, सिवाय इसके कि आप मैपर फ़ंक्शन के अंदर साइड इफेक्ट्स चला सकते हैं, जो परिणाम प्रकार भी बदलता है।

डेटाबेस में उपयोगकर्ता आईडी का प्रतिनिधित्व करने वाले पूर्णांक की एक सूची की कल्पना करें: [1, 2, 3]। यदि आप fmap उपयोगकर्ता नामों के लिए इन उपयोगकर्ता आईडी चाहते हैं, तो आप पारंपरिक fmap का उपयोग नहीं कर सकते हैं, क्योंकि फ़ंक्शन के अंदर आपको उपयोगकर्ता नाम पढ़ने के लिए डेटाबेस तक पहुंचने की आवश्यकता होती है (जिसके लिए साइड इफेक्ट की आवश्यकता होती है - इस मामले में, IO monad का उपयोग करके)।

traverse के हस्ताक्षर है:

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b) 

traverse साथ

, आप कर सकते हैं दुष्प्रभाव, इसलिए, उपयोगकर्ता नाम मैपिंग प्रयोक्ता आईडी के लिए अपने कोड लगता है:

mapUserIDsToUsernames :: (Num -> IO String) -> [Num] -> IO [String] 
mapUserIDsToUsernames fn ids = traverse fn ids 

---

नहीं है mapM नामक एक फ़ंक्शन भी:

mapM :: Monad m => (a -> m b) -> [a] -> m [b] 

mapM का कोई भी उपयोग traverse के साथ प्रतिस्थापित किया जा सकता है, लेकिन दूसरी तरफ नहीं। mapM आमतौर पर traverse से बेहतर प्रदर्शन करता है, लेकिन mapM केवल सूचियों के साथ मोनैड के लिए काम करता है, जबकि traverse अधिक सामान्य है।

यदि आप सिर्फ साइड इफेक्ट प्राप्त करना चाहते हैं और किसी भी उपयोगी मूल्य को वापस नहीं करना चाहते हैं, तो traverse_ और mapM_ इन कार्यों के संस्करण हैं, जिनमें से दोनों फ़ंक्शन से वापसी मूल्य को अनदेखा करते हैं और थोड़ा तेज़ होते हैं।