Free Monad (ou pas) en Haskell (1)

Voir aussi : video youtube - code source

Cet article introduit les free monads en Haskell : intuition, définition, utilisation, alternatives. Il sera complété par un second article, illustrant comment combiner des free monads.

Free Monad

Intuition

Les free monads sont des types de données particuliers qui permettent de structurer du code. Intuitivement, une free monad implémente une structure d’arbre ou de liste qu’on peut ensuite traiter ou interpréter de différentes façons. Par exemple, les free monads permettent d’implémenter des EDSL (langages dédiés) ou des systèmes d’effets.

Définition

En Haskell, on peut définir les free monads via le type suivant :

data Free f a
  = Pure a
  | Free (f (Free f a))

Pour l’instant, disons que le type Free permet de combiner des foncteurs de type f et qui vont produire une valeur de type a.

Le type Free peut instancier les classes Functor, Applicative et Monad :

instance Functor f => Functor (Free f) where
  fmap g (Pure r) = Pure (g r)
  fmap g (Free x) = Free (fmap (fmap g) x)

instance Functor f => Applicative (Free f) where
  ...

instance Functor f => Monad (Free f) where
  ...

Cela signifie qu’à partir d’un type f de classe Functor, on peut définir un type Free f qui sera automatiquement de classe Functor, Applicative et Monad. Ainsi, on dit parfois que Free permet d’avoir une monade gratuitement (for free), à partir d’un simple foncteur.

Intuition avec les listes

Si on revient à la définition du type Free, on peut s’intéresser à sa nature récursive et la comparer à une définition de liste :

data Free f a = Pure a | Free (f (Free f a))
data List   a = Nil    | Cons  a (List a)

On peut donc voir une liste comme une valeur inserée devant une sous-liste (un chainage de valeurs). De même, on peut voir un Free comme un foncteur appliqué à un autre Free (une imbrication d’évaluations de foncteur).

Intuition avec les monades

On peut également “expliquer” les free monad en les rapprochant des monades “classiques”. Pour rappel, avec une monad m, on a l’opérateur >>= (appelé “bind” et qui permet de chainer des actions), que l’on peut définir avec les fonctions join et fmap :

(>>=) :: m a -> (a -> m b) -> m b
(>>=) x g = join (fmap g x)

join :: m (m a) -> m a
...

fmap :: (a -> b) -> m a -> m b
...

Autrement dit, avec des monades classiques, on applique l’action (avec fmap) et on “applatit” l’imbrication de monades (avec join). On peut donc voir les free monads comme des monades classiques dont on conserve la structure d’imbrications pour pouvoir l’interpréter (l’applatir) plus tard, et éventuellement de différentes façons.

Ainsi, on a en fait une monade libre (free monad) dans le sens où elle n’est pas directement liée à une implémentation/signification particulière. Ce lien sera fait plus tard, lors de l’interprétation de la free monad.

Quelques fonctions sur les free monads

La bibliothèque free propose une implémentation des free monads ainsi que de nombreux autres types et fonctions bien pratiques.

On peut noter la fonction liftF, qui permet de construire une free monad à partir d’un foncteur :

liftF :: Functor f => f a -> Free f a
liftF x = Free $ fmap return x

et la fonction foldFree, qui permet d’appliquer un interpréteur sur une free monad :

foldFree
  :: (Functor f, Monad m)
  => (forall t. f t -> m t)
  -> Free f a
  -> m a
foldFree _ (Pure r) = return r
foldFree g (Free x) = do
  y <- g x 
  foldFree g y

Exemple (avec des Free Monads)

On veut implémenter un EDSL de systéme de fichiers : lister les fichiers (filesFs), créer un dossier (filesMkdir) et supprimer un dossier (filesRmdir).

Modèle

Tout d’abord, on écrit un type FilesF (de classe Functor) qui modélise l’EDSL :

data FilesF a
  = FilesLs ([FilePath] -> a)
  | FilesMkdir FilePath a     -- équivalent à: FilesMkdir FilePath (() -> a)
  | FilesRmdir FilePath a
  deriving (Functor)

