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

magma

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,

boo

Pour cette démonstration,
utilisons TypeScript  :

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

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 ?