Chapitre 13 : Les monoïdes unifient tout

Combinaisons sauvages

Dans ce chapitre, nous étudierons les monoïdes à travers les semi-groupes. Les monoïdes sont la gomme à mâcher dans les cheveux de l'abstraction mathématique. Ils captent une notion transdisciplinaire, les reliant tant métaphoriquement que concrètement. Ils constituent la force omniprésente qui connecte toutes les formes de calcul. L'oxygène de notre base de code, le sol sur lequel il fonctionne, une intrication quantique encodée.

Les monoïdes concernent la combinaison. Mais qu'est-ce que la combinaison ? Cela englobe accumulation, concaténation, multiplication, sélection, composition, ordonnancement jusqu'à l'évaluation ! Nous verrons de nombreux exemples ici, n'effleurant que les contreforts de la montagne des monoïdes. Leurs applications sont immenses. Ce chapitre vise à établir une intuition solide pour créer vos propres monoïdes.

Abstraction de l'addition

L'addition présente des propriétés intéressantes. Examinons-la avec notre regard abstrait.

C'est d'abord une opération binaire : une opération prenant deux éléments d'un ensemble pour en retourner un troisième du même ensemble.

// a binary operation
1 + 1 = 2

Observez ? Domaine et codomaine identiques - les nombres. On dit qu'ils sont « clos par addition ». Cela permet d'enchaîner les opérations, le résultat restant toujours un nombre :

// we can run this on any amount of numbers
1 + 7 + 5 + 4 + ...

De plus (quel jeu de mot calculé...), l'associativité permet de regrouper librement les opérations. Une opération binaire associative est un terreau fertile pour le calcul parallèle via le découpage des tâches.

// associativity
(1 + 2) + 3 = 6
1 + (2 + 3) = 6

Ne confondez pas avec la commutativité (réorganisation des termes) qui, bien que présente dans l'addition, n'est pas notre centre d'intérêt ici - trop spécifique pour nos besoins d'abstraction.

Quelles propriétés méritent d'être abstraites ? Les ancêtres mathématiciens ont conçu les interfaces algébriques en répondant à cette question.

L'abstraction de l'addition a mené au concept de groupe (avec éléments inverses). Nous nous concentrons sur l'opérateur binaire associatif via l'interface semi-groupe, définie par une méthode concat.

Implémentons-la pour l'addition sous Sum :

const Sum = (x) => ({
  x,
  concat: ({ x: y }) => Sum(x + y),
  empty: () => Sum(0), // Nécessaire pour l'interface monoïde
})

const Sum = x => ({
  x,
  concat: other => Sum(x + other.x)
})

Notez que concat nécessite un autre Sum et retourne toujours un Sum.

J'utilise une fabrique d'objets plutôt que notre approche prototype habituelle, principalement car Sum n'est pas un foncteur pointé et évite le new. Exemple d'usage :

Sum(1).concat(Sum(2)).concat(Sum(3)) // Sum(6)

Sum(1).concat(Sum(3)) // Sum(4)
Sum(4).concat(Sum(37)) // Sum(41)

Nous programmons ainsi contre une interface ancrée dans la théorie des groupes, bénéficiant de siècles de littérature.

Sum n'est ni un foncteur pointé ni un foncteur. Exercice : vérifier les lois (indice : map est impossible car il ne peut transformer le type sous-jacent).

Utilité ? Comme toute interface, permuter les instances produit différents résultats :

const Product = (x) => ({
  x,
  concat: ({ x: y }) => Product(x * y),
})

```js
const Product = x => ({ x, concat: other => Product(x * other.x) })

const Min = x => ({ x, concat: other => Min(x < other.x ? x : other.x) })

const Max = x => ({ x, concat: other => Max(x > other.x ? x : other.x) })

Non limité aux nombres. Autres types :

const Any = (x) => ({ x, concat: ({ x: y }) => Any(x || y) })
const All = (x) => ({ x, concat: ({ x: y }) => All(x && y) })

```js
const Any = x => ({ x, concat: other => Any(x || other.x) })
const All = x => ({ x, concat: other => All(x && other.x) })

Any(false).concat(Any(true)) // Any(true)
Any(false).concat(Any(false)) // Any(false)

All(false).concat(All(true)) // All(false)
All(true).concat(All(true)) // All(true)

[1,2].concat([3,4]) // [1,2,3,4]

"miracle grow".concat("n") // miracle grown"

Map({day: 'night'}).concat(Map({white: 'nikes'})) // Map({day: 'night', white: 'nikes'})

À force d'observer ces schémas, leur ubiquité saute aux yeux : fusion de structures de données, combinaison logique, construction de chaînes... Presque toute tâche peut être modelée via cette interface combinatoire.

J'ai utilisé Map à plusieurs reprises - il encapsule Object pour l'enrichir méthodiquement sans altérations profondes.

Tous mes foncteurs préférés sont des semi-groupes.

Les types implémentant foncteur implémentent aussi semi-groupe. Voyons Identity (alias Container) :

