Itérateurs avec Traversable, en Haskell
Voir aussi : video youtube - code source
En Haskell, la fonction traverse
implémente la notion d’itérateur. On peut
voir cela comme une généralisation à la fois de “map” et de “fold”; ou encore
comme un “map” qui peut réaliser des effets pendant le parcours via un
contexte d’Applicative
. Elle a beaucoup d’applications potentielles,
via différentes structures et contextes.
Exemple : traverser une liste, avec l’applicative IO
On veut parcourir une liste tout en réalisant des entrées/sorties : la liste contient des noms de variable d’environnement et on veut récupérer leur valeur auprès du système d’exploitation.
Pour cela, la fonction getEnv
du module System.Environment
permet de
récupérer une variable d’environnement :
> :t getEnv "HOME"
ghcigetEnv :: IO String
> getEnv "HOME"
ghci"/home/test"
Si on veut récupérer une liste de variables d’environnement, on ne peut pas
juste “mapper” cette fonction sur une liste de noms, car on obtiendrait alors
une liste d’actions IO
, qui n’est pas évaluable directement :
> :t fmap getEnv ["HOME", "USER"]
ghcifmap getEnv ["HOME", "USER"] :: [IO String]
Il faut donc transformer cette liste d’actions qui retournent des strings ([IO String]
) en une action qui retourne une liste de strings (IO [String]
).
C’est ce que fait la fonction sequenceA
:
> :t sequenceA $ fmap getEnv ["HOME", "USER"]
ghcisequenceA $ fmap getEnv ["HOME", "USER"] :: IO [String]
> sequenceA $ fmap getEnv ["HOME", "USER"]
ghci"/home/test","test"] [
La fonction traverse
correspond à la composition de sequenceA
et de fmap
:
traverse = sequenceA . fmap
Autrement dit, traverse
prend une fonction qui “transforme un élément dans un
contexte”, l’applique sur les éléments d’une structure et collecte les
résultats dans le contexte.
> :t traverse getEnv ["HOME", "USER"]
ghcitraverse getEnv ["HOME", "USER"] :: IO [String]
> traverse getEnv ["HOME", "USER"]
ghci"/home/test","test"] [
La classe de types Traversable
Un type est de classe Traversable
s’il est de classe Functor
(implémente fmap
), de classe Foldable
(implémente foldMap
), et
instancie :
class (Functor t, Foldable t) => Traversable t where
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
sequenceA :: Applicative f => t (f a) -> f (t a)
mapM :: Monad m => (a -> m b) -> t a -> m (t b)
sequence :: Monad m => t (m a) -> m (t a)
{-# MINIMAL traverse | sequenceA #-}
instance Traversable []
...
La fonction traverse
permet de généraliser les “map” et les “fold”. En effet,
on lui passe une fonction a -> f b
qui permet à la fois de transformer (map)
les éléments de a
vers b
et à la fois de réduire (fold) les éléments via
l’applicative f
.
On notera que mapM
(resp. sequence
) est l’équivalent de traverse
(resp.
sequenceA
) mais pour le cas, plus restreint, des monades.
Implémenter des “map” avec traverse
Soit le mapping suivant, qui multiplie par 2 les nombres d’une liste :
> fmap (*2) [1, -2, 3, -4]
ghci2,-4,6,-8] [
On peut écrire un mapping équivalent en utilisant traverse
.
Exemple avec l’applicative State
Le type State s a
permet de représenter un état de type s
et un résultat de
type a
. Par exemple, la fonction suivante ne stocke pas d’état mais retourne
un résultat de type Int
:
mul2State :: Int -> State () Int
= pure . (*2) mul2State
Si on utilise cette fonction pour “traverser” une liste, on obtient un State
sans état et de résultat une liste d’entiers :
> :t traverse mul2State [1, -2, 3, -4]
ghcitraverse mul2State [1,-2,3,-4] :: State () [Int]
On peut donc évaluer ce State
et récupérer son résultat :
> runState (traverse mul2State [1, -2, 3, -4]) ()
ghci2,-4,6,-8],())
([
> evalState (traverse mul2State [1, -2, 3, -4]) ()
ghci2,-4,6,-8] [
Ce qui correspond bien au mapping voulu.
Exemple avec l’applicative Identity
Au lieu d’utiliser State
, on peut également utiliser l’applicative Identity
suivante (qui existe déjà dans
Data.Functor.Identity) :
newtype Identity a = Identity { runIdentity :: a }
instance Functor Identity where
fmap f (Identity x) = Identity (f x)
instance Applicative Identity where
pure x = Identity x
Identity f <*> Identity x = Identity (f x)
L’applicative Identity
ne fait rien de particulier. Elle transmet sa valeur à
l’identique et permet également d’y mapper une fonction.
On peut écrire une fonction pour multiplier un élément par 2, dans le
contexte Identity
.
mul2Identity :: Int -> Identity Int
= Identity . (*2) mul2Identity
Si on traverse une liste avec cette fonction, on obtient la liste où chaque
élément est multiplié par 2, dans le contexte Identity
.
> traverse mul2Identity [1, -2, 3, -4]
ghciIdentity [2,-4,6,-8]
> runIdentity $ traverse mul2Identity [1, -2, 3, -4]
ghci2,-4,6,-8] [
Implémenter fmap à partir de traverse
D’une façon plus générale, on peut implémenter fmap
à partir de traverse
et
de l’applicative Identity
.
myFmap :: (Traversable t) => (a -> b) -> t a -> t b
= runIdentity . traverse (Identity . f) myFmap f
Exemple d’utilisation :
> myFmap (*2) [1, -2, 3, -4]
ghci2,-4,6,-8] [
Implémenter des “fold” avec traverse
Soit la réduction suivante, qui calcule la somme des nombres positifs d’une liste :
> foldl (\acc x -> acc + max 0 x) 0 [1, -2, 3, -4]
ghci4
On peut écrire une réduction équivalents en utilisant traverse
.
Exemple avec l’applicative State
La réduction consiste à mettre à jour un résultat, selon les éléments
successivement parcourus. Pour cela, on peut utiliser l’état d’un State
:
positiveState :: Int -> State Int ()
= modify (+ max 0 x) positiveState x
Si on utilise cette fonction pour “traverser” une liste, on obtient un State
dont l’état final sera la somme voulue, et sans résultat :
> runState (traverse positiveState [1, -2, 3, -4]) 0
ghci4)
([(),(),(),()],
> execState (traverse positiveState [1, -2, 3, -4]) 0
ghci4
Ce qui correspond bien à la réduction voulue.
Exemple avec l’applicative Const
Au lieu d’utiliser State
, on peut également utiliser l’applicative Const
suivante (qui existe déjà dans
Data.Functor.Const) :
newtype Const a b = Const { getConst :: a }
instance Functor (Const a) where
fmap _ (Const x) = Const x
instance Monoid a => Applicative (Const a) where
pure _ = Const mempty
Const x <*> Const y = Const (x `mappend` y)
L’applicative Const
permet de contenir et de mettre à jour une valeur de type
a
, tout en ignorant une valeur de type b
.
Pour implémenter notre réduction, on peut utiliser cette applicative pour
contenir un monoïde Sum
. Ainsi, les élements parcourus seront ignorés mais on
pourra mettre à jour le contexte Const
selon Sum
:
positiveSum :: Int -> Const (Sum Int) ()
= Const . Sum . max 0 positiveSum
Si on traverse une liste avec cette fonction, on obtient la liste où chaque élément est ignoré mais le contexte mis à jour.
> traverse positiveSum [1, -2, 3, -4]
ghciConst (Sum {getSum = 4})
> getConst $ traverse positiveSum [1, -2, 3, -4]
ghciSum {getSum = 4}
Implémenter foldMap à partir de traverse
D’une façon plus générale, on peut implémenter foldMap
à partir de traverse
et de l’applicative Const
.
myFoldMap :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
= getConst . traverse (Const . f) myFoldMap f
Exemple d’utilisation :
> myFoldMap (Sum . max 0) [1, -2, 3, -4]
ghciSum {getSum = 4}
Instancier un type Traversable
Instanciation manuelle
On peut instancier la classe Traversable
pour nos propres types. Par exemple,
considérons le type Tree a
suivant :
data Tree a
= Leaf
| Node (Tree a) a (Tree a)
deriving (Foldable, Functor, Show)
Tree a
définit un arbre binaire polymorphe. Il peut prendre une valeur Leaf
ou une valeur Node
avec un sous-arbre gauche, une donnée de type a
et un
sous-arbre droit.
Tree a
instancie Functor
et Foldable
. Pour instancier Traversable
, il
nous reste donc à écrire la fonction traverse
de type :
traverse :: Applicative f => (a -> f b) -> Tree a -> f (Tree b)
Traverser un Leaf
est trivial. Pour un Node
, il suffit de traverser le
sous-arbre gauche, appliquer la fonction sur la donnée du noeud, traverser le
sous-arbre droit puis retourner un Node
avec ces trois résultats.
Par exemple, en “notation do” (disponible avec l’extension de langage
ApplicativeDo
) :
instance Traversable Tree where
traverse _ Leaf = pure Leaf
traverse f (Node l x r) = do
<- traverse f l
l' <- f x
x' <- traverse f r
r' pure $ Node l' x' r'
Ou alors, en “style applicatif” :
instance Traversable Tree where
traverse _ Leaf = pure Leaf
traverse f (Node l x r) = Node <$> traverse f l <*> f x <*> traverse f r
On notera que, pour être correcte, l’implémentation de traverse
doit
respecter certaines lois (voir Haskell/Traversable
(wikibooks) ou
Data.Traversable
(hackage)).
Instanciation automatique
Alternativement, on peut utiliser l’extension DeriveTraversable
et instancier
automatiquement la classe Traversable
:
{-# LANGUAGE DeriveTraversable #-}
data Tree a
= Leaf
| Node (Tree a) a (Tree a)
deriving (Foldable, Functor, Show, Traversable)
Exemples d’utilisation
Une fois la classe Traversable
instanciée, on peut désormais traverser des
Tree a
. Par exemple, pour mapper une fonction :
> t1 = Node (Node Leaf 20 Leaf) (-42) (Node Leaf 22 Leaf)
ghci
> traverse (Identity . (*2)) t1
ghciIdentity (Node (Node Leaf 40 Leaf) (-84) (Node Leaf 44 Leaf))
Ou bien pour calculer une réduction :
> traverse (Const . Sum . max 0) t1
ghciConst (Sum {getSum = 42})
Ou encore les deux à la fois :
> f x = modify (+ max 0 x) >> pure (x*2)
ghci
> runState (traverse f t1) 0
ghciNode (Node Leaf 40 Leaf) (-84) (Node Leaf 44 Leaf),42) (
Conclusion
En Haskell, la classe Traversable
implémente la notion d’itérateur, notamment
via la fonction traverse
. Cette dernière permet de traverser une structure de
données selon un contexte d’Applicative
, ce qui permet de réaliser à la fois
un mapping et une réduction. La classe Traversable
est assez classique en
Haskell et peut également être instanciée pour de nouveaux types, manuellement
ou automatiquement.