Monade State, Transformateur et MTL, en Haskell
Voir aussi : video youtube - video peertube - code source
Au tutoriel 59, on a vu comment utiliser les transformateurs de monade pour “empiler” les fonctionnalités voulues, via le système de types. On va maintenant détailler la monade State
et voir comment l’implémenter avec des transformateurs et avec une classe de type “à la MTL”.
Simuler une variable mutable
Avec un langage fonctionnel pur comme Haskell, on ne peut pas “modifier une variable”. Une solution classique est de prendre la variable initiale et de retourner la variable “modifiée”, en plus du résultat. Par exemple, la fonction count42
suivante consomme un entier de la liste courante et retourne si on a consommé la valeur 42.
count42 :: [Int] -> (Bool, [Int])
=
count42 s0 case s0 of
-> (False, [])
[] :ns) -> (n==42, ns) (n
Cependant, cette technique nécessite de gérer explicitement l’état “modifiable” tout au long du code. Par exemple, la fonction rep3Count42
suivante appelle count42
trois fois successivement et retourne les résultats dans un triplet.
rep3Count42 :: [Int] -> ((Bool, Bool, Bool), [Int])
=
rep3Count42 s0 let (v1, s1) = count42 s0
= count42 s1
(v2, s2) = count42 s2
(v3, s3) in ((v1,v2,v3), s3)
Exemple d’exécution :
$ ghci statet0.hs
*Main> count42 [42, 13]
True,[13])
(
*Main> rep3Count42 [42, 13]
True,False,False),[]) ((
La monade State
La monade State
permet de simuler un état mutable simplement. Concrètement, on peut l’implémenter par un type polymorphe State s a
où s
est le type de l’état et a
le type de la valeur produite. Le type State s a
encapsule simplement une fonction runState
qui permet de passer d’un état à l’état suivant, en produisant une valeur. On définit également les fonctions get
et put
qui permettent respectivement de récupérer et de définir l’état d’un State
.
newtype State s a = State { runState :: s -> (a, s) }
get :: State s s
= State $ \s -> (s, s)
get
put :: s -> State s ()
= State $ \_ -> ((), s) put s
L’intérêt de ce type State
est qu’il correspond à des structures plus évoluées, notamment Functor
, Applicative
et Monad
. En Haskell, on peut implémenter cela facilement en instanciant les classes de types correspondantes.
instance Functor (State s) where
-- fmap :: (a -> b) -> State s a -> State s b
fmap f (State act) = State $ \s ->
let (a1, s1) = act s
in (f a1, s1)
instance Applicative (State s) where
-- pure :: a -> State s a
pure a = State $ \s -> (a, s)
-- (<*>) :: State s (a -> b) -> State s a -> State s b
State act1 <*> State act2 = State $ \s ->
let (a1, s1) = act1 s
= act2 s1
(a2, s2) in (a1 a2, s2)
instance Monad (State s) where
-- (>>=) :: State s a -> (a -> State s b) -> State s b
State act >>= k = State $ \s ->
let (a1, s1) = act s
in runState (k a1) s1
On peut ensuite profiter des fonctionnalités que fournit Haskell pour ces structures. Par exemple, on peut réécrire, plus simplement, la fonction coun42
en “notation do” et la fonction rep3Count42
en “style applicatif”.
count42 :: State [Int] Bool
= do
count42 <- get
s0 case s0 of
-> return False
[] :ns) -> put ns >> return (n==42)
(n
rep3Count42 :: State [Int] (Bool, Bool, Bool)
= (,,) <$> count42 <*> count42 <*> count42 rep3Count42
Exemple d’exécution :
$ ghci statet1.hs
*Main> runState count42 [42, 13]
True,[13])
(
*Main> runState rep3Count42 [42, 13]
True, False, False),[]) ((
Le transformateur StateT
Comme expliqué dans le tutoriel précédent, il peut être intéressant de définir un transformateur plutôt qu’une monade. Ceci permet notamment “d’empiler des monades”. Ainsi, pour implémenter un transformateur StateT
, on ajoute un paramètre de type m
(la monade sur laquelle empiler) et on modifie les fonctions get
et put
de façon à encapsuler m
.
newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }
get :: Monad m => StateT s m s
= StateT $ \s -> return (s, s)
get
put :: Monad m => s -> StateT s m ()
= StateT $ \_ -> return ((), s) put s
De même, on modifie les instances de Functor
, Applicative
et Monad
pour StateT
.
instance Monad m => Functor (StateT s m) where
-- fmap :: (a -> b) -> StateT s m a -> StateT s m b
fmap f (StateT act) = StateT $ \s -> do
<- act s
(a1, s1) return (f a1, s1)
instance Monad m => Applicative (StateT s m) where
-- pure :: a -> StateT s a
pure a = StateT $ \s -> return (a, s)
-- (<*>) :: StateT s m (a -> b) -> StateT s m a -> StateT s m b
StateT act1 <*> StateT act2 = StateT $ \s -> do
<- act1 s
(a1, s1) <- act2 s1
(a2, s2) return (a1 a2, s2)
instance Monad m => Monad (StateT s m) where
-- (>>=) :: StateT s m a -> (a -> StateT s m b) -> StateT s m b
StateT act >>= k = StateT $ \s -> do
<- act s
(a1, s1) runStateT (k a1) s1
On instancie également MonadTrans
, ce qui permet de “lifter” des actions de la monade m
pour pouvoir l’utiliser dans StateT
.
instance MonadTrans (StateT s) where
-- lift :: m a -> StateT s m a
= StateT $ \s -> do
lift c <- c
x return (x, s)
Ainsi, on peut, par exemple, implémenter rep3Count42
“par dessus” IO
pour ajouter un affichage, et rendre count42
empilable sur n’importe quelle monade.
count42 :: Monad m => StateT [Int] m Bool
= do
count42 <- get
s0 case s0 of
-> return False
[] :ns) -> put ns >> return (n==42)
(n
rep3Count42 :: StateT [Int] IO (Bool, Bool, Bool)
= do
rep3Count42 $ putStrLn "inside rep3Count42"
lift <$> count42 <*> count42 <*> count42 (,,)
Exemple d’exécution :
$ ghci statet2.hs
*Main> runStateT count42 [42, 13]
True,[13])
(
*Main> runStateT rep3Count42 [42, 13]
inside rep3Count42True, False, False),[]) ((
Le style MTL
La bibliothèque MTL implémente des transformateurs classiques, ainsi que des classes de types correspondantes.
Par exemple pour StateT
, on peut implémenter les fonctions get
et put
via une classe de type MonadState
.
{-# LANGUAGE FlexibleContexts, FlexibleInstances, FunctionalDependencies #-}
class Monad m => MonadState s m | m -> s where
get :: m s
put :: s -> m ()
Ainsi, MonadState s m
est une classe où m
doit être de classe Monad
et où m
détermine le type s
.
On peut alors définir StateT
et lui faire instancier MonadState
.
newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }
instance (Monad m) => MonadState s (StateT s m) where
= StateT $ \s -> return (s,s)
get = StateT $ \_ -> return ((),s) put s
Ainsi que les classes de la section précédente.
instance Monad m => Functor (StateT s m) where
-- ...
instance Monad m => Applicative (StateT s m) where
-- ...
instance Monad m => Monad (StateT s m) where
-- ...
instance MonadTrans (StateT s) where
-- ...
Enfin, on peut instancier les classes sur lesquelles on veut empiler, par exemple MonadIO
.
instance MonadIO m => MonadIO (StateT s m) where
-- liftIO :: IO a -> StateT s m a
= lift . liftIO liftIO
On peut maintenant écrire rep3Count42
et count42
comme des actions dans des monades m
, pour lesquelles on précise les contraintes de type voulues (MonadState [Int]
, MonadIO
…).
count42 :: (MonadState [Int] m) => m Bool
= do
count42 <- get
s0 case s0 of
-> return False
[] :ns) -> put ns >> return (n==42)
(n
rep3Count42 :: (MonadState [Int] m, MonadIO m) => m (Bool, Bool, Bool)
= do
rep3Count42 $ putStrLn "inside rep3Count42"
liftIO <$> count42 <*> count42 <*> count42 (,,)
Avec la MTL
Bien évidemment la bibliothèque MTL propose déjà une implémentation de StateT
et de MonadState
. On peut donc écrire tout simplement :
{-# LANGUAGE FlexibleContexts #-}
import Control.Monad.IO.Class (liftIO, MonadIO)
import Control.Monad.State.Class (MonadState)
import Control.Monad.State.Lazy (get, put, runStateT)
count42 :: (MonadState [Int] m) => m Bool
= do
count42 <- get
s0 case s0 of
-> return False
[] :ns) -> put ns >> return (n==42)
(n
rep3Count42 :: (MonadState [Int] m, MonadIO m) => m (Bool, Bool, Bool)
= do
rep3Count42 $ putStrLn "inside rep3Count42"
liftIO <$> count42 <*> count42 <*> count42
(,,)
main :: IO ()
= do
main 42, 13] >>= print
runStateT count42 [42, 13] >>= print runStateT rep3Count42 [
Conclusion
La monade State
définit un contexte de “variable mutable”. On peut l’implémenter par un type algébrique contenant une fonction qui prend l’état courant et retourne le nouvel état ainsi qu’une valeur résultat.
On peut également l’implémenter sous forme de transformateur de monade, en ajoutant un paramètre de type (la monade de base) au type algébrique. Ceci permet de définir une pile de monades, avec les fonctionnalités désirées, vérifiée par le système de types.
Enfin, on peut associer des classes de types aux différents transformateurs de monade pour définir leurs fonctions de base et les fonctions de transformation. Ceci permet de simplifier l’écriture du code (le style MTL), qui se résume à spécifier les contraintes de type correspondant aux monades désirées.
Voir aussi : FPComplete Monad Transformers