Les valeurs du type FilesF peuvent prendre des paramètres mais doivent toujours retourner une fonction (qui sera appliquée sur le reste de l’imbrication). Par exemple, la valeur FilesLs ([FilePath] -> a) signifie qu’on ne prend pas de paramètre mais qu’on retourne un [FilePath] qui sera passé au reste de l’imbrication pour produire, à la fin, une valeur de type a. Autre exemple, FilesMkdir FilePath a signifie qu’on prend un paramètre de type FilePath et qu’on ne retourne rien (ou plutôt qu’on retourne une fonction () -> a qui de prend aucun paramètre et retourne une valeur de type a).

À partir du foncteur FilesF, on peut créer automatiquement la free monad correspondante :

type Files = Free FilesF

Pour simplifier l’utilisation de notre EDSL, on peut écrire des fonctions qui construisent les valeurs de base de notre free monad Files :

filesLs :: Files [FilePath]
filesLs = liftF $ FilesLs id

filesMkdir :: FilePath -> Files ()
filesMkdir fp = liftF $ FilesMkdir fp ()

filesRmdir :: FilePath -> Files ()
filesRmdir fp = liftF $ FilesRmdir fp ()

Application

On a désormais les primitives de notre EDSL, utilisables comme un Functor, une Applicative ou une Monad. Par exemple, on peut définir une application app2 qui crée un dossier “output1”, liste les fichiers puis supprime le dossier “output1”, en utilisant la notation-do :

app2 :: Files [FilePath]
app2 = do
  filesMkdir "output1"
  files <- filesLs
  filesRmdir "output1"
  return files

Interpréteur 1

Il ne reste plus qu’à écrire un interpréteur pour pouvoir réaliser/calculer une application écrite avec notre EDSL.

Par exemple, pour réaliser réellement les opérations sur le système de fichiers, on peut écrire l’interpréteur runFilesFs suivant, qui affiche des messages d’information et appelle les fonctions nécessaires du module System.Directory.

runFilesFs :: FilesF a -> IO a
runFilesFs (FilesLs next) = do
  putStrLn "running filesLs"
  files <- listDirectory "."
  return $ next files
runFilesFs (FilesMkdir fp next) = do
  putStrLn "running filesMkdir"
  createDirectory fp
  return next
runFilesFs (FilesRmdir fp next) = do
  putStrLn "running filesRmdir"
  removeDirectory fp
  return next

Exemple d’exécution :

$ ghci myfiles-free.hs 

*Main> foldFree runFilesFs app2
running filesMkdir
running filesLs
running filesRmdir
["Free.hs","myfiles-free.hs","myfiles-mtl.hs","shell.nix","tmp","output1"]

Interpréteur 2

Les free monads permettent d’écrire facilement différents interpréteurs. Par exemple, l’interpréteur runFilesMock suivant simule les opérations sans les réalisés réellement sur le système de fichiers.

runFilesMock :: FilesF a -> IO a
runFilesMock (FilesLs next) = do
  putStrLn "mock filesLs"
  return $ next ["mock1", "mock2"]
runFilesMock (FilesMkdir fp next) = do
  putStrLn $ "mock filesMkdir " <> fp
  return next
runFilesMock (FilesRmdir fp next) = do
  putStrLn $ "mock filesRmdir " <> fp
  return next

Exemple d’exécution :

$ ghci myfiles-free.hs 

*Main> foldFree runFilesMock app2
mock filesMkdir output1
mock filesLs
mock filesRmdir output1
["mock1","mock2"]

Interpréteur 3

Enfin, on peut également spécifier la monade utilisée pour l’interprétation. Les deux interpréteurs précédents utilisaient la monade IO mais on peut vouloir utiliser une monade plus spécifique. Par exemple, l’interpréteur runFilesPure suivant simule les opérations et stocke les messages d’information, via la monade State [String]. Ceci peut être pratique pour exécuter l’interprétation dans du code pur ou encore tester automatiquement le code.

runFilesPure :: FilesF a -> State [String] a
runFilesPure (FilesLs next) = do
  modify' (++ ["filesLs"])
  return $ next ["pure1", "pure2"]
runFilesPure (FilesMkdir fp next) = do
  modify' (++ ["filesMkdir " <> fp])
  return next
runFilesPure (FilesRmdir fp next) = do
  modify' (++ ["filesRmdir " <> fp])
  return next

Exemple d’exécution :

$ ghci myfiles-free.hs 

*Main> (a, s) = runState (foldFree runFilesPure app2) []

*Main> a
["pure1","pure2"]

*Main> s
["filesMkdir output1","filesLs","filesRmdir output1"]

