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, [])
        (n:ns) -> (n==42, ns)

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
        (v2, s2) = count42 s1
        (v3, s3) = count42 s2
    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
get = State $ \s -> (s, s)

put :: s -> State s ()
put s = State $ \_ -> ((), 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
            (a2, s2) = act2 s1
        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
count42 = do
    s0 <- get
    case s0 of
        [] -> return False
        (n:ns) -> put ns >> return (n==42)

rep3Count42 :: State [Int] (Bool, Bool, Bool)
rep3Count42 = (,,) <$> count42 <*> count42 <*> count42

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
get = StateT $ \s -> return (s, s)

put :: Monad m => s -> StateT s m ()
put s = StateT $ \_ -> return ((), 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
        (a1, s1) <- act s
        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
        (a1, s1) <- act1 s
        (a2, s2) <- act2 s1
        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
        (a1, s1) <- act s
        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
    lift c = StateT $ \s -> do
        x <- c
        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
count42 = do
    s0 <- get
    case s0 of
        [] -> return False
        (n:ns) -> put ns >> return (n==42)

rep3Count42 :: StateT [Int] IO (Bool, Bool, Bool)
rep3Count42 = do
    lift $ putStrLn "inside rep3Count42"
    (,,) <$> count42 <*> count42 <*> count42

Exemple d’exécution :

$ ghci statet2.hs 

*Main> runStateT count42 [42, 13]
(True,[13])

*Main> runStateT rep3Count42 [42, 13]
inside rep3Count42
((True, 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
    get   = StateT $ \s -> return (s,s)
    put s = StateT $ \_ -> return ((),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
    liftIO = lift . 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
count42 = do
    s0 <- get
    case s0 of
        [] -> return False
        (n:ns) -> put ns >> return (n==42)

rep3Count42 :: (MonadState [Int] m, MonadIO m) => m (Bool, Bool, Bool)
rep3Count42 = do
    liftIO $ putStrLn "inside rep3Count42"
    (,,) <$> 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
count42 = do
    s0 <- get
    case s0 of
        [] -> return False
        (n:ns) -> put ns >> return (n==42)

rep3Count42 :: (MonadState [Int] m, MonadIO m) => m (Bool, Bool, Bool)
rep3Count42 = do
    liftIO $ putStrLn "inside rep3Count42"
    (,,) <$> count42 <*> count42 <*> count42

main :: IO ()
main = do
    runStateT count42 [42, 13] >>= print
    runStateT rep3Count42 [42, 13] >>= print

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