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)....

Scala : Fonction Partielle (PartialFunction)

Fonction partielle

Une fonction partielle est une fonction avec un domaine de définition restreint. Elle n'est pas entièrement définie sur l'ensemble des valeurs du type correspondant à l'ensemble de définition. Par exemple, une fonction qui prend un Integer en paramètre et qui n’est pas définie pour toutes les valeurs possibles Integer : la fonction racine carrée n’est pas définie pour les nombre négatifs, la fonction division (x, y) qui à x associe x/y n'est pas définie pour y=0.

En scala une fonction partielle est du type trait PartialFunction[-A, +B] qui étend la fonction unaire ((A) => B) :

trait PartialFunction[-A, +B] extends (A) ⇒ B

Une fonction partielle Scala doit obligatoirement définir 2 méthodes : apply et isDefinedAt. Voici quelques exemples de fonction partielle en Scala :

  - List [+A]:

def isDefinedAt(x: Int): Boolean
//Tests whether this sequence contains given index.

def apply(n: Int): A
//Selects an element by its index in the sequence.

   - Map [A, +B] :

def isDefinedAt(key: A): Boolean
//Tests whether this map contains a binding for a key. 

def apply(key: A): B
//Retrieves the value which is associated with the given key.

Exemple pratique

Nous disposons d’une liste de nombres réels. L’objectif ici est de calculer la racine carrée de chaque nombre positif de la liste. Il faudra en effet omettre les nombres négatifs. 

Solution avec Java (<8) :

public class Main {

    public static void main(String[] args) {
        List<Double> result = square(Arrays.asList(-4.0, 1.0, 16.0, 36.0, -81.0, 49.0));
        System.out.println("Reslutat : "+result);
    }

    static List<Double> square(List<Double>  inputs){
        List<Double> result = new ArrayList<Double>();
        for (Double value : inputs){
          if(value >=0){
              result.add(Math.sqrt(value));
          }
        }
        return result;
    }
}

Cette solution procédurale effectue un parcours afin d'omettre les nombre négatifs de la liste. Voyons comment implémenter une solution fonctionnelle avec Scala en utilisant la fonction collect.

Scala dispose d’une fonction collect qui s’applique à une liste. Elle prend en paramètre une fonction partielle (fp) et l’applique à chaque élément de la liste. Pour chaque élément e de la liste, la fonction collect appelle fp isDefinedAt(e). Si cette application retourne true, fp apply(e) est appelée sinon l'élément est omis. L’exemple ci-dessus applique la fonction partielle ages du type Map sur une liste de noms names :

Une fonction partielle peut être utilisée conjointement avec la fonction collect afin d’implémenter élégamment le problème de calcul de la racine carrée d’une liste de nombre réels :

  def main(args: Array[String]) = {
    val result = List(-4.0, 1.0, 16.0, 36.0, -81.0, 49.0) collect square
    println("result, " + result)
  }


  val square = new PartialFunction[Double,Double]{
    def apply(v1: Double): Double = Math.sqrt(v1)
    def isDefinedAt(x: Double): Boolean = x match {
      case x => x > 0
      case _ => false
    }
  }

Une solution équivalente simplifiée en utilisant case :

  def main(args: Array[String]) = {
    val result = List(-4.0, 1.0, 16.0, 36.0, -81.0, 49.0) collect square
    println("result, " + result)
  }

  def square : PartialFunction[Double, Double] = {
    case value if(value >= 0) => Math.sqrt(value)
  }

Combinaison de fonctions partielles

Commençons par un petit exercice. Nous disposons d’une liste d’entiers et nous voulons multiplier les nombres impairs par 3 et les nombres pairs par 2. Nous allons donc définir deux fonctions partielles. Une fonction partielle pour les nombres impairs et une autre pour les nombres pairs. Il suffit de combiner les deux fonctions partielles avec la fonction orElse.  Cette fonction s’applique de la manière suivante : 

fp1(e) orElse fp2(e). 

Si la fonction partielle fp1 n’est pas applicable au paramètre e (isDefinedAt(e)=false), fp2 est appliquée au paramètre e. notre implémentation va consister à appliquer la fonction collect avec comme paramètre la combinaison de deux fonctions partielles :

  def main(args: Array[String]) = {
    println("result : " + (List(3, 7, 4, 5, 8, 10, 6, 13).collect(multiplyOddNumber orElse multiplyPeerNumber)) )
  }

  def multiplyOddNumber: PartialFunction[Int, Int] = {
     case x if x % 2 == 1 => 3*x
    }

  def multiplyPeerNumber: PartialFunction[Int, Int] = {
    case x if x % 2 == 0 => 2*x
  }

result : List(9, 21, 8, 15, 16, 20, 12, 39)

