Monad Transformer: WriterT

Aujourd’hui nous allons voir un cas d’utilisation de monad transformer. Pourquoi avoir besoin de cette abstraction ? Tout simplement pour pouvoir combiner les effets de monades différentes. La monade Writer généralement utilisée pour logguer un calcul dans un language pure (comme Haskell), est extrêmement simple. C’est un tuple composé du type du résultat attendu et du type utilisé pour accumuler les logs. Le type utilisé pour les logs devra être un Monoid, c’est à dire avoir un élément neutre (que l’on nommera zero) et une opération binaire associative (que l’on nommera append).

  trait Monoid[A] {
    def zero: A
    
    def append(x: A, y: A): A
  }

  case class Writer[W, A](a: A, w: W){
    def map[B](f: A => B): Writer[W, B] = this match {
      case Writer(a, w) => Writer(f(a), w)
    }

    def flatMap[B](f: A => Writer[W, B])(implicit W: Monoid[W]): Writer[W, B] = this match {
      case Writer(a, w) => f(a) match {
        case Writer(b, ww) => Writer(b, W.append(w, ww))
      }
    }

    def :++>(ww: W)(implicit W: Monoid[W]): Writer[W, A] = this match {
      case Writer(a, w) => Writer(a, W.append(w, ww))
    }

    def :++>>(f: A => W)(implicit W: Monoid[W]): Writer[W, A] = this match {
      case Writer(a, w) => Writer(a, W.append(f(a), w))
    }

    def written: Writer[W, W] = this match {
      case Writer(_, w) => Writer(w, w)
    }
  }

object Writer {
  implicit def writerMonad[W](implicit W: Monoid[W]): Monad[({type f[x] = Writer[W, x]})#f]{
    def point[A](v: => A): Writer[W, A] = Writer(v, W.zero)

    def bind(fa: Writer[W, A])(f: A => Writer[W, B]) = fa flatMap f
  }
}

Voici maintenant un petit exemple:

