xavier-van-de-woestyne-initial
Xavier Van de Woestyne
Functional Programmer

Le monoïde

01/02/2017

Observons une première structure algébrique appliquée à l'informatique : le monoïde !

Après avoir tâché de définir les structures algébriques dans un précédent article, j'ai décidé de présenter rapidement le Monoïde, une structure algébrique très simple pour s'initier à leur usage. Les exemples proposés dans cet article sont rédigés en OCaml car, en plus d’être un magnifique langage, son système de types et de modules se prête bien à l'implémentation de structures algébriques.

Pré-requis

Nous avions dit qu'il fallait trois ingrédients pour construire une structure algébrique :

  • un ensemble d'éléments ;
  • une loi de composition interne ;
  • des axiomes.

Pour représenter l'ensemble des éléments appartenant à une structure algébrique, nous allons simplement utiliser un type. La loi de composition interne sera une fonction, et comme, par essence, un axiome ne doit pas être démontré, dans un premier temps je laisserai cet ingrédient de côté. Pour représenter un monoïde, je vais utiliser une signature de module, un contrat que je devrai respecter pour implémenter un module concret.

module type MONOID =
sig
  type t
  val ( <+> ) : t -> t -> t
end

Concrètement, pour construire un monoïde, il faudra que je fournisse un module qui contient un type t et une fonction <+> qui pour deux éléments de type t, renverra un élément lui aussi de type t.

Actuellement, notre signature de module est absolument identique à celle du Magma que nous avions évoqué dans l'article d'introduction aux structures algébriques. C'est normal, un monoïde est un magma. Cependant, il nécessite quelques ajouts, étant donné que les axiomes liés au monoïde impliquent quelques éléments complémentaires.

Le monoïde est un Magma, qui a la particularité d'être associatif et unifère.

Associatif

Le terme associatif signifie que sa loi de composition interne est associative (logique) : (x <+> y) <+> z est équivalent à x <+> (y <+> z). Ou dans le monoïde des nombres naturels associé à l'opérateur + : (1 + 2) + 3 est équivalent à 1 + (2 + 3).

Unifère

Pour qu'une structure soit unifère, il faut qu'il existe dans son ensemble d'éléments un élément neutre. L'élément neutre d'un ensemble pour une loi de composition interne est un élément de cet ensemble qui laisse tous les autres éléments inchangés lorsqu'il est composé avec eux par cette loi à droite ou à gauche.

  • neutral <+> x = x ;
  • x <+> neutral = x.

Par exemple, en reprenant le monoïde des nombres naturels associé à l'opérateur +, l'élément neutre est le zéro :

  • 0 + 12 = 12 ;
  • 12 + 0 = 12.

C'est absolument tout ce qu'il est nécessaire d'avoir pour définir un monoïde. Il faut cependant légèrement modifier notre module pour obliger la définition d'un élément neutre.

module type MONOID =
sig
  type t
  val ( <+> ) : t -> t -> t
  val neutral : t
end

Quelques monoïdes courants

Maintenant que nous avons une interface minimale pour implémenter des monoïdes, voyons-en quelques-uns très simples. La syntaxe d'OCaml est assez simple, on définit un module et on dit qu'il respecte l'interface MONOID définie précédemment, ensuite, il faut implémenter les éléments requis par MONOID sinon le compilateur refuse de compiler le programme. Il est nécéssaire de spécifier le type t associé à MONOID, sinon il sera considéré comme un type abstrait.

Le premier est assez évident, il porte sur les entiers et l'opérateur d'addition.

module Int_sum : MONOID with type t = int =
struct
  type t = int
  let (<+>) = ( + )
  let neutral = 0
end

Un autre assez simple, les entiers et la multiplication.

module Int_prod : MONOID with type t = int  =
struct
  type t = int
  let ( <+> ) = ( * )
  let neutral = 1
end

Les chaînes de caractères forment elles aussi un monoïde si on le définit comme tel :

module String_monoid : MONOID with type t = string =
struct
  type t = string
  (* "foo" ^ "bar" == "foobar"*)
  let ( <+> ) = (^)
  let neutral = ""
end

Les listes (et donc aussi les tableaux) :

