Haskell Language
Traversable
Recherche…
Introduction
La classe Traversable
généralise la fonction anciennement appelée mapM :: Monad m => (a -> mb) -> [a] -> m [b]
pour travailler avec des effets Applicative
sur des structures autres que des listes.
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]]