Kapitel 07: Hindley-Milner und Ich

Was ist dein Typ?

Wenn Sie neu in der funktionalen Programmierung sind, werden Sie bald bis zum Hals in Typsignaturen stecken. Typen bilden die Metasprache, die es Menschen aus unterschiedlichen Hintergründen ermöglicht, prägnant und effektiv zu kommunizieren. Meistens werden sie im Hindley-Milner-System geschrieben, das wir in diesem Kapitel gemeinsam analysieren werden.

Bei reinen Funktionen haben Typsignaturen eine Ausdruckskraft, bei der sich natürliche Sprache nicht einmal die Kerze halten kann. Diese Signaturen flüstern Ihnen die intimsten Geheimnisse einer Funktion ins Ohr. In einer einzigen, kompakten Zeile offenbaren sie Verhalten und Absicht. Wir können „freie Theoreme“ aus ihnen ableiten. Typen können inferiert werden, sodass explizite Annotationen unnötig sind. Sie lassen sich präzise feinjustieren oder allgemein halten. Sie dienen nicht nur Compiler-Checks, sondern erweisen sich als beste Dokumentation. Typsignaturen sind somit zentral für funktionale Programmierung – weitaus wichtiger, als man zunächst glaubt.

JavaScript ist eine dynamische Sprache, doch wir verzichten nicht gänzlich auf Typen. Wir arbeiten weiterhin mit Strings, Zahlen, Booleans usw. Nur fehlt die Sprachintegration, sodass wir diese Informationen mental tracken müssen. Mit Signaturkommentaren können wir dies kompensieren.

Für JavaScript existieren Typprüftools wie Flow oder der typisierte Dialekt TypeScript. Da dieses Buch funktionale Codierungsprinzipien vermitteln soll, halten wir uns an das Standardtypsystem von FP-Sprachen.

Geschichten aus der Krypta

Aus verstaubten Mathebüchern, über weite Meere von Whitepapers, zwischen lässigen Blogposts bis hin zum Quellcode selbst – überall finden wir Hindley-Milner-Typsignaturen. Das System ist simpel, bedarf aber Erklärung und Übung, um diese kleine Sprache vollständig zu erfassen.

// capitalize :: String -> String
const capitalize = s => toUpperCase(head(s)) + toLowerCase(tail(s));

capitalize('smurf'); // 'Smurf'

Hier nimmt capitalize einen String und gibt einen String zurück. Die Implementierung ist nebensächlich – die Typsignatur steht im Fokus.

In HM schreibt man Funktionen als a -> b, wobei a und b Variablen für beliebige Typen sind. Die Signatur von capitalize bedeutet somit: »Eine Funktion von String nach String«. Mit anderen Worten: Sie nimmt einen String entgegen und gibt einen String zurück.

Weitere Funktionssignaturen:

// strLength :: String -> Number
const strLength = s => s.length;

// join :: String -> [String] -> String
const join = curry((what, xs) => xs.join(what));

// match :: Regex -> String -> [String]
const match = curry((reg, s) => s.match(reg));

// replace :: Regex -> String -> String -> String
const replace = curry((reg, sub, s) => s.replace(reg, sub));

strLength folgt demselben Muster: Eingabe String, Ausgabe Number.

Andere Signaturen mögen zunächst verwirren. Ohne Details zu verstehen, betrachten Sie einfach den letzten Typ als Rückgabewert. Bei match interpretieren Sie: Nimmt Regex und String, gibt [String] zurück. Doch hier verbirgt sich eine interessante Eigenschaft, die ich erklären möchte.

Für match können wir die Signatur gruppieren:

// match :: Regex -> (String -> [String])
const match = curry((reg, s) => s.match(reg));

Ah, durch Klammerung wird es klarer: Eine Funktion, die Regex nimmt und eine Funktion von String zu [String] zurückgibt. Dank Currying ist dies exakt der Fall: Geben Sie eine Regex ein, erhalten Sie eine Funktion, die auf ihren String-Parameter wartet. Die letzte Typangabe bestimmt stets den Rückgabewert.

// match :: Regex -> (String -> [String])
// onHoliday :: String -> [String]
const onHoliday = match(/holiday/ig);

Jedes Argument entfernt jeweils einen Typ vom Anfang der Signatur. onHoliday ist match mit bereits vorhandener Regex.

// replace :: Regex -> (String -> (String -> String))
const replace = curry((reg, sub, s) => s.replace(reg, sub));

Wie bei replace mit voller Klammerung zu sehen, wird die Notation redundant. Wir lassen sie daher weg. Praktisch: replace nimmt Regex, String, String und gibt String zurück.

Zum Schluss noch dies:

// id :: a -> a
const id = x => x;

