Functional Programming : monoïde , functor, monad

 Monoïdes :

Un monoïde est un ensemble E doté d'une fonction * et d'un élément neutre e tel que :

-          ∀(x,y)∈ (E, E) ,  x*y ∈ E (stabilité, magma) : respecte la lois de composition interne

-          ∀(x,y,z) ∈ (E, E, E), x*(y*z) = (x*y)*z (associativité)

-          Unifère (E a un élément neutre pour l’opération *) : c’est-à-dire il existe e qui appartient à E, et pour tout x qui appartient à E, x*e=e*x=x (existence d'un élément neutre)

Il existe plusieurs exemples de monoïdes :

-          L’ensemble de nombres entiers (N) muni de l’opération (+) avec 0 comme élément neutre (soit x, y, z des entiers) :  x + y est un entier ; x + 0 = 0 + x = x ; x + (y + z) = (x+y) + z

-          L’ensemble de nombre réel muni de l’opération de multiplication (*) et 1 comme élément neutre (soit x, y, z des réels) :  x*y reste un réel ; x*1 = 1*x = x ; x* (y*z) = (x*y) * z

Il existe aussi des contres exemples :

-          L’ensemble de nombre entiers négatifs (N-) muni de l’opération de multiplication (*) n’est pas monoïdes car N- n’est pas un magma. En effet si nous prenons deux éléments appartenant à (N-) par exemple -2 et -1, la multiplication -2*-1 = 2 n’appartient pas à (N-)

-          L’ensemble de nombre paire (2N) muni de l’opération de multiplication n’est également pas un monoïde car l’élément neutre pour la multiplication est 1, or 1 n’appartient pas à (2N) autrement dit (2N) n’est pas unifère ((2N, *) n’a pas d’élément neutre)

Pour un informaticien, un type T est un monoïde s’il existe une opération (T, T) => T et un élément neutre pour cette opération. Par exemple les entiers naturels avec l’addition et 0, les chaines de caractères avec la concaténation et "".  Un monoïde est donc simplement une structure de donnée ayant :

•          Un ensemble d’objet de type T: exemple les nombres, les listes, …
•           Une fonction binaire F qui prend en paramètre deux objets (t1, t2)  de type T et retourne un résultat également de type T : F (t1, t2) est de type T : def F(a: T, b: T): T et  (a F b) F c == a F (b F c)
•           Un élément neutre e de type T : si t est de type T, F(t, e) = F (e, t) = t 

Exemple : Les Integer avec la fonction + et e = 0, ou avec la fonction * (multiplication) et e (élément neutre) = 1, ou Les list<T> avec la fonction concat et e = Nil (List(), liste vide), ou les ensembles (Set), avec la fonction Union et e = Set() (ensemble vide).

Functor

Un terme incompréhensible…pour simplifier la définition, disons que c’est une structure de donnée typée T (Integer, List<T>, Set<T>…) munie :

-          d’un constructeur : of = e :T => F[T]. Le constructeur nous donne ce qu’on appelle : élément boxé, encapsulé, contextualisé …

-          d’une fonction appelée bind avec comme signature (Figure 1)

-          d’un élément boxé (encapsulé) neutre (E) pour toute fonction f. Autrement dit, l’application de la fonction f par la fonction bind n’aura aucun effet sur l’élément neutre boxé E.

Figure 1 : Signature de la méthode bind

Des exemples pour clarifier mes propos :

Listes muni de la fonction bind = map (de java  8 ou scala) avec of = constructeur de List et la liste vide (E = List()) comme élément boxé neutre. La fonction map est très fréquente lorsque le programme consiste à parcourir une liste et appliquer une fonction à chacun de ses éléments.

La fonction map prend une fonction en paramètre et l’applique aux éléments de la liste et retourne la liste résultante :

Soit f = (x : Integer => 2*x),

-          List(1,2,3).map (f) = Lis(2*1, 2*2, 2*3) = List(2,4,6)

-          List().map (f) = Lis()

Option ou Maybe : élément boxé neutre = None, bind (None, f) = None et bind (Option(x), f) = Option(f)

Monades :

Une monade est avant tout une structure de donnée (comme List, Set, Integer, etc.) permettant d’encapsuler une valeur. Elle peut être vue comme une boite, vide ou ayant un contenu, qui nous fournit des abstractions et des opérations au-dessus de la valeur éventuellement encapsulée. 

Il existe différents types de boites correspondant à différents types de structures. Prenons un exemple pour le type Option de scala ou Maybe de Haskell. Une option de scala permet d’exprimer le fait que l’objet qu’on manipule contient peut être une valeur, mais peut-être pas. Dans ce cas, la boîte nous permet de manipuler cet objet potentiel sans s’inquiéter de la présence ou non d’une valeur. Une monade M est munie :

-          Constructeur de Monade : Une fonction notée of permettant d’encapsuler et de construire une valeur d’un type T donné. Cette encapsulation du type T est également appelée Boxée T et notée M[T]. Un exemple vaut mieux qu’un long discours : si T = Integer, of(Integer) peut être List<Integer>. Il suffit de définir une fonction pour ces objets Monades (List<Integer>) qui détermine comment appliquer une fonction à ces objets monades.

-          Une fonction notée apply qui définit comment on applique les fonctions (du type f : A => M[B]) aux objets Boxés M[A]. La fonction f retourne un élément Boxé. La signature de la fonction apply  (X : M[A], f : A => M[B]) => MA[B], elle applique la fonction f à un élément Boxé de type A et retourne un élément Boxé. Le paramètre du type A n’est pas nécessairement Boxé par contre son paramètre de retour est Boxé.

-          d’un élément boxé neutre (E) pour toute fonction f. Autrement dit, l’application de la fonction f par la fonction apply n’aura aucun effet sur l’élément neutre boxé E.

Un exemple vaut toujours mieux qu’une définition théorique :

Liste munie de la fonction apply = flatMap de scala et élément neutre E = liste vide = List() :

 La fonction flatMap s’applique à une liste. Elle applique une fonction g aux éléments de la liste. Cette fonction g a pour paramètre de retour une liste. Du coup, lorsqu'elle est appliquée à un élément de la liste, elle retourne une liste. La fonction flatMap permet de concaténer ces listes (les listes retournées par la fonction g) pour en donner une seule et unique liste. Exemple en Scala : 

Un autre exemple pour finir :

Soit une fonction :

f : (i: Int) => List (i.toDouble / 4, i.toDouble / 2).

La fonction f retourne bien une liste (élément boxé). Par contre elle prend un entier (Int) en paramètre non boxé ! Trouvons la fonction apply permettant d’appliquer la fonction f à une List[Int] : il suffit d’appliquer la fonction f aux éléments de la liste. Par exemple pour une liste : List[Int] (1, 2) = List[Double](1.0/4, 1.0/2, 2.0/4, 2.0/2) = List[Double](0.25, 0.5, 0.5, 1.0)....