Haskell Language
तह

परिचय

टिप्पणियों

एक Foldable संरचना के तत्वों की गिनती

length तत्वों की आवृत्तियां में गिना जाता है a एक तह संरचना में ta ।

ghci> length [7, 2, 9]  -- t ~ []
3
ghci> length (Right 'a')  -- t ~ Either e
1  -- 'Either e a' may contain zero or one 'a'
ghci> length (Left "foo")  -- t ~ Either String
0
ghci> length (3, True)  -- t ~ (,) Int
1  -- '(c, a)' always contains exactly one 'a'

length बराबर होने के रूप में परिभाषित किया गया है:

class Foldable t where
    -- ...
    length :: t a -> Int
    length = foldl' (\c _ -> c+1) 0

ध्यान दें कि यह वापसी प्रकार Int संचालन को प्रतिबंधित करता है जिसे कॉल द्वारा प्राप्त मूल्यों पर length फ़ंक्शन के लिए किया जा सकता है। fromIntegral एक उपयोगी कार्य है जो हमें इस समस्या से निपटने की अनुमति देता है।

एक संरचना को उल्टा मोड़ना

किसी भी गुना को Dual दिशा की मदद से विपरीत दिशा में चलाया जा सकता है, जो एक मौजूदा मोनो को प्रवाहित करता है ताकि एकत्रीकरण पीछे की ओर हो जाए।

newtype Dual a = Dual { getDual :: a }

instance Monoid m => Monoid (Dual m) where
    mempty = Dual mempty
    (Dual x) `mappend` (Dual y) = Dual (y `mappend` x)

जब एक foldMap कॉल के अंतर्निहित foldMap को Dual साथ फ़्लिप किया जाता है, तो गुना पीछे की ओर चलता है; निम्न Reverse प्रकार Data.Functor.Reverse में परिभाषित किया गया है। Data.Functor.Reverse :

newtype Reverse t a = Reverse { getReverse :: t a }

instance Foldable t => Foldable (Reverse t) where
    foldMap f = getDual . foldMap (Dual . f) . getReverse

हम सूची के लिए एक reverse लिखने के लिए इस मशीनरी का उपयोग कर सकते हैं:

reverse :: [a] -> [a]
reverse = toList . Reverse

बाइनरी ट्री के लिए फोल्डेबल का एक उदाहरण

दृष्टांत के लिए Foldable आप कम से कम के लिए एक परिभाषा प्रदान करने की आवश्यकता foldMap या foldr ।

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

instance Foldable Tree where
    foldMap f Leaf = mempty
    foldMap f (Node l x r) = foldMap f l `mappend` f x `mappend` foldMap f r
    
    foldr f acc Leaf = acc
    foldr f acc (Node l x r) = foldr f (f x (foldr f acc r)) l

यह कार्यान्वयन पेड़ के इन-ऑर्डर ट्रैवर्सल को निष्पादित करता है।

ghci> let myTree = Node (Node Leaf 'a' Leaf) 'b' (Node Leaf 'c' Leaf)

--    +--'b'--+
--    |       |
-- +-'a'-+ +-'c'-+
-- |     | |     |
-- *     * *     *

ghci> toList myTree
"abc"

DeriveFoldable विस्तार GHC उत्पन्न करने के लिए अनुमति देता है Foldable प्रकार की संरचना के आधार उदाहरणों। हम Node कंस्ट्रक्टर के लेआउट को समायोजित करके मशीन-लिखित ट्रैवर्सल के क्रम को भिन्न कर सकते हैं।

data Inorder a = ILeaf
               | INode (Inorder a) a (Inorder a)  -- as before
               deriving Foldable

data Preorder a = PrLeaf
                | PrNode a (Preorder a) (Preorder a)
                deriving Foldable

data Postorder a = PoLeaf
                 | PoNode (Postorder a) (Postorder a) a
                 deriving Foldable

-- injections from the earlier Tree type
inorder :: Tree a -> Inorder a
inorder Leaf = ILeaf
inorder (Node l x r) = INode (inorder l) x (inorder r)

preorder :: Tree a -> Preorder a
preorder Leaf = PrLeaf
preorder (Node l x r) = PrNode x (preorder l) (preorder r)

postorder :: Tree a -> Postorder a
postorder Leaf = PoLeaf
postorder (Node l x r) = PoNode (postorder l) (postorder r) x

ghci> toList (inorder myTree)
"abc"
ghci> toList (preorder myTree)
"bac"
ghci> toList (postorder myTree)
"acb"

एक सूची में एक Foldable संरचना समतल

