Haskell Language
traversable

परिचय

ट्रैवर्सिबल संरचना के लिए तत्काल फंक्शनल और फोल्डेबल

import Data.Traversable as Traversable

data MyType a =  -- ...
instance Traversable MyType where
    traverse = -- ...

हर Traversable संरचना एक बनाया जा सकता है Foldable Functor का उपयोग कर fmapDefault और foldMapDefault में पाया कार्यों Data.Traversable ।

instance Functor MyType where
    fmap = Traversable.fmapDefault

instance Foldable MyType where
    foldMap = Traversable.foldMapDefault

fmapDefault Identity एप्लिकेशन fmapDefault में traverse चलाकर परिभाषित किया गया है।

newtype Identity a = Identity { runIdentity :: a }

instance Applicative Identity where
    pure = Identity
    Identity f <*> Identity x = Identity (f x)

fmapDefault :: Traversable t => (a -> b) -> t a -> t b
fmapDefault f = runIdentity . traverse (Identity . f)

foldMapDefault का उपयोग कर परिभाषित किया गया है Const अनुप्रयोगी functor है, जबकि एक monoidal मूल्य जमा है जो अपनी पैरामीटर ध्यान नहीं देता।

newtype Const c a = Const { getConst :: c }

instance Monoid m => Applicative (Const m) where
    pure _ = Const mempty
    Const x <*> Const y = Const (x `mappend` y)

foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldMapDefault f = getConst . traverse (Const . f)

बाइनरी ट्री के लिए ट्रैवर्सेबल का एक उदाहरण

के क्रियान्वयन traverse आमतौर पर के एक कार्यान्वयन की तरह लग रहे fmap एक में पहुंचाया Applicative संदर्भ।

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

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

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

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

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

ghci> traverse print myTree
'a'
'b'
'c'

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

data Inorder a = ILeaf
               | INode (Inorder a) a (Inorder a)  -- as before
               deriving (Functor, Foldable, Traversable)  -- also using DeriveFunctor and DeriveFoldable

data Preorder a = PrLeaf
                | PrNode a (Preorder a) (Preorder a)
                deriving (Functor, Foldable, Traversable)

data Postorder a = PoLeaf
                 | PoNode (Postorder a) (Postorder a) a
                 deriving (Functor, Foldable, Traversable)

-- 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> traverse print (inorder myTree)
'a'
'b'
'c'
ghci> traverse print (preorder myTree)
'b'
'a'
'c'
ghci> traverse print (postorder myTree)
'a'
'c'
'b'

रिवर्स में एक संरचना का पता लगाना

Backwards एप्लिकेटर फन्नेटर की मदद से एक विपरीत दिशा में एक ट्रावर्सल चलाया जा सकता है, जो एक मौजूदा ऐप्लिकेटर को फ़्लिप करता है ताकि उल्टे क्रम में संयोजित प्रभाव उत्पन्न हो।

newtype Backwards f a = Backwards { forwards :: f a }

instance Applicative f => Applicative (Backwards f) where
    pure = Backwards . pure
    Backwards ff <*> Backwards fx = Backwards ((\x f -> f x) <$> fx <*> ff)

Backwards एक "उल्टा traverse " में उपयोग करने के लिए रखा जा सकता है। जब किसी traverse कॉल के अंतर्निहित एप्लिकेशन को Backwards से फ़्लिप किया जाता है, तो परिणामस्वरूप प्रभाव रिवर्स ऑर्डर में होता है।

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

instance Traversable t => Traversable (Reverse t) where
    traverse f = fmap Reverse . forwards . traverse (Backwards . f) . getReverse

ghci> traverse print (Reverse "abc")
'c'
'b'
'a'

Reverse newtype Data.Functor.Reverse के अंतर्गत पाया जाता है।

ट्रैवर्सेबल की परिभाषा

