La puissance de mon Monoïde est supérieure à 9000

Qu'est ce qu'un monoide ?

Un monoïde est un magma unifère associatif

Non, en vrai, c'est quoi un monoïde ?

Laissez moi vous raconter une histoire...

Il était une fois,

Pour cette démonstration, utilisons TypeScript  :

• Syntaxe proche de JavaScript
• Sucre syntaxique et classes
• Typage statique
• Langage cool

• Lisible par les non initiés

Modélisons Boo

class Guy {		
    constructor(public power:number) {}

    //Égalité structurelle
    equals(g:Guy): boolean {    	
    	return g.power == this.power
    }
}

var boo = new Guy(8500)
console.log(boo.power) //affiche 8500
					

Mais la Terre est fournie avec un protecteur infatiguable !

Modélisons goku et le combat

var boo = new Guy(8500);
var goku = new Guy(4000)

var fight = function (guy1:Guy, guy2:Guy):Guy {	
	return guy1.power > guy2.power ? guy1 : guy2
}

var winner = fight(goku, boo)
console.log(winner) // affiche boo, car il est de loin de le plus fort
					

Goku a perdu !

Appel à un ami

Modélisons la fusion

var boo = new Guy(8500);
var goku = new Guy(4000)
var vegeta = new Guy(3900);

var fusion = function(guy1:Guy, guy2:Guy):Guy {
 		return new Guy(guy1.power + guy2.power);
}

var bejito = fusion(goku, vegeta); 
console.log(bejito.power) // affiche 7900

var winner = fight(bejito, boo)
console.log(winner) // affiche toujours boo, car il est toujours le plus fort
					

Bejito est vaincu !

Augmentons le nombre de ressource

Fusion partout !

var goten = new Guy(2000)
var trunks = new Guy(2500)

var gotenks = fusion(goten, trunks)
console.log(gotenks.power) // affiche 4500

var gobejitenks = fusion(gotenks, bejito) 
console.log(gobejitenks) // affiche 12400

fight(gobejitenks, boo) // gobejitenks gagne

Gobejitenks gagne

Que nous montre cet exemple ?

Loi de composition interne

var fusion = function(guy1:Guy, guy2:Guy):Guy {
 		return new Guy(guy1.power + guy2.power);
}

• fusion est une fonction...
• ...qui prend 2 paramètres du même type Guy
• ...qui renvoit une valeur du même type Guy

Associativité

var fusion = function(guy1:Guy, guy2:Guy):Guy {
 		return new Guy(guy1.power + guy2.power);
}			

var fusionned1 = fusion(fusion(goku, vegeta), goten)
var fusionned2 =  fusion(goku, fusion(vegeta, goten))
console.log(fusionned1.equals(fusionned2)) //affiche true

Les lois de composition interne associative permettent généralement de rendre plus lisible les fold/inject/reduce

var gobejitenks = [goku, vegeta, goten, trunks].reduce(fusion)

Élement neutre

élèment neutre de fusion :

var goku = new Guy(4000)
var mrSatan = new Guy(0)

var gotan = fusion(goku, mrSatan)
var saku = gusion(mrSatan, goku)

console.log(gotan.equals(saku)) //affiche true
console.log(gotan.equals(goku)) //affiche true
console.log(saku.equals(goku)) //affiche true
					

On a un monoïde !

Un monoide est un ensemble muni d'une loi de composition interne associative et d'un élément neutre

• Ensemble des Guy
• fusion
• new Guy(0)

ET ?

À quoi ca sert ?

La fusion, ça prend du temps

Q, librairie de promesse

• Execution séquentielle de code asynchrone
• composabilité
• Les promesses, c'est cool

fusion différée

//La fusion executera la callback de promesse qu'après 0.5 seconde
var fusion = function(guy1:Guy,guy2:Guy):Q.IPromise<Guy> {
    var deferred = Q.defer();
	
    setTimeout(() => {
       deferred.resolve(new Guy(guy1.power + guy2.power))
    }, 500);
	
    return deferred.promise;
};

