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 :

ghci> :t getEnv "HOME"
getEnv :: IO String

ghci> getEnv "HOME"
"/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 :

ghci> :t fmap getEnv ["HOME", "USER"]
fmap 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 :

ghci> :t sequenceA $ fmap getEnv ["HOME", "USER"]
sequenceA $ fmap getEnv ["HOME", "USER"] :: IO [String]

ghci> sequenceA $ fmap getEnv ["HOME", "USER"]
["/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.

ghci> :t traverse getEnv ["HOME", "USER"]
traverse getEnv ["HOME", "USER"] :: IO [String]

ghci> traverse getEnv ["HOME", "USER"]
["/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 :

ghci> fmap (*2) [1, -2, 3, -4]
[2,-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
mul2State = pure . (*2)

Si on utilise cette fonction pour “traverser” une liste, on obtient un State sans état et de résultat une liste d’entiers :

ghci> :t traverse mul2State [1, -2, 3, -4]
traverse mul2State [1,-2,3,-4] :: State () [Int]

On peut donc évaluer ce State et récupérer son résultat :

ghci> runState (traverse mul2State [1, -2, 3, -4]) ()
([2,-4,6,-8],())

ghci> evalState (traverse mul2State [1, -2, 3, -4]) ()
[2,-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
mul2Identity = Identity . (*2)

Si on traverse une liste avec cette fonction, on obtient la liste où chaque élément est multiplié par 2, dans le contexte Identity.

ghci> traverse mul2Identity [1, -2, 3, -4]
Identity [2,-4,6,-8]

ghci> runIdentity $ traverse mul2Identity [1, -2, 3, -4]
[2,-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
myFmap f = runIdentity . traverse (Identity . f)

Exemple d’utilisation :

ghci> myFmap (*2) [1, -2, 3, -4]
[2,-4,6,-8]

Implémenter des “fold” avec traverse

Soit la réduction suivante, qui calcule la somme des nombres positifs d’une liste :

ghci> foldl (\acc x -> acc + max 0 x) 0 [1, -2, 3, -4]
4

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 ()
positiveState x = modify (+ max 0 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 :

ghci> runState (traverse positiveState [1, -2, 3, -4]) 0
([(),(),(),()],4)

ghci> execState (traverse positiveState [1, -2, 3, -4]) 0
4

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) ()
positiveSum = Const . Sum . max 0

Si on traverse une liste avec cette fonction, on obtient la liste où chaque élément est ignoré mais le contexte mis à jour.

ghci> traverse positiveSum [1, -2, 3, -4]
Const (Sum {getSum = 4})

ghci> getConst $ traverse positiveSum [1, -2, 3, -4]
Sum {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
myFoldMap f = getConst . traverse (Const . f)

Exemple d’utilisation :

ghci> myFoldMap (Sum . max 0) [1, -2, 3, -4]
Sum {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
    l' <- traverse f l
    x' <- f x
    r' <- traverse f 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 :

ghci> t1 = Node (Node Leaf 20 Leaf) (-42) (Node Leaf 22 Leaf)

ghci> traverse (Identity . (*2)) t1
Identity (Node (Node Leaf 40 Leaf) (-84) (Node Leaf 44 Leaf))

Ou bien pour calculer une réduction :

ghci> traverse (Const . Sum . max 0) t1
Const (Sum {getSum = 42})

Ou encore les deux à la fois :

ghci> f x = modify (+ max 0 x) >> pure (x*2)

ghci> runState (traverse f t1) 0
(Node (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.