class (Functor t, Foldable t) => Traversable t where
    {-# MINIMAL traverse | sequenceA #-}
    
    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
    traverse f = sequenceA . fmap f
    
    sequenceA :: Applicative f => t (f a) -> f (t a)
    sequenceA = traverse id
    
    mapM :: Monad m => (a -> m b) -> t a -> m (t b)
    mapM = traverse
    
    sequence :: Monad m => t (m a) -> m (t a)
    sequence = sequenceA

Traversable संरचनाओं t हैं finitary कंटेनर तत्वों के a है जो एक effectful "आगंतुक" ऑपरेशन के साथ पर संचालित किया जा सकता। आगंतुक समारोह f :: a -> fb प्रदर्शन एक संरचना और के प्रत्येक तत्व पर दुष्प्रभाव के traverse का उपयोग करने वालों दुष्प्रभाव तैयार करता Applicative । यह देखने का एक और तरीका है कि है sequenceA कहते Traversable संरचनाओं के साथ निकल Applicative रों।

एक संचित पैरामीटर की सहायता से एक ट्रैवर्सेबल संरचना को बदलना

दो mapAccum फ़ंक्शंस फोल्डिंग और मैपिंग के संचालन को जोड़ती है।

--                                                       A Traversable structure
--                                                                   |
--                                                     A seed value  |
--                                                             |     |
--                                                            |-|  |---|
mapAccumL, mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
--                                      |------------------|              |--------|
--                                               |                            |
--                       A folding function which produces a new mapped       |
--                         element 'c' and a new accumulator value 'a'        |
--                                                                            |
--                                                            Final accumulator value
--                                                             and mapped structure

ये फ़ंक्शंस सामान्यीकृत fmap हैं कि वे मैप किए गए मानों को इस बात पर निर्भर करने की अनुमति देते हैं कि गुना में पहले क्या हुआ है। वे foldl / foldr को सामान्यीकृत foldl कि वे संरचना में जगह बनाने के साथ-साथ इसे एक मूल्य तक कम कर देते हैं।

उदाहरण के लिए, tails को mapAccumR का उपयोग करके लागू किया जा सकता है और इसकी बहन inits को mapAccumL का उपयोग करके लागू किया जा सकता है।

tails, inits :: [a] -> [[a]]
tails = uncurry (:) . mapAccumR (\xs x -> (x:xs, xs)) []
inits = uncurry snoc . mapAccumL (\xs x -> (x `snoc` xs, xs)) []
    where snoc x xs = xs ++ [x]

ghci> tails "abc"
["abc", "bc", "c", ""]
ghci> inits "abc"
["", "a", "ab", "abc"]

mapAccumL को State mapAccumL में ट्रैवर्सिंग द्वारा कार्यान्वित किया जाता है।

{-# LANGUAGE DeriveFunctor #-}

newtype State s a = State { runState :: s -> (s, a) } deriving Functor
instance Applicative (State s) where
    pure x = State $ \s -> (s, x)
    State ff <*> State fx = State $ \s -> let (t, f) = ff s
                                              (u, x) = fx t
                                          in (u, f x)

mapAccumL f z t = runState (traverse (State . flip f) t) z

mapAccumR रिवर्स में mapAccumL चलाकर काम करता है।

mapAccumR f z = fmap getReverse . mapAccumL f z . Reverse

सामग्री के साथ आकृतियों के रूप में ट्रैवर्सेबल संरचनाएं

यदि टाइप t Traversable तो ta मानों को दो टुकड़ों में विभाजित किया जा सकता है: उनका "आकार" और उनका "कंटेंट":

data Traversed t a = Traversed { shape :: t (), contents :: [a] }

जहाँ "सामग्री" वही है जो आप Foldable उदाहरण का उपयोग करके "विज़िट" करते हैं।

एक ही दिशा जा रहे हैं, से ta करने के लिए Traversed ta कुछ भी लेकिन आवश्यकता नहीं है Functor और Foldable

break :: (Functor t, Foldable t) => t a -> Traversed t a 
break ta = Traversed (fmap (const ()) ta) (toList ta)

लेकिन पीछे जाने से महत्वपूर्ण रूप से traverse फ़ंक्शन का उपयोग किया traverse है

import Control.Monad.State

-- invariant: state is non-empty
pop :: State [a] a
pop = state $ \(a:as) -> (a, as)

recombine :: Traversable t => Traversed t a -> t a
recombine (Traversed s c) = evalState (traverse (const pop) s) c

Traversable कानूनों को break . recombine आवश्यकता होती है break . recombine और recombine . break दोनों पहचान हैं। विशेष रूप से, इसका मतलब यह है कि contents में सही संख्या तत्व हैं जो पूरी तरह से बिना किसी बाएं ओवर के shape भरने के लिए contents ।

Traversed t Traversable ही है। के कार्यान्वयन के traverse की सूची के उदाहरण का उपयोग करते हुए तत्वों पर जाकर काम करता है Traversable और उसके बाद परिणाम को निष्क्रिय आकार reattaching।

instance Traversable (Traversed t) where
    traverse f (Traversed s c) = fmap (Traversed s) (traverse f c)

सूचियों की एक सूची को प्रेषित करना

यह देखते हुए कि zip टपल की सूची में एक सूची का tuple स्थानांतरित करता है,

ghci> uncurry zip ([1,2],[3,4])
[(1,3), (2,4)]

और transpose और sequenceA के प्रकारों के बीच समानता,

-- transpose exchanges the inner list with the outer list
--           +---+-->--+-+
--           |   |     | |
transpose :: [[a]] -> [[a]]
--            | |     |   |
--            +-+-->--+---+

-- sequenceA exchanges the inner Applicative with the outer Traversable
--                                             +------>------+
--                                             |             |
sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
--                                                |       |
--                                                +--->---+

विचार उपयोग करने के लिए है [] के Traversable और Applicative तैनात करने के लिए संरचना sequenceA n-ary का एक प्रकार के रूप में zip , एक साथ सभी आंतरिक सूचियों को एक साथ ज़िप करने pointwise।

[] 's डिफ़ॉल्ट "प्राथमिकता वाला विकल्प" Applicative उदाहरण हमारे उपयोग के लिए उपयुक्त नहीं है - हमें "zippy" Applicative । इसके लिए हम Control.Applicative में पाए जाने वाले ZipList newtype का उपयोग करते हैं।

newtype ZipList a = ZipList { getZipList :: [a] }

instance Applicative ZipList where
    pure x = ZipList (repeat x)
    ZipList fs <*> ZipList xs = ZipList (zipWith ($) fs xs)

अब हम मिल transpose मुक्त करने के लिए, में traversing द्वारा ZipList Applicative ।

transpose :: [[a]] -> [[a]]
transpose = getZipList . traverse ZipList

ghci> let myMatrix = [[1,2,3],[4,5,6],[7,8,9]]
ghci> transpose myMatrix
[[1,4,7],[2,5,8],[3,6,9]]