Introduction

Lors des précédents articles sur la découverte de la programmation fonctionnelle, nous avons parcouru toutes les bases nous permettant de mieux appréhender des notions mathématiques qui ont le vent en poupe mais qui ne cessent de nous intriguer.

Dans la suite, nous allons nous concentrer sur la définition formelle de certains outils mathématiques que nous avons déjà manipulés.

Dans un premier temps, nous définirons les semigroupes. Puis, nous explorerons la relation que ceux-ci ont avec les monoïdes. Enfin, nous décortiquerons les foncteurs.

Cet article aura pour vocation de poser des définitions. Ces définitions, nous permettront par la suite d’introduire des structures plus complexes qui font toute la puissance de la programmation fonctionnelle.

Semigroupes

Définition: Un Semigroupe est un ensemble A muni de la fonction combine(A, A): A associative.

La retranscription de cette définition en Scala pourrait se traduire par un trait définissant cette dite méthode combine en Scala.

trait Semigroup[A] {
  def combine(a: A, b: A): A
}

En analysant la définition d’un Semigroupe, nous pouvons identifier plusieurs Semigroupes :

L’ensemble des entiers positifs muni de l’addition

1 + 2 = 3 // opération de (Int, Int) vers Int

L’ensemble des entiers muni de la multiplication

(-3) * 2 = -6 // opération de (Int, Int) vers Int

Un autre exemple particulièrement intéressant serait les listes non vides munies de la concaténation. Elaborons sur ce dernier exemple en décrivant ces listes :

case class NonEmptyList[+A](head: A, tail: List[A])

Afin de définir le Semigroupe associé aux listes non vides. Nous devons redéfinir les Semigroupes afin de les adapter à notre exemple.

trait Semigroup[S[_]] {
  def combine[A](a: S[A], b: S[A]): S[A]
}

L’écriture S[_] permet de définir des types constructeurs. Il est ainsi possible d’identifier List comme étant un type constructeur et List[Int] comme étant un type.

Les types constructeurs se différencient des types simples (Int, Long, etc. ) par les “trous” qui leurs sont associés. List est un type constructeur avec un trou, là où, Either est un type constructeur à deux trous.

Les types constructeurs sont nommés Higher Kinded Types en anglais.

Une analogie similaire peut etre faite avec les fonctions. Une fonction f serait une value constructor tandis que l’appel de cette fonction f avec un parametre x renvoie une value f(x)

Cet apparté terminé, et, dans la lignée de ce que nous avons vu avec les typeclasses dans l’article 5 sur découverte la programmation fonctionnelle. Il nous faut à présent définir le comportement du Semigroup NonEmptyList en lui associant une méthode combine.

Prenons l’exemple des NonEmptyList[Int]

implicit val nonEmptyListSyntax: Semigroup[NonEmptyList] = new Semigroup[NonEmptyList] {
     override def combine[Int](a: NonEmptyList[Int], b: NonEmptyList[Int]): NonEmptyList[Int] = {
      NonEmptyList(a.head, b.head :: a.tail ++ b.tail)
    }
  }

Notre méthode combine définie pour des NonEmptyList[Int], nous pouvons l’appeler en important dans notre scopenonEmptyListSyntax.combine

import nonEmptyListSyntax._

val f = NonEmptyList(1, Nil)
val d = NonEmptyList(3,List(2,7,5))
combine(f, d)

> NonEmptyList(1,List(3, 2, 7, 5))

 

Monoïdes

En mathématiques, un monoïde est une des structures algébriques utilisées en algèbre générale. C’est un ensemble muni d’une loi de composition interne associative et d’un élément neutre. Autrement dit, c’est un magma associatif et unifère, c’est-à-dire un demi-groupe unifère.

– Wikipédia

En décortiquant la définition ci-haut, nous pouvons extraire différents éléments nous permettant de définir un monoïde.
Par définition, un magma est un ensemble muni d’une loi de composition interne. Unifère défini un ensemble possédant un élément neutre.

Un monoïde est donc un ensemble d’éléments de type A muni :

• d’une loi de composition interne associative combine (A, A) => A
• d’un élément vide/neutre.

Un monoïde est facilement transcriptible en un trait en Scala :

trait Monoid[A] {
  def combine(a: A, b: A): A
  def empty: A
}

Cette définition, couplée à celle d’un semigroupe, nous permet de redéfinir les monoides sur la base d’un semigroupe :

type Monoid[A] extends Semigroup[A]{
  def empty: A
}

Les monoides, sont des ensembles que nous utilisons tous les jours (même inconsciemment). En effet, l’ensemble des entiers muni de l’addition constitue un monoïde.

1 + 2 = 3 // opération de (Int, Int) vers Int
1 + 2 = 2 + 1 = 3 // associativité
1 + 0 = 1 // 0 est un élément neutre

Un autre exemple de monoïdes, l’ensemble des entiers muni de la multiplication :

3 * 2 = 6 // opération de (Int, Int) vers Int
3 * 2 = 2 * 3 = 6 // associativité
2 * 1 = 2 // 1 est un élément neutre pour la multiplication

Nous avons vu un autre exemple dans le précédent article sur la programmation fonctionnelle au sujet des Typeclasses. En effet, nous avions définit une opération |+| nous permettant d’additionner le contenu de deux ou plusieurs Option[Int].

Reprenons la définition:

object CanBeAdded {
  implicit val optionIntCanBeAdded: CanBeAdded[Int] = new CanBeAdded[Int] {
    override def combine(v: Option[Int], sh: Option[Int]): Option[Int] = (v, sh) match {
      case (None, None) => Some(0)
      case (Some(x), None) => Some(x) //element neutre
      case (None, Some(y)) => Some(y) //element neutre
      case (Some(x), Some(y)) => Some(x + y) //associativité
    }
  }
}

Nous retrouvons les notions d’associativité, la fonction combine(Option[Int], Option[Int]): Option[Int] ainsi que l’élément neutre None.

Outre cet exemple, les monoïdes sont des structures utiles de bien des façons. Dans le domaine du Big Data, la partie Reduce d’un algorithme de Map Reduce pourrait être implémenter à l’aide de Monoïde. Un ensemble E , muni de sa loi de composition interne combine(E, E): E permettrait d’aggréger les résultats de l’opération map et de fournir un résultat dans E. Quant à l’élément neutre, il servirait pour indiquer l’absence de résultat.

Vous trouverez d’excellents exemples dans l’article de Francois Sarradin consacré aux Monoïdes.

La définition d’un Monoïde induit que nous pouvons toujours extraire un Semigroupe à partir d’un Monoïde. Seulement, la réciproque est fausse. En effet, nous ne pouvons pas avoir de Monoïde avec l’ensemble des entiers strictement positifs muni de l’addition or cet ensemble est par définition un semigroupe. De même, l’ensemble des listes non vides que nous avons vu dans le cadre des Semigroupes ne peut avoir d’élément neutre et par conséquent ne peut être un monoïde.

Foncteurs

Définition: Un foncteur est un type F muni d’une opération map: (A => B) => F[B]

Un foncteur (ou foncteur covariant) est donc une abstraction qui caractérise des “structures” qui implémentent une méthode map. Cette définition, nous permet d’identifier des foncteurs dans des structures habituelles tels que les Option ainsi que les List.

Comme nous l’avons fait pour les cas des Semigroupes et des Monoïdes, nous allons définir les foncteurs sous forme d’un trait.

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

Pour des soucis d’implémentation, nous allons modifier légèrement la signature de la fonction map afin qu’elle prenne en paramètre le foncteur sur lequel nous appliquerons la fonction.

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

Dans l’article Découvrir la programmation fonctionnelle #3 | Boucles, nous avions défini une class Maybe reprennant le comportement d’une Option pour laquelle nous avions défini une fonction map. Par définition, Maybe est un foncteur.

Formalisons à nouveau Maybe afin d’implémenter cette fois le foncteur de maniere plus formelle.

sealed trait Maybe[+A]

case class Yep[+A](v: A) extends Maybe[A]
case object Nope extends Maybe[Nothing]

Maintenant, il ne nous reste plus qu’a implémenter une instance de foncteur pour Maybe

object Functor {
  implicit val maybeFunctor: Functor[Maybe] = new Functor[Maybe] {
    override def map[A, B](fa: Maybe[A])(f: A => B): Maybe[B] = fa match {
      case Yep(a) => Yep(f(a))
      case Nope => Nope
    }
  }
}

Cette implémentation nous permettra par la suite de l’utiliser comme ceci:

val maybe = Yep(someValue) 
maybeFunctor.map(maybe)(f)

Une fonction à un paramètre est aussi un foncteur. Il peut aussi être chainer en utilisant une fonction map :

Foncteur Contravariant

Définition: Un foncteur contravariant est un type F muni d’une opération contramap : (B => A): F[A] => F[B].

Cette définition peut-être re-transcrite en considérant qu’un foncteur contravariant d’un ensemble A vers un ensemble B est un foncteur covariant d’un ensemble A vers l’ensemble opposé à B.

object ContravariantFunctor {
  implicit val maybeContravariantFunctor: Functor[Maybe] = new Functor[Maybe] {
    override def contramap[A, B](fa: Maybe[A])(f: B => A): Maybe[B] = fa match {
      case Yep(a) => ??? // impossible !!!
      case Nope => Nope
    }
  }
}

Au même titre que le principe d’un foncteur covariant représente un ajout en queue dans une chaine. Un foncteur contravariant quant à lui représente l’ajout en tête.

Les foncteurs contravariants ne marchent que pour les types qui représentent des transformations. Dans notre cas, il est impossible de définir une fonction contramap sur Maybe.

Parcontre, si nous prenons l’exemple d’une DisplayableMaybe que l’on peut afficher sur un terminal ou tout autre support externe.

trait DisplayableMaybe [A] {
  def print(a: A): String
  
  def contramap[B](f: B => A): DisplayableMaybe[B] = new DisplayableMaybe[B] {
    def print(b: B): String = print(f(b))
  }
}  

Nous ne les détaillerons pas dans cet article, mais sachez qu’il existe également des foncteurs dit invariants. Leurs caractéristiques est de rajouter des transformations en tête et en queue en même temps. Ces foncteurs implémentent une fonction dit imap qui est l’équivalent d’un map et d’un contramap.

Conclusion

Dans cet article, nous avons vu les Semigroupes, puis nous nous sommes penchés sur les Monoides , nous avons également vu des implémentations concrètes avant de passer en revu les foncteurs.

Avec cette base, nous pourrons nous pencher plus spécifiquement sur les monades au prochain article.

En attendant la suite, n’hésitez pas à poser vos questions en commentaire.