def as[A](v: => A): Writer[String, A] = Monad[({type f[x] = Writer[String, x]})#f].point(v)

def foo = for {
  x <- as(1) :++> "J'ajoute 1"
  y <- as(2) :++> ", J'ajoute 2"
} yield x + y

println(foo) // Writer(3, J'ajoute 1, J'ajoute 2)
 

Dans ce cas de figure, l’utilisation de la monade Writer est ridicule mais permet d’en apprécier le fonctionnement. Le véritable objectif est de transformer Writer en Monad Transformer de sorte que d’autres monades aient la possibilité de logger comme Option, Either ou encore List.

Pour cela, il nous faut généraliser Writer. Writer[W, A] est tout simplement vu comme un tuple (A, W). Soit maintenant WriterT (pour Writer Transformer) la version plus générale. Il peut être vu comme F[(A, W)] avec F un type d’ordre supérieur (un type qui accepte un type en paramètre pour créer un nouveau type :D). Pour pouvoir implémenter les mêmes opérations de Writer, il faudra au minimum que F soit un functor voire une monade.


trait Functor[F[_]]{
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

trait Monad[F[_]] extends Functor[F] {
  def point[A](v: => A): F[A]

  def bind(fa: F[A])(f: A => F[B]): F[B]

  def map[A, B](fa: F[A])(f: A => B): F[B] = bind(fa)(a => point(f(a)))
}

sealed trait WriterT[F[_], W, A]{ self =>
  def run: F[(A, W)]

  def map[B](f: A => B)(implicit F: Functor[F]): WriterT[F, W B] =
    WriterT(F.map(run){ case (a, w) =>  (f(a), w) })

  def flatMap[B](f: A => WriterT[F, W, B])(implicit F: Monad[F], W: Monoid[W]): WriterT[F, W, B] = {
    val tmp = F.bind(run){ 
      case (a, w) =>
        F.map(f(a).run){ case (b, ww) => (b, W.append(w, ww)) }
    }
    
    WriterT(tmp)
  }

  def :++>(w: W)(implicit F: Monad[F], W: Monoid[W]): WriterT[F, W, A] =
    flatMap(a => WriterT(F.point((a, w))))

  def :++>>(f: A => W)(implicit F: Monad[F], W: Monoid[W]): WriterT[F, W, A] = 
    flatMap(a => Writer(F.point((a, f(a)))))
  
}

object WriterT{
  def apply[F[_], W, A](v: F[(A, W)]): WriterT[F, W, A] = new WriterT[F, W, A]{
    def run = v
  }

  def lift[F[_], W, A](v: F[A])(implicit F: Functor[F], W: Monoid[W]): WriterT[F, W, A] =
    WriterT(F.map(v)(a => (a, W.zero)))

}

On peut obtenir notre Writer de tout à l’heure en le déclarant ainsi

type Writer[W, A] = WriterT[Id, W, A]

type Id[X] = X

implicit val idMonad = new Monad[Id] {
  def point(v: => A): A = v
  def bind(fa: A)(f: A => B): B = f(fa)
}

En reprenant notre exemple ‘bidon’ de tout à l’heure et en l’adaptant à WriterT, on voit finalement que le type "contenant" à très peu d’importance. Le couplage est extrêmement faible. La seule chose que l’on demande, c’est que le type "contenant" soit une monade.

type M[X] = Option[X] // ou encore List[X]
def as[A](v: => A): WriterT[M, String, A] = Monad[({type f[x] = WriterT[M, String, x]})#f].point(v)

def foo = for {
  x <- as(1) :++> "J'ajoute 1"
  y <- as(2) :++> ", J'ajoute 2"
} yield x + y
 
println(foo.run) // Some(3, J'ajoute 1, J'ajoute 2)

Voici maintenant un exemple un peu plus évolué (mais toujours inutile), incluant un soupçon de validation:

import WriterT._

def isNull[A](x: A): WriterT[Option, String, A] = for {
  a <- lift[Option, String, A](Option(x)) :++>> (r => "la référence est n'est pas null -> "[" + r + "]")
} yield a

println(isNull(1).run) // Some(1, la référence est n'est pas null -> [1])
println(isNull(null).run) // None 

La librairie Scalaz propose une implémentation plus robuste mais l’esprit est le même.

Le principal problème c’est que le système d’inférence de Scala ne fonctionne pas très bien avec ce style (Monad Transformer). En conséquence, certaines combinaisons de monades se retrouvent visuellement polluées par des annotations de types, comme le montre cet exemple avec le type algébrique (\/ via EitherT), équivalent Scalaz d’Either mais en (beaucoup) mieux.

import scalaz._
import std.string._
import scala.math._

object EitherTExample extends Application {
  type Writer[+W, +A] = WriterT[Id, W, A] 
  type EitherTWriterAlias[W, A] = EitherT[({type f[x] = Writer[W, x]})#f, W, A]
  type WriterAlias[A] = Writer[String, A]

  def squareroot(x:Double): EitherTWriterAlias[String, Double] = 
    if (x < 0) EitherT.left[WriterAlias, String, Double]("Can't take squareroot of negative number") 
    else EitherT.right[WriterAlias, String, Double](sqrt(x))

  def inverse(x:Double): EitherTWriterAlias[String, Double] = 
    if (x == 0) EitherT.left[WriterAlias, String, Double]("Can't take inverse of zero ") 
    else EitherT.right[WriterAlias, String, Double](1/x)

  def resultat(x:Double) = for {
    y <- squareroot(x).flatMap(i => EitherT[({type f[x] = Writer[String, x]})#f, String, Double](Writer[String, String \/ Double]("Squareroot ok", \/-(i))))
    z <- inverse(y).flatMap(i => EitherT[({type f[x] = Writer[String, x]})#f, String, Double](Writer[String, String \/ Double]("Inverse ok", \/-(i))))
  } yield z

  println("0 : " + resultat(0.0).run.run)
  println("-1 : " + resultat(-1.0).run.run)
  println("4 : " + resultat(4).run.run)
}

Pour alléger cet inconvénient, J’ai ajouté dans Scalaz 7 deux nouvelles Typeclass MonadWriter (et ListenableMonadWriter). En utilisant les syntaxes spéciales associées, on peut avoir une version plus agréable à l’oeil de l’exemple précédent.

import scalaz._
import std.string._
import syntax.monadWriter._
import scala.math._

object EitherTExample extends Application {
  implicit val monadWriter = EitherT.monadWriter[Writer, String, String]

  def squareroot(x: Double) =
    if (x < 0)
      monadWriter.left[Double]("Can't take squareroot of negative number")
    else
      monadWriter.right[Double](sqrt(x))

  def inverse(x: Double) = 
    if (x == 0)
      monadWriter.left[Double]("Can't take inverse of zero")
    else
      monadWriter.right[Double](1 / x)

  def resultat(x: Double) = for {
    y <- squareroot(x) :++> "Squareroot ok"
    z <- inverse(y)    :++> ", Inverse ok"
  } yield z

  println("0 : " + resultat(0.0).run.run) // (Squareroot ok,-\/(Can't take inverse of zero ))
  println("-1 : " + resultat(-1.0).run.run) // (,-\/(Can't take squareroot of negative number))
  println("4 : " + resultat(4).run.run) // (Squareroot ok, Inverse ok,\/-(0.5))
}

Applicative Functor (Partie II)

Après une petite introduction aux Applicative Functors, nous allons aujourd’hui plus s’intéresser à leurs utilisations dans des situations "réelles". Nous verrons tout au long de l’article:

  1. Le type algébrique Validation
  2. L’abstraction Semigroup
  3. Un exemple de validation de données (un formulaire)

Différencier l’erreur du succès

La validation est certainement le principal point d’entrée pour utiliser une librairie comme Scalaz. En voici une définition:

sealed trait Validation[E, A]{
  def map[B](f: A => B): Validation[E, B] = this match {
    case Success(a) => Success(f(b))
    case Failure(e) => Failure(e)
  }
}
case class Success[E, A](v: A) extends Validation[E, A]
case class Failure[E, A](e: E) extends Validation[E, A]

Certains ne manquerons pas de remarquer que le type ressemble en tout point au type de la librairie standard Scala: Either. Ces types sont identiques ! Pour être plus precis, on dit qu’ils sont isomorphiques. Pour faire simple, cela signifie que nous pouvons définir 2 fonctions dont une Validation[E, A] => Either[E, A] et l’autre Either[E, A] => Validation[E, A]

La première chose vous vous demandez est certainement "Pourquoi définir Validation si ce type est identique à Either ?". La réponse est tout simplement car nous pourrons définir  une implémentation d’applicative pour Validation qui permettra l’accumulation d’erreur, ce que ne permet pas son homologue Either.

Abstraire l’accumulation

Lorsque l’on parle d’accumulation des erreurs, on voit directement des types String ou encore List comme potentiels candidats. Le problème, c’est que la méthode pour accumuler une chaine de caractères n’est pas la même que pour accumuler une liste. Si nous voulons garder le type de l’erreur générique, il nous faut donc trouver une abstraction qui nous permet d’encapsuler cette opération. C’est la que l’abstraction Semigroup rentre en jeu. Un Semigroup est donc une opération binaire associative. Par exemple pour l’ensemble des entiers, l’addition et la multiplication sont des opérations binaires associatives.

Soit le type Semigroup

trait Semigroup[A] {
  def append(x: A, y: A): A
}

Implémentons ce type de classe aux String et aux List

val stringSemigroup = new Semigroup[String]{
  def append(x: String, y: String): String = x + y
}

def listSemigroup[A] = new Semigroup[List[A]]{
  def append(x: List[A], y: List[A]): List[A] = x ::: y
}

Passons à l’implementation de l’applicative de Validation:

def validationApplicative[E, A](implicit E: Semigroup[E]) = new Applicative[({type f[x] = Validation[E, x]})#f]{
  def pure[A](v: => A): Validation[E, A] = Success[E, A](v)

  def ap[A, B](ff: Validation[E, A => B], fa: Validation[E, A]): Validation[E, B] = (ff, fa) match {
    case (Success(f), Success(a))  => Success(f(a))
    case (Failure(e), Success(_))  => Failure(e)
    case (Success(_), Failure(e))  => Failure(e)
    case (Failure(e), Failure(ee)) => Failure(E.append(e, ee)) 
  }
}

Le type anonyme ({type f[x] = Validation[E, x]})#f permet de déclarer un type M[_, _] en N[_] demandé par le type de classe Applicative. Scala ne peut pas convertir implicitement un type de rang 2 en un type de rang 1. Cette notation fonctionne de la même manière que la curryfication. On va partiellement appliquer le type Validation, en fournissant le type E mais en laissant le second type disponible.

Le semigroupe que forme le type E est utilisé lorsque l’on rencontre 2 échecs (Failure) et permet donc l’accumulation d’erreur.

Validation d’un formulaire

Attaquons nous maintenant à un cas concret. Notre objectif est d’à partir de 3 chaines de caractères de construire une entité Person. Si nous n’arrivons pas à la construire, on retourne un message d’erreur au client.

Voici les différentes classes de notre domaine:

sealed trait Sex 
case object Male extends Sex
case object Female extends Sex 

case class Person(name: String, sex: Sex, age: Int)

Définissons nos méthodes de validation

def getAge(s: String): Validation[String, Int] = 
  Option(s).filter(_.forAll(_.isDigit)).map(x => Success(x.toInt)).getOrElse(Failure("provided age is empty or not a number"))

def getName(s: String): Validation[String, String] = 
  Option(s).filter(!_.forAll(_.isWhitespace)).map(Success(_)).getOrElse(Failure("name is empty"))

def getSex(s: String): Validation[String, Sex] = {
  val tmp = Option(s).flatMap { 
    case "M" => Some(Success(Male))
    case "F" => Some(Success(Female))
    case _   => None 
  }

  tmp.getOrElse(Failure("provided sex is empty or invalid")) // lol
}

type VS[A] = Validation[String, A]
def getPerson(name: String, sex: String, age: String): Validation[String, Person] =
  lift3A[VS, Person](getName(name), getSex(sex), getAge(age))(Person(_, _, _))

La méthode liftA3 a été vue dans le précédent article. Voici sa définition:

def liftA3[F[_]: Applicative, A, B, C, D](fa: F[A], fb: f[B], fc: F[C])(f: (A, B, C) => D): F[D] = {
    import Applicative[F]._

    ap(ap(ap(pure(f.curried), fa), fb), fc)
}

Elle nous permet de combiner le résultat de 3 mêmes types qui possèdent une instance d’Applicative avec une fonction pure.

Dans la librairie Scalaz, Il y a une syntaxe particulière pour les applicatives qui donne ceci

def getPerson(name: String, sex: String, age: String): Validation[String, Person] =
  getName(name) |@| getSex(sex) |@| getAge(age) apply (Person(_, _, _))

Voici les différents résultats que nous aurions en exécutant la méthode "getPerson":

  getPerson("Yorick", "25", "M") // Success(Person(Yorick, 25, Male))
  getPerson("", "25", "M") // Failure(name is empty)
  getPerson("", "25", "toto") // Failure(name is empty, provided sex is empty or invalid)
  getPerson("", "fsdf", "toto") // Failure(name is empty, provided age is empty or not a number, provided sex is empty or invalid)

Cette accumulation d’erreur n’est possible qu’en utilisant un style applicatif. En utilisant une monade, à la première erreur l’évaluation de l’expression de "getPerson" se serait arrêtée.

Introduction aux Applicative Functors (Partie I)

Aujourd’hui j’aimerais parler des applicative functors. C’est une abstraction qui est souvent ignorée, certainement à cause de la notoriété (exagérée) des monades. Comme les monades, les applicatives functors permettent de séquencer des opérations.

En ce sens, elles sont moins puissantes que les monades mais suffisantes dans de nombreux cas. Nous verrons pourquoi par la suite.

Dans applicative functor, il y a functor ! Rappelons sa définition:

trait Functor[F[_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

Cette abstraction est très utile car elle permet d’appliquer une fonction indépendamment du contexte F. Voici une implémentation simple avec le type Option

val optionFunctor = new Functor[Option]{
  def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa match {
    case Some(a) => Some(f(a))
    case None    => None
  }
}

Pour le type Option c’est très pratique car on a plus besoin de vérifier s’il y a une valeur ou non. L’abstraction Functor s’en occupe pour nous. La librairie standard de Scala fourni une méthode map qui permet d’avoir le même résultat. La seule différence vient du fait que la librairie n’a aucune représentation de la notion de Functor. Nous pouvons donc simplifier son implémentation comme ceci:

val optionFunctor = new Functor[Option]{
  def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa map f
}

Passons maintenant à la définition d’Applicative functor:

trait Applicative[F[_]] {
  def pure[A](v: => A): F[A]

  def ap[A, B](ff: F[A => B], fa: F[A]): F[B]
}

La méthode pure permet à partir d’une valeur simple A d’obtenir une valeur dans un contexte F (F[A])

L’objectif de la méthode ap est d’extraire de ff une fonction (A => B) que l’on appliquera à la valeur de type A extraite de fa.

Voici l’implémentation du type Option

val optionApplicative = new Applicative[Option]{

  def pure[A](v: => A): Option[A] = Some(v)

  def ap[A, B](ff: Option[A => B], fa: Option[A]): Option[B] = (ff, fa) match {
    case (Some(f), Some(a)) => Some(f(a))
    case _                  => None
  }
}

L’utilité de cette abstraction n’est peut-être pas évidente au premier coup d’œil mais ça viendra par la suite.

Grâce à cette abstraction, nous pouvons définir quelques méthodes utiles comme celles-ci:

  object Applicative {
    def apply[F[_]](implicit F: Applicative[F]) = F
  }

  def liftA2[F[_]: Applicative, A, B, C](fa: F[A], fb: f[B])(f: (A, B) => C): F[C] = {
    import Applicative[F]._

    ap(ap(pure(f.curried), fa), fb)
  }

  def liftA3[F[_]: Applicative, A, B, C, D](fa: F[A], fb: f[B], fc: F[C])(f: (A, B, C) => D): F[D] = {
    import Applicative[F]._

     ap(ap(ap(pure(f.curried), fa), fb), fc)
  }

  // ... on peut continuer comme ça au moins jusqu'à vingt :)

}

La fonction liftA2 permet à partir de 2 valeurs F[A] et F[B], d’en extraire leurs contenus, de les passer en paramètre de la fonction f et de construire un nouveau contexte avec la valeur issue de l’application de f.

La fonction liftA3 est identique à liftA2 sauf qu’elle s’applique sur 3 valeurs F[A], F[B] et F[C]

Utilisons encore notre type Option avec un cas d’utilisation simple:

def addApplicativeOption(a: Option[Int], b: Option[Int], c: Option[Int]): Option[Int] =
  liftA3(a, b, c)(_ + _ + _)

Si nous avions implémenté cette méthode monadiquement, elle serait ainsi:

def addMonadOption(a: Option[Int], b: Option[Int], c: Option[Int]): Option[Int] =
  for {
    x <- a
    y <- b
    z <- c
  } yield x + y + z

Alors certains dirons "Oui mais… Nous pourrions également implémenter une fonction utilitaire pour avoir la même concision !". Ce qui est vrai mais malheureusement comme pour Functor, la librairie standard de Scala ne fourni pas de représentation pour la notion de monade. Donc on ne pourrait pas savoir si une valeur supporte une opération monadique. Le sucre syntaxique for n’est possible dans notre cas que si l’instance utilisée implémente les fonctions map et flatMap (ce qui ne rassemble pas toutes les conditions nécessaires pour être une monade !) Pour combler ce manque, nous utiliserons cette représentation:

trait Monad[F[_]]{
  def point[A](v: => A): F[A]

  def bind[A, B](fa: F[A])(f: A => F[B]): F[B]
}

l’implémentation pour le type Option est directe

val optionMonad = new Monad[Option]{
  def point[A](v: => A): Option[A] = Some(v)

  def bind[A, B](fa: Option[A])(f: A => Option[B]): Option[B] = fa flatMap f
}

Définissons maintenant les fonctions utilitaires équivalentes à celles de l’abstraction Applicative

 object Monad {
    def apply[F[_]](implicit F: Monad[F]) = F
  }

  def liftM2[F[_]: Monad , A, B, C](fa: F[A], fb: f[B])(f: (A, B) => C): F[C] = {
    import Monad[F]._

    bind(fa){
      a =>
        bind(fb){
          b =>
            point(f(a, b))
        }
    }
  }

  def liftM3[F[_]: Monad, A, B, C, D](fa: F[A], fb: f[B], fc: F[C])(f: (A, B, C) => D): F[D] = {
    import Monad[F]._

     bind(fa){
       a =>
         bind(fb){
           b =>
             bind(fc){
              c =>
               point(f(a, b, c))
             }
         }
     }
  }

  // ... on peut continuer comme ça au moins jusqu'à vingt :)

La version monadique est plus complexe car il y a plusieurs inclusions de fonctions contrairement à la version applicative.

Ce qui revient pour notre méthode d’exemple:

def addMonadOption(a: Option[Int], b: Option[Int], c: Option[Int]): Option[Int] =
  liftM3(a, b, c)(_ + _ + _)

liftA3 et liftM3 ne se limitent pas qu’aux options. Elles peuvent s’appliquer sur n’importe quel type qui implémente le type de classe Applicative (liftA2) ou Monad (liftM3). Nous pouvons écrire une version plus générique de nos méthodes addApplicativeOption et addMonadOption:

def addApplicative[F[_]: Applicative](a: F[Int], b: F[Int], c: F[Int]): F[Int] =
  liftA3(a, b, c)(_ + _ + _)

def addMonad[F[_]: Monad](a: F[Int], b: F[Int], c: F[Int]): F[Int] =
  liftM3(a, b, c)(_ + _ + _)

Nous avons 2 abstractions différentes mais le résultat est identique. Quel(s) point(s) les différencient ?

Principalement dans l’évaluation !

Comparons l’implémentation des méthodes ap et bind pour le type Option:

def ap[A, B](ff: Option[A => B], fa: Option[A]): Option[B] = (ff, fa) match {
  case (Some(f), Some(a)) => Some(f(a))
  case (None   , Some(_)) => None
  case (Some(_), None)    => None
  case (None,    None)    => None
}

def bind[A, B](fa: Option[A])(f: A => Option[B]): Option[B] = fa match {
  case Some(a) => f(a)
  case None    => None
}

Dans la méthode ap, on voit que même si ff est à None, on évalue le paramètre fa. Pour les Applicatives, un contexte précédant ne peut pas influencer l’évaluation du suivant !

C’est pourquoi les monades sont plus puissantes car un contexte précédant peut influencer le suivant. Par exemple la méthode bind appliquée aux options, si fa est à None, on évalue pas le reste.

Cette caractéristique des monades les rend moins applicables que les Applicatives. Donc si votre type ne forme pas une monade, il y a de fortes chances qu’il soit un applicative functor !

D’autres conclusions peuvent être faites. Si votre type forme une monade, alors il forme obligatoirement un applicative functor ! La méthode suivante permet de construire un applicative functor pour F si et seulement si F est une monade:

def monadApplicativeFunctor[F[_]](implicit F: Monad[F]) = new Applicative[F]{
  def pure[A](v: => A): F[A] = F.point(v)

  def ap[A, B](ff: F[A => B], fa: F[A]): F[B] =
    F.bind(ff){
      f =>
        F.bind(fa){
          a =>
            F.point(f(a))
        }
    }
}

Si votre type forme un applicative functor, alors il forme obligatoirement un functor. Exemple:

def ApplicativeToFunctor[F[_]](implicit F: Applicative[F]) = new Functor[F]{
  def map[A, B](fa: F[A])(f: A => B): F[B] = F.ap(F.pure(f), fa)
}

Par implication, si votre type forme une monade, alors il forme obligatoirement un functor. Exemple

def monadFunctor[F[_]](implicit F: Monad[F]) = new Functor[F]{
  def map[A, B](fa: F[A])(f: A => B): F[B] = F.bind(fa)(a => F.point(f(a)))
}

En résumé:

  1. Les applicative functors permettent la composition et le sequencement de valeurs contextualisées comme les monades
  2. Ils sont moins puissants mais peuvent s’appliquer dans plus de situations que les monades
  3. Ils sont très efficaces lorsque l’on veut composer des contextes qui n’ont aucunes dépendances entre eux

Nous verrons dans une prochaine publication une utilisation plus concrète des applicative functors. Nous verrons comme exemple la validation de données.