Exemple (en style Tagless Final)

A titre de comparaison, voici comment on pourrait implémenter notre EDSL en style Tagless Final (voir le tuto 62),

Modèle

Pour modéliser notre langage, on définit une classe MonadFiles qui indique le type des fonctions primitives.

class Monad m => MonadFiles m where
  filesLs :: m [FilePath]
  filesMkdir :: FilePath -> m ()
  filesRmdir :: FilePath -> m ()

Application

On notera que MonadFiles dérive de Monad. On peut donc, comme avec les free monads, écrire une application dans notre EDSL en utilisant la notation-do :

app2 :: MonadFiles m => m [FilePath]
app2 = do
  filesMkdir "output1"
  files <- filesLs
  filesRmdir "output1"
  return files

Interpréteur 1

Il ne reste plus qu’à écrire les interpréteurs. Pour cela, on définit un wrapper de type, avec newtype, pour lequel on instancie notre monade MonadFiles avec le comportement voulu. Par exemple, pour réaliser les opérations réelles sur le système de fichiers, tout en affichant des messages d’information :

newtype FilesFs m a = FilesFs { runFilesFs :: m a }
  deriving (Functor, Applicative, Monad, MonadIO)

instance MonadIO m => MonadFiles (FilesFs m) where
  filesLs = do
    liftIO $ putStrLn "running filesLs"
    liftIO $ listDirectory "."
  filesMkdir fp =  do
    liftIO $ putStrLn "running filesMkdir"
    liftIO $ createDirectory fp
  filesRmdir fp =  do
    liftIO $ putStrLn "running filesRmdir"
    liftIO $ removeDirectory fp

Exemple d’exécution :

$ ghci myfiles-mtl.hs 

*Main> runFilesFs app2
running filesMkdir
running filesLs
running filesRmdir
["Free.hs","myfiles-free.hs","myfiles-mtl.hs","shell.nix","tmp","output1"]

Interpréteur 2

Ici aussi, on peut facilement écrire d’autre interpréteur. Il suffit d’écrire un autre wrapper de types, avec son instance à MonadFiles. Par exemple, pour simuler les opérations sans les réaliser réellement :

newtype FilesMock m a = FilesMock { runFilesMock :: m a }
  deriving (Functor, Applicative, Monad, MonadIO)

instance MonadIO m => MonadFiles (FilesMock m) where
  filesLs = do
    liftIO $ putStrLn "mock filesLs"
    return ["mock1", "mock2"]
  filesMkdir fp = 
    liftIO $ putStrLn $ "mock filesMkdir " <> fp
  filesRmdir fp = 
    liftIO $ putStrLn $ "mock filesRmdir " <> fp

Exemple d’exécution :

$ ghci myfiles-mtl.hs 

*Main> runFilesMock app2
mock filesMkdir output1
mock filesLs
mock filesRmdir output1
["mock1","mock2"]

Interpréteur 3

Enfin, on peut également utiliser une monade de base plus spécifique que IO, comme State [String] :

newtype FilesPure m a = FilesPure { runFilesPure :: State [String] a}
  deriving (Functor, Applicative, Monad, MonadState [String])

instance MonadFiles (FilesPure m) where
  filesLs = do
    modify' (++ ["filesLs"])
    return ["pure1", "pure2"]
  filesMkdir fp = do
    modify' (++ ["filesMkdir " <> fp])
    return ()
  filesRmdir fp = do
    modify' (++ ["filesRmdir " <> fp])
    return ()

Exemple d’exécution :

$ ghci myfiles-mtl.hs 

*Main> (a, s) = runState (runFilesPure app2) []

*Main> a
["pure1","pure2"]

*Main> s
["filesMkdir output1","filesLs","filesRmdir output1"]

Conclusion

La free monad peut être vue comme une imbrication d’applications de foncteurs. Ainsi, à partir d’un simple foncteur, on obtient une monade gratuitement. Plus exactement, on a une monade libre dont on peut lier l’interprétation plus tard et selon différentes implémentations.

La free monad est une contruction assez pratique et élégante mais peut poser des problèmes de performances ou d’extensibilité. C’est pourquoi, on lui préfère parfois des variantes (Church-encoded free monad, freer monad, etc) ou le style Tagless Final.

Quelques liens intéressants :

• What are free monads?
• Free monad considered harmful
• A Modern Architecture for FP
• Introduction to Free Monads