// map :: (a -> b) -> [a] -> [b]
const map = curry((f, xs) => xs.map(f));

Die id-Funktion nimmt einen beliebigen Typ a und gibt denselben Typ zurück. Typvariablen verhalten sich wie Code-Variablen. Namen wie a/b sind Konvention, aber beliebig wählbar. Gleiche Variablen bedeuten gleiche Typen. Wichtig: a -> b erlaubt beliebige Typen, aber a -> a erzwingt Identität – String -> String ist okay, String -> Bool nicht.

map nutzt Typvariablen a und b, wobei b unterschiedlich sein kann. Lesart: map nimmt Funktion a -> b, Array von a, liefert Array von b.

Diese Signatur offenbart die Funktionalität unverhüllt: Nimm Funktion a -> b, Array von a, liefere Array von b. Die einzig sinnvolle Implementierung? Wende die verdammte Funktion auf jedes a an. Alles andere wäre dreiste Lüge.

Typverständnis eröffnet weite Horizonte. Whitepapers werden verdaulicher, Signaturen selbst-dokumentierend. Mit Übung lesen Sie sie fließend – Informationen en masse ohne Handbuchstudium.

Weitere Beispiele zur Eigenanalyse:

// head :: [a] -> a
const head = xs => xs[0];

// filter :: (a -> Bool) -> [a] -> [a]
const filter = curry((f, xs) => xs.filter(f));

// reduce :: ((b, a) -> b) -> b -> [a] -> b
const reduce = curry((f, x, xs) => xs.reduce(f, x));

reduce ist vielleicht die ausdrucksstärkste Funktion – aber knifflig. Scheitern ist normal. Für Neugierige: Die Signatur verrät, dass es einen Startwert b mit jedem a-Element kombiniert, um finales b zu erzeugen.

Betrachten wir die Signatur: Die erste Funktion b -> a -> b kombiniert den Akkumulator b mit jedem a. Die Parameter b und [a] speisen diese Verarbeitung. Das Endergebnis ist der finale b-Wert – exakt wie reduce operiert.

Die Kunst der Einschränkung

Typvariablen führen zu Parametrizität: Funktionen behandeln alle Typen einheitlich. Untersuchen wir dies:

// head :: [a] -> a

head: [a] -> a – außer dem Array-Typ gibt es keine Informationen. Was kann es mit a tun? Nichts Spezifisches. Mögliche Implementierung: Erstes/letztes Element. Der Name head verrät es.

Noch ein Beispiel:

// reverse :: [a] -> [a]

Was tut reverse: [a] -> [a]? Ohne Typwissen nur generische Operationen: Umordnung ja, Sortieren nein. Polymorphe Typen schränken Möglichkeiten drastisch ein.

Diese Einschränkung ermöglicht Typsignatur-Suchen via Hoogle. Die Informationsdichte zeigt ihre Macht.

Kostenlos wie im Theorem

Neben Implementierungen ergeben sich freie Theoreme – Beispiele aus Wadlers Paper:

// head :: [a] -> a
compose(f, head) === compose(head, map(f));

// filter :: (a -> Bool) -> [a] -> [a]
compose(map(f), filter(compose(p, f))) === compose(filter(p), map(f));

Ohne Code: head nach f anwenden ≡ effizienter als map(f) gefolgt von head. Computer benötigen formale Regeln für solche Optimierungen – hier kommt Mathematik ins Spiel.

Was intuitiv logisch scheint, bedarf mathematischer Formalisierung – gerade in starren Computermodellen.

Das filter-Theorem: p ∘ f komponieren und filtern ≡ erst map(f), dann filter(p). Das Typsystem garantiert, dass filter a unverändert lässt.

Diese Logik gilt für alle polymorphen Signaturen. In JavaScript lassen sich solche Optimierungen via Tools oder compose realisieren – endlose Möglichkeiten.

Einschränkungen

Typen lassen sich an Interfaces binden:

// sort :: Ord a => [a] -> [a]

Links des Pfeils: a muss Ord implementieren. Ord definiert Ordnung. Dies dokumentiert Anforderungen und schränkt ein – sogenannte Typ-Constraints.

// assertEqual :: (Eq a, Show a) => a -> a -> Assertion

Hier sichern Eq und Show Gleichheitsprüfung und String-Darstellung von as.

Spätere Kapitel vertiefen Constraint-Konzepte.

Zusammenfassung

Hindley-Milner-Signaturen sind allgegenwärtig in der funktionalen Welt. Sie sind leicht zu lesen, benötigen aber Übung zur Meisterschaft. Ab jetzt versehen wir jede Codezeile mit Typsignaturen.

Kapitel 08: Tupperware