Exemple

var boo = new Guy(8500);
var goku = new Guy(4000);
var vegeta = new Guy(3500);

var promiseForBejito:Q.IPromise<Guy> = fusion(goku, vegeta);

promiseForBejito.done((bejito:Guy) => {
	// affiche boo, une fois que la fusion est fini
	console.log(fight(bejito, boo)) 
})
					

fusion n'est plus une loi de composition interne

Le type de retour Q.IPromise<Guy> n'est pas le même que celui d'entrée, Guy

La lisibilité du reduce en prend un coup

var heroes = [goku, vegeta, goten, trunks];
var promiseForGobejitenks:Q.IPromise<Guy> = heroes.reduce(
    (acc:Q.IPromise<Guy>, guy:Guy) => {
       return acc.then((fusionned) => fusion(fusionned, guy))
    }, Q(new Guy(0))
)

promiseForGobejitenks.done((gobejitenks) => {
    // gobejitenks gagne, après que les fusions aient eu lieues
    // Soit 1.5 secondes
    console.log(fight(gobejitenks, boo)) 
})
					

Retour de la loi de composition interne

var fusionPromise = function(guy1:Q.IPromise<Guy>,
                             guy2:Q.IPromise<Guy>):Q.IPromise<Guy> {

    //execute le then quand les 2 promesses sont résolues
    return Q.all([guy1, guy2]).then((guys) =>  fusion(guys[0], guys[1]))
}

var noHero:Q.IPromise<Guy> = Q(new Guy(0));
var heroes = [goku, vegeta, goten, trunks];
var promiseForHeroes:Array<Q.IPromise<Guy>> = heroes.map(Q)

var promiseForGobejitenks = promiseForHeroes.reduce(fusionPromise, noHero)

promiseForGobejitenks.done((gobejitenks) => {
    // gobejitenks gagne, après 1.5 secondes    
    console.log(fight(gobejitenks, boo)) 
})
					

Mais nos heros sont 4

Algorithme de parcours en "arbre"

• Si la liste ne contient pas d'élément, on renvoit l'élément neutre
• Si la liste contient 1 élément, on renvoit celui-ci
• Si la liste contient 2 éléments, on renvoit leur fusion
• Si la liste contient plus que 2 éléments, on divise la liste en 2 parts, et on execute l'algorithme ici défini sur chacune des parties, avant de fusionner leurs résultats

ATTENTION ! Fonction récursive à l'horizon !

var reduceFusion = function(coll:Array<Q.IPromise<Guy>>):Q.IPromise<Guy> {
    var elementsCount = coll.length;
    if(elementsCount == 2) {
        return fusionPromise(coll[0], coll[1]);
    } else if(elementsCount == 1) {
        return fusionPromise[0];
    } else if (elementsCount == 0) {
        return Q(new Guy(0))
    } else {
        var halfSize = elementsCount / 2
        var half1Combined = reduceFusion(coll.slice(0, halfSize));
        var half2Combined = reduceFusion(coll.slice(halfSize, elementsCount));
        return fusionPromise(half1Combined, half2Combined);
    }
};
					

Usage

var promiseForHeroes = [goku, vegeta, goten, trunks].map(Q)
reduceFusion(promiseForHeroes).done((gobejitenks) => {
	//gobejitenks gagne, après seulement 1s, et plus 1.5 s
	console.log(fight(gobejitenks, boo)) 
})
					

Que s'est il passé ?

Que fallait-il pour pouvoir paralléliser ?

• Une loi de composition interne...
• ... associative...
• ... avec un élément neutre

On retrouve notre monoïde

Abstraction du type Monoïde

interface Monoid<T> {
    ZERO:T; //element neutre
    combine:(a:T, b:T) => T //loi de composition interne
}

reduce, parallélisation et monoïde

