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 toutxetydansM;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.