module List_monoid : MONOID with type t = list=
struct
  type t = int list
  let ( <+> ) = List.append
  let neutral = []
end

Dans le dernier exemple, on voit que j'ai dû fixer le type de la liste, ce qui rend le module peu flexible. Dans un prochain article, nous observerons une autre approche, celle de la monade, pour généraliser (entre autre) le comportement du monoïde à des types paramétrés par d'autres types.

On peut rapidement vérifier que ces types évoqués sont bien des monoïdes, en testant nos fonctions que nous avons choisies pour implémenter nos modules, par exemple :

List_monoid.(neutral <+> [1; 2]) == [1; 2]

Mais... à quoi ça sert ?

Les plus aguerris me diront que c'est très mignon mais que ça ne sert à rien car je n'ai, au final, que défini une série d'alias. Ils n'auront pas tort, cependant, au-delà de proposer un traitement uniforme à certains types, les axiomes liés aux monoïdes offrent de véritables intérêts !

Effectivement, vu comme des simples alias, savoir qu'une liste ou une chaîne de caractères est un monoïde... ça n'a pas beaucoup d'intérêt. Observons maintenant ce que chacune des lois peut nous apporter.

Les apports liés à la loi de composition interne

Imaginons une fonction reduce implémentée de la sorte :

let reduce (x :: xs) f =
  List.fold_left f x xs

