Kapitel 13: Monoide vereinen alles

Wilde Kombination

In diesem Kapitel untersuchen wir Monoide anhand von Halbgruppen. Monoide sind das Bindemittel der mathematischen Abstraktion. Sie erfassen ein Konzept, das sich über mehrere Disziplinen erstreckt und sie im übertragenen Sinne buchstäblich vereint. Sie sind die ominöse Kraft, die alles Berechenbare verbindet. Der Sauerstoff in unserer Codebasis, der Boden, auf dem sie läuft, quantenverschränkte Kodierung.

Monoide drehen sich um Kombination. Aber was ist Kombination? Sie kann so vieles bedeuten: Akkumulation, Verkettung, Multiplikation, Auswahl, Komposition, Ordnung, sogar Auswertung! Hier sehen wir viele Beispiele, aber wir erkunden nur vorsichtig die Ausläufer des Monoid-Berges. Die Instanzen sind zahlreich und die Anwendungen vielfältig. Ziel dieses Kapitels ist es, eine gute Intuition zu vermitteln, damit Sie eigene Monoide erstellen können.

Abstraktion der Addition

Die Addition hat interessante Eigenschaften, die wir diskutieren sollten. Betrachten wir sie durch unsere Abstraktionsbrille.

Zunächst ist sie eine binäre Operation, also eine Verknüpfung, die zwei Werte aus derselben Menge nimmt und einen Wert zurückgibt.

// a binary operation
1 + 1 = 2

Sehen Sie? Zwei Werte im Definitionsbereich, ein Wert im Zielbereich - alles in der gleichen Zahlenmenge. Man sagt, Zahlen sind "unter Addition abgeschlossen", was bedeutet, dass sich der Typ nie ändert. Dadurch können wir die Operation verketten:

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

Hinzu kommt (welch berechnetes Wortspiel...) die Assoziativität, die uns freie Gruppierung der Operationen ermöglicht. Nebenbei ist eine assoziative binäre Operation ein Rezept für Parallelverarbeitung, da wir Arbeit portionieren können.

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

Verwechseln Sie dies nicht mit Kommutativität, die Umgruppierung der Reihenfolge erlaubt. Zwar gilt dies für Addition, aber diese Eigenschaft ist für unsere Abstraktion zu speziell.

Welche Eigenschaften sollten überhaupt in unserer abstrakten Superklasse sein? Was ist additionsspezifisch und was verallgemeinerbar? Diese Denkweise nutzten Mathematiker bei der Konzeption abstrakter Algebra-Schnittstellen.

Historisch entstand das Gruppen-Konzept bei der Addition-Abstraktion. Eine Gruppe enthält Zusätze wie negative Zahlen. Hier interessiert uns nur der assoziative binäre Operator, daher wählen wir die weniger spezifische Halbgruppe-Schnittstelle. Eine Halbgruppe hat eine concat-Methode als assoziative binäre Operation.

Implementieren wir sie für Addition als Sum:

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

Hinweis: concat nimmt einen anderen Sum-Wert und gibt stets Sum zurück.

Ich verwende eine Objektfabrik statt Prototypen, da Sum nicht pointed ist und wir new vermeiden möchten. Anwendungsbeispiel:

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

So können wir gegen Schnittstellen programmieren. Da diese aus der Gruppentheorie stammt, hat sie Jahrhunderte dokumentierter Anwendungen - gratis Dokumentation!

Wie erwähnt ist Sum weder pointed noch ein Funktor. Als Übung prüfen Sie die Gesetze. Kurz: Es hält nur Zahlen, daher ist map hier sinnlos - es könnte den Wert nicht transformieren.

Warum nützlich? Wie bei jeder Schnittstelle können wir Instanzen austauschen:

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) })

Dies beschränkt sich nicht auf Zahlen. Weitere Typen:

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'})

Bei langer Betrachtung zeigt sich das Muster überall: Datenstrukturen mergen, Logik kombinieren, Strings bauen... fast jede Aufgabe lässt sich in diese kombinierbare Schnittstelle pressen.

Ich habe Map mehrfach verwendet. Map umhüllt Object für methodische Erweiterungen ohne Universumsänderung.

Alle meine Lieblingsfunktoren sind Halbgruppen.

Bisherige Funktor-Typen implementieren auch Halbgruppen. Beispiel Identity („the artist previously known as Container“):

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

Es ist eine Halbgruppe genau dann, wenn sein __value eine Halbgruppe ist. Wie ein Papierflugzeug mit brüchigen Flügeln: Es funktioniert nur während es eines hält.