const Identity = (x) => ({
  __value: x,
  concat: (o) => Identity(x.concat(o.__value)),
})

```js
Identity.prototype.concat = function(other) {
  return new Identity(this.__value.concat(other.__value))
}

Identity.of(Sum(4)).concat(Identity.of(Sum(1))) // Identity(Sum(5))
Identity.of(4).concat(Identity.of(1)) // TypeError: this.__value.concat is not a function

C'est un semi-groupe si et seulement si sa __value en est un. Comme un conteneur instable, il reflète les propriétés de son contenu.

D'autres types suivent ce modèle :

IO.empty = () => IO.of(empty)
IO.prototype.concat = function (o) {
  return IO.of(this.__value.concat(o.__value))
}

```js
// combine with error handling
Right(Sum(2)).concat(Right(Sum(3))) // Right(Sum(5))
Right(Sum(2)).concat(Left('some error')) // Left('some error')


// combine async
Task.of([1,2]).concat(Task.of([3,4])) // Task([1,2,3,4])

Utilité maximale en combinant ces semi-groupes en cascade :

formValidation
  .concat(formSubmission)
  .concat(createUser)
// Combinaison de Task, Either, Array...

```js
// formValues :: Selector -> IO (Map String String)
// validate :: Map String String -> Either Error (Map String String)

formValues('#signup').map(validate).concat(formValues('#terms').map(validate)) // IO(Right(Map({username: 'andre3000', accepted: true})))
formValues('#signup').map(validate).concat(formValues('#terms').map(validate)) // IO(Left('one must accept our totalitarian agreement'))

serverA.get('/friends').concat(serverB.get('/friends')) // Task([friend1, friend2])

// loadSetting :: String -> Task Error (Maybe (Map String Boolean))
loadSetting('email').concat(loadSetting('general')) // Task(Maybe(Map({backgroundColor: true, autoSave: false})))

Dans ces exemples : validation de formulaire via IO/Either/Map, requêtes asynchrones avec Task/tableau, et chargement/analyse de configurations avec une pile Task/Maybe/Map.

chain/ap sont possibles, mais les semi-groupes expriment l'intention plus clairement.

Cette logique transcende les foncteurs : toute structure composée de semi-groupes est elle-même un semi-groupe.

const Analytics = (clicks, path, idleTime) => ({
  clicks,
  path,
  idleTime,
  concat: other =>
    Analytics(clicks.concat(other.clicks), path.concat(other.path), idleTime.concat(other.idleTime))
})

Analytics(Sum(2), ['/home', '/about'], Right(Max(2000))).concat(Analytics(Sum(1), ['/contact'], Right(Max(1000))))
// Analytics(Sum(3), ['/home', '/about', '/contact'], Right(Max(2000)))

Tout se combine harmonieusement. La même logique s'applique avec Map :

const settings = Map({
  volume: Max(50),
  delay: Sum(2000),
  features: Any(false),
})

```js
Map({clicks: Sum(2), path: ['/home', '/about'], idleTime: Right(Max(2000))}).concat(Map({clicks: Sum(1), path: ['/contact'], idleTime: Right(Max(1000))}))
// Map({clicks: Sum(3), path: ['/home', '/about', '/contact'], idleTime: Right(Max(2000))})

Nous pouvons superposer autant d'instances que nécessaire, comme ajouter un arbre à la forêt... ou une étincelle à l'incendie selon votre codebase.

Par défaut, on combine le contenu. Mais parfois, on combine les conteneurs. Exemple avec Stream :