Comme l'opérateur <+> renvoie toujours un résultat inscrit dans le type t, on peut travailler sur des séquences (des listes) d'éléments inscrits dans un monoïde gratuitement, par exemple : let somme_de li = reduce li (+) ou encore let produit_de li = reduce li (*). Un autre exemple serait : reduce [[1]; [2]; [3]] (@) (@ est l'opérateur de concaténation de listes en OCaml) qui donne le résultat [1;2;3].

Les apports liés à l'élément neutre

Dans l'exemple précédent, l'utilisation de reduce sur une liste vide provoque une erreur ; plutôt que de directement séparer la tête de la queue de la liste, nous pouvons utiliser, comme élément de départ pour l'utilisation de la fonction fold_left l'élément neutre. Pour généraliser ce comportement, nous allons créer un module OCaml paramétré par un autre module d'interface MONOID qui construira un nouveau module en lui ajoutant la fonction reduce :

module Monoid(M : MONOID) :
sig
  include MONOID with type t = M.t
  val reduce : t list -> t
end = struct
  include M
  let reduce = List.fold_left (<+>) neutral
end

module IntSum = Monoid(Int_sum)

Maintenant, notre fonction peut aussi fonctionner avec des listes vides : IntSum.reduce [] == 0.

Concrètement, l'élément neutre nous permet de dealer avec des listes vides !

Et l'associativité

L'associativité sur la loi de composition interne permet plusieurs choses assez cool :

  • diviser pour mieux régner ;
  • du parallélisme potentiel ;
  • du cacul incrémental.

Il est possible de facilement diviser un gros calcul monoïdal en plusieurs sous-calculs. Comme on a vu que <+> est associatif, chaque fragment composé par <+> peut être exécuté de manière indépendante. On peut donc très facilement paralléliser un calcul d'une séquence de <+> sur des valeurs monoïdales.

Opérer avec la loi de composition interne permet aussi de réaliser facilement du calcul incrémental. Imaginons par exemple que nous voudrions calculer la somme de 5 nombres : let x = IntSum.reduce [1; 2; 3; 4; 5], imaginons maintenant que nous voulions calculer la somme de 6 nombres, il n'est pas nécéssaire de refaire tout le calcul : x <+> 6.

Ce genre d'exemple semble assez naïf (pour ne pas dire inutile) avec des entiers. Cependant, vous imaginez de très grosses chaînes de caractères ou de très grosses listes ? Non seulement il est possible (et relativement simple) de paralléliser le calcul, mais en plus, il n'est pas nécéssaire de recalculer ce qui a déjà été fait.

Et concrètement, un monoïde, ça sert à quoi ?

Un monoïde décrit globalement l'idée qu'il y a derrière un motif d'agrégation. C'est une structure de données qui possède une sémantique d'accumulation. Je résumerai en disant qu'on a une liste de choses (monoïdales) et qu'on a une manière de les combiner pour obtenir, après ces combinaisons, un seul objet agrégé.

Monoïde homomorphisme

Maintenant que nous savons ce qu'est un monoïde, voyons ce qu'est un homomorphisme... c'est un mot barbare pour dire (dans les grandes lignes) "qui a la même forme" (il serait indéniablement possible de donner une définition plus rigoureuse et plus matheuse, mais l'objectif de cette section est de comprendre l'homomorphisme des monoïdes au travers un exemple très concret).

Concrètement, un homomorphisme entre deux monoïdes (M et N) est simplement une fonction (f) qui respecte ces contraintes :

  • f(x M.<+> y)=f(x) N.<+> f(y) pour tout x et y dans M ;
  • f(M.neutral) = N.neutral.

Par exemple, définissons rapidement un monoïde pour un document (il est légèrement différent du monoïde de la chaîne de caractères uniquement pour le plaisir) :

(* Notre type t *)
type document =
  | Text of string

(* Notre élément neutre *)
let neutral = Text ""

(* Notre loi de composition interne *)
let ( <+> ) (Text a) (Text b) =
  Text (a ^ b)

(* Notre fonction reduce *)
let reduce = List.fold_left (<+>) neutral

Implémentons rapidement une fonction pour compter les mots d'un document :

let count (Text t) =
  Str.(split (regexp " ") t)
  |> List.length

L'implémentation est assez moche... mais ce n'est pas la peine de faire quelque chose de très poussé pour les besoins de l'exercice.

En admettant que j'ai plusieurs pages, par exemple :

let pageA = Text "Hello World "
let pageB = Text "Foo bar "
let pageC = Text "O Caml "

J'ai deux manières de calculer le nombre total de pages :

  • count (pageA <+> pageB <+> pageC)
  • (count pageA) + (count pageB) + (count pageC)

La deuxième méthode considère que count est une fonction d'agrégation, qui agrège des documents en entier (associé à +, qui est donc aussi un monoïde). Est-ce que count est un homomorphisme entre le monoïde du document et celui des entiers (avec + comme loi de composition interne) ? Oui car :

  • count(pageA <+> pageB) = count(pageA) + count(pageB) ;
  • count(Text "") = 0 (soit l'élément neutre du monoïde des entiers avec +).

Observons maintenant la différence de performance entre ces deux implémentations avec un grand nombre de page :

let total = replicate [pageA; pageB; pageC] 10000

let a =
  reduce total
  |> count

let b =
  List.map count total
  |> List.fold_left (+) 0
ocaml str.cma exampleA.ml  2,36s user 0,19s system 99% cpu 2,563 total
ocaml str.cma exampleB.ml  0,16s user 0,01s system 98% cpu 0,176 total

Wow, alors oui, il est évidemment possible de dire que la concaténation de chaînes est une opération coûteuse, cependant, peu importe les modifications apportées au code, il sera difficilement possible de faire "plus rapide" qu'une simple addition. La notion de diviser pour mieux régner que nous avons observée dans les points forts liés aux monoïdes peut vraiment permettre de gros gains de performances.

Donc la chose à retenir de cet exemple est que plutôt que d'appliquer un homomorphisme sur une structure complexe à calculer, il vaut mieux l'appliquer plusieurs fois sur des petites structures simples à calculer. L'idée derrière diviser pour mieux régner est au centre de l'application de map/reduce.

Pour conclure

  • Un monoïde est une structure algébrique assez simple ;
  • ses règles offrent des stratégies d'implémentation ;
  • un traitement uniforme sur des typologies de structures ;
  • une possibilité de composition, de calcul parallèle et incrémental.

De nombreux outils (liés entre autre au traitement du Big Data) reposent sur les propriétés de parallélisation des monoïdes. Un des exemples les plus populaires sur le marché est l'algorithme MapReduce proposé par Google en 2006 (et qui est à la base de l'agrégation de Hadoop). Prochainement, nous nous intéresserons plus en détail à la notion de mapping de valeurs pour produire des monoïdes et comprendre rapidement comment pouvoir tout transformer en monoïde potentiel.

Aller plus loin avec les monoïdes

Monoids : Theme and Variations (Functional Pearl) par Brent A. Yorgey.