toList एक सपाट Foldable संरचना ta की एक सूची में a रों।

ghci> toList [7, 2, 9]  -- t ~ []
[7, 2, 9]
ghci> toList (Right 'a')  -- t ~ Either e
"a"
ghci> toList (Left "foo")  -- t ~ Either String
[]
ghci> toList (3, True)  -- t ~ (,) Int
[True]

toList को इसके बराबर होने के रूप में परिभाषित किया गया है:

class Foldable t where
    -- ...
    toList :: t a -> [a]
    toList = foldr (:) []

फोल्डेबल संरचना के प्रत्येक तत्व के लिए साइड-इफ़ेक्ट करना

traverse_ एक कार्यान्वित Applicative एक में प्रत्येक तत्व के लिए कार्रवाई Foldable संरचना। यह केवल दुष्प्रभावों को ध्यान में रखते हुए, क्रिया के परिणाम को अनदेखा करता है। (ऐसे संस्करण के लिए जो परिणाम नहीं छोड़ता, Traversable उपयोग करें।)

-- using the Writer applicative functor (and the Sum monoid)
ghci> runWriter $ traverse_ (\x -> tell (Sum x)) [1,2,3]
((),Sum {getSum = 6})
-- using the IO applicative functor
ghci> traverse_ putStrLn (Right "traversing")
traversing
ghci> traverse_ putStrLn (Left False)
-- nothing printed

for_ तर्कों के साथ traverse_ । यह एक अनिवार्य भाषा में एक foreach लूप जैसा दिखता है।

ghci> let greetings = ["Hello", "Bonjour", "Hola"]
ghci> :{
ghci|     for_ greetings $ \greeting -> do
ghci|         print (greeting ++ " Stack Overflow!")
ghci| :}
"Hello Stack Overflow!"
"Bonjour Stack Overflow!"
"Hola Stack Overflow!"

sequenceA_ एक गिर Foldable से भरा Applicative एक एकल कार्रवाई में कार्रवाई, परिणाम अनदेखी।

ghci> let actions = [putStrLn "one", putStLn "two"]
ghci> sequenceA_ actions
one
two

traverse_ को इसके समकक्ष होने के रूप में परिभाषित किया गया है:

traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()
traverse_ f = foldr (\x action -> f x *> action) (pure ())

sequenceA_ के रूप में परिभाषित किया गया है:

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

यही नहीं, जब Foldable भी एक है Functor , traverse_ और sequenceA_ निम्नलिखित संबंध है:

traverse_ f = sequenceA_ . fmap f

एक मुड़ा हुआ में एक Foldable संरचना समतल

foldMap के लिए Foldable संरचना के प्रत्येक तत्व को Monoid , और फिर उन्हें एक एकल मान में जोड़ता है।

foldMap और foldr एक-दूसरे की शर्तें, जिनका अर्थ यह है कि के मामलों में परिभाषित किया जा सकता Foldable जरूरत उनमें से केवल एक के लिए एक परिभाषा दे।

class Foldable t where
    foldMap :: Monoid m => (a -> m) -> t a -> m
    foldMap f = foldr (mappend . f) mempty

Product मोनोइड के साथ उदाहरण उपयोग:

product :: (Num n, Foldable t) => t n -> n
product = getProduct . foldMap Product

फोल्डेबल की परिभाषा

class Foldable t where
    {-# MINIMAL foldMap | foldr #-}

    foldMap :: Monoid m => (a -> m) -> t a -> m
    foldMap f = foldr (mappend . f) mempty

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

    -- and a number of optional methods

Intuitively (हालांकि नहीं तकनीकी रूप से), Foldable संरचनाओं तत्वों के कंटेनर हैं a है जो एक अच्छी तरह से परिभाषित क्रम में उनके तत्वों की एक्सेस दें। foldMap ऑपरेशन कंटेनर के प्रत्येक तत्व को एक Monoid और Monoid संरचना का उपयोग करके उन्हें Monoid है।

एक तह संरचना खाली है अगर जाँच

null रिटर्न True अगर कोई तत्व हैं a एक तह संरचना में ta , और False अगर वहाँ एक या अधिक है। संरचनाएं जिसके लिए null है True एक है length 0 की।

ghci> null []
True
ghci> null [14, 29]
False
ghci> null Nothing
True
ghci> null (Right 'a')
False
ghci> null ('x', 3)
False

null को इसके समतुल्य होने के रूप में परिभाषित किया गया है:

class Foldable t where
    -- ...
    null :: t a -> Bool
    null = foldr (\_ _ -> False) True