Stream([clickLog]).concat(Stream([scrollLog])

```js
const submitStream = Stream.fromEvent('click', $('#submit'))
const enterStream = filter(x => x.key === 'Enter', Stream.fromEvent('keydown', $('#myForm')))

submitStream.concat(enterStream).map(submitForm) // Stream()

Les flux d'événements fusionnent en un nouveau flux. Les instances varient : Task peut combiner selon la première réussite, etc. L'interface Alternative traite ces cas de sélection.

Les monoïdes à partir de rien

En abstraisant l'addition, nous avons omis zéro comme les Babyloniens.

Zéro est l'élément neutre : $x + 0 = x$. Conceptuellement, empty représente cette neutralité. L'impact est identique à gauche/droite : $0 + 1 = 1 = 1 + 0$

// identity
1 + 0 = 1
0 + 1 = 1

Nommons ce concept empty avec l'interface Monoid : semi-groupe + élément neutre. Implémentation via structure cohérente :

const Monoid = (x) => ({
  x,
  concat: ({ x: y }) => Monoid(x.concat(y)),
  empty: () => Monoid(/* valeur neutre spécifique */)
})

Array.empty = () => []
String.empty = () => ""
Sum.empty = () => Sum(0)
Product.empty = () => Product(1)
Min.empty = () => Min(Infinity)
Max.empty = () => Max(-Infinity)
All.empty = () => All(true)
Any.empty = () => Any(false)

L'utilité de empty ? C'est comme demander à quoi sert zéro.

Quand tout échoue, comptez sur zéro. Nombre de bugs souhaités ? Zéro. Notre tolérance face au code non sécurisé. Un nouveau départ. Destructeur ou sauveur.

En code : des valeurs par défaut sensibles :

const settings = {
  fontSize: 12,
  ...userSettings,
}

```js
const settings = (prefix="", overrides=[], total=0) => ...

const settings = (prefix=String.empty(), overrides=Array.empty(), total=Sum.empty()) => ...

Ou retourner une valeur neutre :

const safeGetData = () => cachedData || fetchFreshData()

```js
sum([]) // 0

Valeur initiale parfaite pour l'accumulateur : [...].reduce(fn, Monoid.empty())

Réduction radicale

concat et empty s'adaptent parfaitement à reduce. Mais ignorer empty mène au danger :

[].reduce((acc, x) => acc + x) // TypeError

```js
// concat :: Semigroup s => s -> s -> s
const concat = x => y => x.concat(y)

[Sum(1), Sum(2)].reduce(concat) // Sum(3)

[].reduce(concat) // TypeError: Reduce of empty array with no initial value

Erreur fatale. JavaScript échoue sur les tableaux vides. Que retourner ? NaN ? -1 ? Une solution sûre s'impose.

Créons une version sécurisée fold avec empty obligatoire :

const fold = curry((empty, xs) => xs.reduce((acc, x) => acc.concat(x), empty))

```js
// fold :: Monoid m => m -> [m] -> m
const fold = reduce(concat)

empty est le point de départ neutre. Nous broyons un tableau en une valeur unique.

fold(Sum.empty(), [Sum(1), Sum(2)]) // Sum(3)
fold(Sum.empty(), []) // Sum(0)

fold(Any.empty(), [Any(false), Any(true)]) // Any(true)
fold(Any.empty(), []) // Any(false)


fold(Either.of(Max.empty()), [Right(Max(3)), Right(Max(21)), Right(Max(11))]) // Right(Max(21))
fold(Either.of(Max.empty()), [Right(Max(3)), Left('error retrieving value'), Right(Max(11))]) // Left('error retrieving value')

fold(IO.of([]), ['.link', 'a'].map($)) // IO([<a>, <button class="link"/>, <a>])

Les derniers exemples nécessitent un empty manuel. Les langages typés l'infèrent automatiquement.

Pas tout à fait un monoïde

Certains semi-groupes ne peuvent devenir monoïdes. Exemple First :

const First = (x) => ({ x, concat: () => First(x) })

```js
const First = x => ({ x, concat: other => First(x) })

Map({id: First(123), isPaid: Any(true), points: Sum(13)}).concat(Map({id: First(2242), isPaid: Any(false), points: Sum(1)}))
// Map({id: First(123), isPaid: Any(true), points: Sum(14)})

En fusionnant des comptes, First garde le premier ID. Impossible de définir une valeur empty ici. Utilité malgré tout.

Théorie unificatrice

Théorie des groupes vs théorie des catégories ?

L'opération binaire est omniprésente en algèbre abstraite. Pour la modéliser en théorie des catégories, l'identité est requise. D'où le chemin semi-groupe → monoïde.

Les monoïdes forment une catégorie mono-objet où les morphismes sont concat, empty est l'identité, et la composition garantie.

La composition comme monoïde

Les fonctions de type a → a (endomorphismes) forment le monoïde Endo :

const Endo = (f) => ({
  run: f,
  concat: (o) => Endo((x) => f(o.run(x))),
})

```js
const Endo = run => ({
  run,
  concat: other =>
    Endo(compose(run, other.run))
})

Endo.empty = () => Endo(identity)


// in action

// thingDownFlipAndReverse :: Endo [String] -> [String]
const thingDownFlipAndReverse = fold(Endo(() => []), [Endo(reverse), Endo(sort), Endo(append('thing down')])

thingDownFlipAndReverse.run(['let me work it', 'is it worth it?'])
// ['thing down', 'let me work it', 'is it worth it?']

Leur concaténation via compose préserve les types.

La monade comme monoïde

join (qui fusionne des monades imbriquées) est une transformation naturelle. Dans la catégorie des endofoncteurs, join définit un monoïde - une Monade.

L'applicative comme monoïde

Les foncteurs applicatifs ont une formulation monoïdale (lax monoidal functor). Implémentation possible :

const App = (x) => ({
  x,
  concat: (o) => App(liftA2(concat, x, o.x)),
})

```js
// concat :: f a -> f b -> f [a, b]
// empty :: () -> f ()

// ap :: Functor f => f (a -> b) -> f a -> f b
const ap = compose(map(([f, x]) => f(x)), concat)

En résumé

Tout est interconnecté. Les monoïdes modélisent des architectures logicielles étendues jusqu'aux plus petits éléments. Pensez-y pour toute combinaison/accumulation, puis élargissez leurs applications.

Exercices