var reduceMonoid = function<T>(m:Monoid<T>, coll:Array<T>):T {
    var elementsCount = coll.length;
    if(elementsCount == 2) {
        return m.combine(coll[0], coll[1]);
    } else if(elementsCount == 1) {
        return coll[0];
    } else if (elementsCount == 0) {
        return m.ZERO
    } else {
        var halfSize = elementsCount / 2
        var firstHalf = reduceMonoid(m, coll.slice(0, halfSize));
        var secondHalf = reduceMonoid(m, coll.slice(halfSize, elementsCount));
        return m.combine(firstHalf, secondHalf);
    }
};
					

fusion et reduceMonoid

var monoidOfPromiseOfGuy:Monoid<Q.IPromise<Guy>> = {
		ZERO: Q(new Guy(0)),
		combine: fusionPromise
};

var promiseForHeroes = [goku,vegeta, goten, trunsk].map(Q)
var promiseForGobejitenks = 
        reduceMonoid(monoidOfPromiseOfGuy, promiseForHeroes);

					

Mais,

quand on commence à penser monoïde,

on en voit partout

var monoidOfBetterGuy: Monoid<Guy> = {
    ZERO:new Guy(0),
    combine:fight
}
var heroes = [goku,vegeta, boo, goten, trunks]
var winnerOfBattleRoyale = 
	reduceMonoid(monoidOfBetterGuy, heroes) // renvoit boo
					

fight est bien une loi de composition interne, associative, avec un élément neutre

var fight = function (guy1:Guy, guy2:Guy):Guy {	
	return guy1.power > guy2.power ? guy1 : guy2
}

var mrSatan = new Guy(0);

//vaut true
fight(goku,fight(boo, vegeta)).equals(fight(fight(goku, boo), vegeta))

fight(goku, mrSatan).equal(goku) // vaut true
fight(mrSatan, goku).equal(goku) // vaut true
					

Au fond,

vous en utilisez tous les jours,

des monoïdes

Quelques exemples

(ensemble, opération, élément neutre)

• (number, +, 0)
• (number, *, 1)
• (number positif, max, 0)
• (string, +, '')
• (Array, concat, [])
• (Promise, Q.all, Q)

Construction de monoïde à partir d'un autre

Wrapping

	//exemple de monoide :
	{
	    ZERO: new Guy(0),
	    combine: (a, b) => new Guy(a.power + b.power)
	};

	{
	    ZERO: new Guy(1),
	    combine: (a, b) => new Guy(a.power * b.power)
	};
					

Composition

class Guy {
    constructor(public power:number, public name:string) {}
} 

//exemple de monoide :
{
    ZERO: new Guy(0, ""),
    combine: (a, b) => new Guy(a.power + b.power, a.name + b.name)
};
					

Monades

{
		ZERO: Some(0),
		combine: (a:Option<number>, b:Option<number>) => {
		    return a.flatMap(c => b.map( d => c + d))
		}
}
					

Promesses

{
		ZERO: Q(0),
		combine: (a:Q.IPromise<number>, b:Q.IPromise<number>) => {
		    return Q.all([a,b]).then( list => list[0] + list[1] )
		}
}
					

Soyons pédant :

en fait ca marche pour tous les morphismes de monoide

Certains langages sont plus adaptés que d'autres à l'utilisation de ce genre d'abstraction

• Haskell possède un type natif Monoid
• Scalaz propose un type Monoid pour Scala
• Et même PHPZ pour PHP !

En conclusion - le monoide

• Lisibilité
• Parcours sous forme d'arbre
• Parallélisation

En conclusion - les mathématiques

• Les gros mots des matheux couvrent des abstractions
• Comme en programmation, les abstractions permettent la réutilisabilité
• Ces abstractions imposent des contrats aux ensembles auxquels elles s'appliquent...
• ... comme nos interfaces
• Il est donc intéressant de s'y plonger, pour ne pas réinventer la roue

Des questions ?