Andere Typen:

// 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])

Besonders nützlich bei verschachtelten Halbgruppen:

// 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})))

Im ersten Beispiel kombiniert ein IO ein Either mit Map zur Formularvalidierung. Dann Serverabfragen mit Task und Array. Schließlich Task, Maybe und Map zum Laden und Mergen von Einstellungen.

Dies kann mit chain oder ap erfolgen, aber Halbgruppen fassen es prägnanter.

Dies erstreckt sich über Funktoren hinaus. Jedes aus Halbgruppen bestehende Objekt ist selbst eine Halbgruppe: Konkatenation des Ganzen durch Teilekonkatenation.

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)))

Alles kombiniert sich elegant. Mit Map-Typ sogar automatisch:

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))})

Wir können beliebig viele kombinieren - wie Bäume im Wald oder Flammen im Feuer, je nach Codebase.

Standardverhalten ist Inhaltskombination, manchmal auch Container-Kombination. Beispiel Stream:

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

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

Eventstreams kombinieren durch Zusammenführung. Alternativ könnte man Halbgruppen-Inhalte verlangen. Für Task gibt es etwa frühere/spätere Kombination oder erste Right-Wahl. Die Alternative-Schnittstelle implementiert solche Auswahloptionen.

Monoide für Nichts

Wir abstrahierten Addition, hatten aber kein Null-Konzept.

Null wirkt als neutrales Element: Jedes Element + 0 bleibt gleich. Abstrakt ist 0 ein neutrales empty-Element. Es muss beidseitig neutral wirken:

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

Nennen wir dies empty und erstellen ein Monoid-Interface. Nehmen Sie eine Halbgruppe und fügen Sie ein neutrales Element hinzu. Implementierung mit empty-Funktion:

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)

Das ist, als fragte man, warum Null nützlich ist. Wie gar nichts zu fragen...

Wenn nichts bleibt: Null. Fehlertoleranz, Neustart, Preisschild. Sie kann vernichten oder retten.

Code-technisch entsprechen sie sinnvollen Defaults:

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

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

Oder Rückgabe bei Leere:

sum([]) // 0

Perfekt als Akkumulator-Startwert...

Falten des Hauses

concat und empty passen perfekt in reduce. Ohne empty wird es riskant:

// 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

Peng! Wie ein verdrehter Knöchel beim Marathon führt dies zur Laufzeitausnahme. JavaScript erlaubt Pistolen an Sneakern, stoppt aber bei leerem Array. Was sollte es zurückgeben? NaN, false, -1? Mit fold und empty wird's sicher:

Sicheres fold mit obligatorischem empty:

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

Der initiale m-Wert ist unser empty-Startpunkt. Wir komprimieren ein Array zu einem Diamantwert.

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>])

Manuelle empty-Angabe bei undefinierbarem Typ-Empty. Getypte Sprachen erkennen dies automatisch.

Kein vollständiges Monoid

Einige Halbgruppen können keine Monoide werden. Beispiel First:

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)})

Account-Zusammenführung mit First-ID. Kein empty möglich, aber dennoch nützlich.

Große vereinheitlichende Theorie

Gruppen- oder Kategorientheorie?

Binäre Operationen sind in abstrakter Algebra allgegenwärtig. In der Kategorientheorie benötigen wir jedoch Identitäten. Daher starten wir mit Halbgruppen und werden mit empty zu Monoiden.

Monoide bilden eine Einzelobjekt-Kategorie: Morphismus ist concat, empty die Identität, Komposition garantiert.

Komposition als Monoid

Funktionen vom Typ a -> a heißen Endomorphismen. Das Monoid Endo erfasst dies:

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?']

Gleiche Typen ermöglichen concat via compose.

Monaden als Monoide

join komprimiert zwei (geschachtelte) Monaden assoziativ. Als natürliche Transformation bildet es in der Endofunktoren-Kategorie ein Monoid (Monade). Details erfordern Recherche.

Applikative als Monoide

Applikative Funktoren haben eine monoidale Formulierung (lax monoidal functor). Implementierung über Monoid und ap-Rekonstruktion:

// 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)

Zusammenfassung

Alles ist vernetzt. Monoide sind mächtige Modellierungswerkzeuge für Architektur bis Datenelemente. Nutzen Sie sie bei Kombinationsaufgaben und erweitern Sie den Anwendungsbereich.

Übungen