Haskell Language
Traversable

Introduction

Functor Instanciation et Pliable pour une structure Traversable

import Data.Traversable as Traversable

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

Chaque Traversable structure peut être un Foldable Functor en utilisant les fmapDefault et foldMapDefault fonctions trouvées dans Data.Traversable .

instance Functor MyType where
    fmap = Traversable.fmapDefault

instance Foldable MyType where
    foldMap = Traversable.foldMapDefault

fmapDefault est défini en exécutant traverse dans le foncteur applicatif d' Identity .

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 est défini à l'aide du foncteur applicatif Const , qui ignore son paramètre tout en accumulant une valeur monoïdale.

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)

Une instance de Traversable pour un arbre binaire

Les implémentations de traverse ressemblent généralement à une implémentation de fmap soulevée dans un contexte 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

Cette implémentation effectue une traversée dans l'ordre de l'arborescence.

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

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

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

La DeriveTraversable extension permet de générer GHC Traversable cas en fonction de la structure du type. Nous pouvons modifier l'ordre du parcours écrit en ajustant la disposition du constructeur de 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'

Traverser une structure en sens inverse

Un parcours peut être exécuté dans le sens opposé à l'aide du foncteur applicatif Backwards , qui retourne une application existante afin que les effets composés se produisent dans l'ordre inverse.

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 peuvent être utilisés dans une " traverse inversée". Lorsque le sous-jacent d'un applicatif traverse appel est retourné avec Backwards , l'effet résultant se produit dans l' ordre inverse.

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'

Le newtype Reverse se trouve sous Data.Functor.Reverse.

Définition de Traversable

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 structures t sont des conteneurs finitaires d'éléments a qui peuvent être exploités avec une effectful opération « visiteur ». La fonction visiteur f :: a -> fb exerce un effet secondaire sur chaque élément de la structure et traverse les effets secondaires en utilisant Applicative . Une autre façon de regarder ce que sequenceA dit Traversable structures font la navette avec Applicative s.

Transformer une structure traversable à l'aide d'un paramètre d'accumulation

Les deux fonctions mapAccum combinent les opérations de pliage et de mappage.

--                                                       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

Ces fonctions généralisent fmap en ce sens qu'elles permettent aux valeurs mappées de dépendre de ce qui s'est passé plus tôt dans le pli. Ils généralisent foldl / foldr en ce qu'ils cartographient la structure en place et la réduisent à une valeur.

Par exemple, les tails peuvent être implémentées en utilisant mapAccumR et ses inits sœurs peuvent être implémentées en utilisant 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 est implémenté en traversant le foncteur applicatif d' State .

{-# 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 fonctionne en exécutant mapAccumL en sens inverse .

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

Structures traversables en tant que formes avec contenu

Si un type t est Traversable alors les valeurs de ta peuvent être divisées en deux parties: leur "forme" et leur "contenu":

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

où le "contenu" est le même que celui que vous "visitiez" en utilisant une instance Foldable .

Franchir une direction, de ta à Traversed ta ne nécessite rien mais Functor et Foldable

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

mais revenir en arrière utilise la fonction de traverse cruciale

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

Les lois Traversable exigent cette break . recombine et recombine . break est à la fois identité. Notamment, cela signifie qu'il y a exactement le bon nombre d'éléments de contents dans le contents pour remplir complètement la shape sans aucun reste.

Traversed t est Traversable lui-même. L'implémentation de traverse fonctionne en visitant les éléments en utilisant l'instance de Traversable de la liste, puis en rattachant la forme inerte au résultat.

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

Transposer une liste de listes

Notant que zip transpose un tuple de listes dans une liste de tuples,

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

et la similitude entre les types de transpose et de 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)
--                                                |       |
--                                                +--->---+

L'idée est d'utiliser la structure Traversable et Applicative [] pour déployer sequenceA comme une sorte de zip n-aire , en regroupant toutes les listes internes ensemble de manière ponctuelle.

[] De » par défaut « choix prioritaire » Applicative exemple ne convient pas à notre utilisation - nous avons besoin d' un « Zippy » Applicative . Pour cela, nous utilisons le nouveau type ZipList , trouvé dans Control.Applicative .

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

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

Maintenant, nous obtenons gratuitement la transpose en parcourant l’ Applicative ZipList .

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]]