La combinaison de nos deux fonctions partielles (multiplyOddNumber orElse multiplyPeerNumber ) nous donne une fonction totale c'est-à-dire une nouvelle fonction définie sur l'ensemble des valeurs du type correspondant à l'ensemble de définition. Nous pouvons donc utiliser la fonction map à la place de collect  :

  def main(args: Array[String]) = {
    println("input, " + (List(3, 7, 4, 5, 8, 10, 6, 13).map(multiplyOddNumber orElse multiplyPeerNumber)) )

  }

Scala : Récursivité terminale @tailrec

Parlons de la pile d'exécution : l'origine de StackOverFlowError

Lors de l’exécution d’une classe Java, la JVM commence l'exécution en chargeant (loading) la classe contenant la méthode main. Ce travail de chargement est assuré par la ClassLoader qui opère à la demande ou de façon anticipée en pré chargeant certaines classes. Un thread est créé pour exécuter la méthode main. Au démarrage d’un thread, la JVM lui associe une pile de mémoire. 

La pile est une zone de mémoire qui stocke les paramètres, les résultats intermédiaires, les retours de méthode/fonction. Pour chaque méthode/fonction exécutée, il existe un contexte d’exécution (stack frame) allouée sur la pile. Un frame est utilisé pour stocker des données locales, des résultats partiels, des valeurs de retour pour les méthodes, et les pointeurs vers 'autres objets liés à la méthode. Un frame n'existe que le temps d'existence d'une méthode et est empilée sur la pile.

Lors de l’appel d’une fonction f(), elle est empilée sur la pile avec ses paramètres et ses variables locales dans le stack frame. A la fin de son exécution, elle est dépilée ainsi que ses variables locales. Ci-dessus, un exemple pour clarifier mes propos :

Vous pouvez remarquer avec cet exemple simplifié qu'un grand nombre d’appels de fonctions imbriqués peut grossir la pile et engendrer un risque important de débordement (d’où l’exception StackOverFlowError, l’option Xss vous permet d’augmenter la taille de la pile). Cela arrive généralement pour les fonctions récursives. En effet, une fonction récursive effectue un (plusieurs) appel(s) à elle-même.

Les fonctions récursives sont très souvent élégantes mais peuvent parfois nécessiter un trop grand nombre d’appels récursifs, entraînant ainsi un débordement de la pile. Chaque appel de la fonction récursive, un stack frame est empilé sur la pile d’exécution. La pile d’exécution peut rapidement s’agrandir : on se retrouve avec autant de frames que d’appels récursifs. 

Pour remédier à cette problématique, le compilateur Scala transforme les fonctions récursives en remplaçant les appels récursifs par des boucles. Cette transformation n’est possible que pour les fonctions récursives terminales. 

Une fonction récursive f est terminale si la dernière instruction est un appel récursif à la fonction (l’appel récursif est du type : retrun f(…)). Un exemple vaut mieux qu’un long discours ! 

def factorielle(n: Int): Int = {
  if (n < 2) 1
  else n * factorielle(n - 1)
}

La fonction récursive factorielle n’est pas terminale. En effet l’appel récursif n’est pas la dernière instruction de la fonction, puisqu’il faut d’abord effectuer le calcul de factorielle(n - 1) puis multiplier le résultat par n.

Pour transformer la fonction factorielle à une fonction récursive terminale, il suffit d’ajouter un paramètre supplémentaire nous permettant de cumuler le résultat (le calcul de factorielle n se fait par factorielle(n, 1) ) :

def factorielle(n: Int, resultat: Int): Int = {
  if (n < 2) resultat
  else factorielle(n - 1, resultat * n)
}

Pour éviter le problème de débordement de la pile, le compilateur transforme cette fonction récursive à une fonction équivalente utilisant une boucle :

def fact_iter(n: Int, resultat: Int) = {
    var valeur = n
    var res = resultat
    while (valeur >= 2) {
      res = res * valeur
      valeur = valeur - 1
    }
    res
  }

L'annotation @tailrec Scala est là pour vous aider !

Le compilateur Scala vous permet d’utiliser l’annotation @annotation.tailrec   pour indiquer une fonction récursive terminale. Si la fonction n’est pas récursive terminale le compilateur Scala produit une erreur.

Nous remarquons que la fonction récursive fibonacci n’est pas terminale. En effet l’appel récursif n’est pas la dernière instruction de la fonction, puisqu’il faut d’abord effectuer le calcul de fibonacci (n - 1) puis additionner avec fibonacci(n-2). En plus des appels récursifs, il y a une opération addition à effectuer.

La version récursive terminale :

def fibonacciTailVersion (count: Int): Int = {
    @tailrec
    def fibonacciHelper (count: Int, value: Int = 1, accum: Int = 0): Int = count match {
      case 0 => accum
      case _ => fibonacciHelper(count - 1, accum, value + accum)
    }
    fibonacciHelper(count)
  }