Foldable.foldl कैसे काम करता है Num> =

Question

LYAH में, ऐसा लगता है कि कोड का एक टुकड़ा है।

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show, Read, Eq) 

instance F.Foldable Tree where 
    foldMap f Empty = mempty 
    foldMap f (Node x l r) = F.foldMap f l `mappend` 
          f x   `mappend` 
          F.foldMap f r 

ghci> F.foldl (+) 0 testTree 
42 
ghci> F.foldl (*) 1 testTree 
64800 

जहाँ तक मुझे पता है, foldMap प्रकार foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m की है, लेकिन Num a => a खुद के प्रकार Monoid नहीं है, तो मैं कैसे Foldable.foldl वास्तव में यहाँ काम करता है सोच रहा हूँ? और foldMap को आंतरिक रूप से Foldable.foldl द्वारा बुलाया जाता है, Monoid का प्रकार क्या है?

Answer 1

यदि आप foldr पर विचार करते हैं तो यह पता लगाना थोड़ा आसान है, जिसमें (a -> b -> b) -> b -> t a -> b है। 'बीजगणित' फ़ंक्शन में a -> b -> b है, जिसे आप a -> (b -> b) के रूप में देख सकते हैं - यह है: एक फ़ंक्शन जो इनपुट के रूप में a लेता है, और आउटपुट के रूप में b -> b देता है।

अब, b -> b एक endomorphism है, जो भी एक monoid है, और Data.Monoid एक प्रकार Endo a को परिभाषित करता है (या यहाँ, यह Endo b होने के लिए शायद चाहिए) है, जो, वास्तव में, एक Monoid।

foldr बस Endo का उपयोग करता है आंतरिक रूप से कॉल करने के लिए foldMap:

foldr :: (a -> b -> b) -> b -> t a -> b 
foldr f z t = appEndo (foldMap (Endo #. f) t) z 

foldl मूल रूप से सिर्फ एक ही चाल करने के लिए चारों ओर तर्क flips:

foldl :: (b -> a -> b) -> b -> t a -> b 
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z 

स्पष्ट है कि, मैं सचमुच की नकल की इन हास्केल स्रोत से दो कार्य कार्यान्वयन। यदि आप documentation of Data.Foldable पर जाते हैं, तो स्रोत देखने के लिए कई लिंक हैं। वही मैंने किया।