Kapitel 12: Traversierung des Steins

Bisher haben Sie in unserem Container-Zirkus gesehen, wie wir den wilden Funktor gezähmt und gezwungen haben, beliebige Operationen auszuführen. Sie staunten über das Jonglieren gefährlicher Effekte mittels Applikation zur Ergebnisaggregation. Sie sahen, wie Container durch Join in Luft auflösten und Effekte in der Komposition verschmolzen. Zuletzt haben wir Typen vor Ihren Augen transformiert.

Für unseren nächsten Trick betrachten wir Traversals. Wir werden Typen wie Trapezkünstler übereinander schwingen sehen, während Werte intakt bleiben. Effekte werden wie Karussellwagen neu geordnet. Wenn Container sich wie Schlangenmenschen verheddern, glättet diese Schnittstelle das Chaos. Unterschiedliche Effektreihenfolgen zeigen verschiedene Verhaltensmuster. Rein in die Datenstrukturen – los geht's!

Typen & Typen

Lassen Sie uns abenteuern:

// readFile :: FileName -> Task Error String

// firstWords :: String -> String
const firstWords = compose(intercalate(' '), take(3), split(' '));

// tldr :: FileName -> Task Error String
const tldr = compose(map(firstWords), readFile);

map(tldr, ['file1', 'file2']);
// [Task('hail the monarchy'), Task('smash the patriarchy')]

Hier lesen wir Dateien und erhalten nutzlose Task-Arrays. Wie können wir diese verzweigen? Ideal wäre eine Typumwandlung von [Task Error String] zu Task Error [String]. So hätten wir einen asynchronen Wert mit allen Ergebnissen – praktischer als viele unkoordinierte Futures.

Ein letztes Knobelbeispiel:

// getAttribute :: String -> Node -> Maybe String
// $ :: Selector -> IO Node

// getControlNode :: Selector -> IO (Maybe (IO Node))
const getControlNode = compose(map(map($)), map(getAttribute('aria-controls')), $);

Diese IOs sehnen sich nach Vereinigung. Wir würden sie gerne joinen, doch ein Maybe blockiert wie ein Aufpasser. Durch Typumstellung auf IO (Maybe Node) könnten sie endlich zusammengeführt werden.

Typ-Feng-Shui

Die Traversable-Schnittstelle umfasst zwei Funktionen: sequence und traverse.

Typ-Neuanordnung mit sequence:

sequence(List.of, Maybe.of(['the facts'])); // [Just('the facts')]
sequence(Task.of, new Map({ a: Task.of(1), b: Task.of(2) })); // Task(Map({ a: 1, b: 2 }))
sequence(IO.of, Either.of(IO.of('buckle my shoe'))); // IO(Right('buckle my shoe'))
sequence(Either.of, [Either.of('wing')]); // Right(['wing'])
sequence(Task.of, left('wing')); // Task(Left('wing'))

Sehen Sie den Effekt? Verschachtelte Typen stülpen sich um wie ein umgestülpter Handschuh. Der innere Funktor wandert nach außen. Beachten Sie: sequence ist anspruchsvoll. Seine Signatur:

// sequence :: (Traversable t, Applicative f) => (a -> f a) -> t (f a) -> f (t a)
const sequence = curry((of, x) => x.sequence(of));

Das zweite Argument muss ein Traversable mit Applicative sein – meist gegeben. Aus t (f a) wird f (t a). Klar erkennen wir den Typentausch. Das erste Argument dient nur in untypisierten Sprachen als Konstruktor-Hilfe, z.B. für Left-Typen.

Anhand von Either sehen wir die Implementierung:

class Right extends Either {
  // ...
  sequence(of) {
    return this.$value.map(Either.of);
  }
}

Ist der Wert ein Applicative, genügt map für den Typensprung.

Das of-Argument wird bei mapping-resistenten Typen wie Left benötigt:

class Left extends Either {
  // ...
  sequence(of) {
    return of(this);
  }
}

Da der äußere Typ in typisierten Sprachen inferiert wird, entfällt hier of. Die Pointed Functor-Eigenschaft sichert stets ein verfügbares of.

Effektkombinatorik

Containerreihenfolge bestimmt das Verhalten: [Maybe a] toleriert Einzelfehler, Maybe [a] ist ganz oder gar nichts. Either Error (Task Error a) kann Client-Validierung abbilden, Task Error (Either Error a) Server-Validierung. Typumstellung erzeugt unterschiedliche Semantik.

// fromPredicate :: (a -> Bool) -> a -> Either e a

// partition :: (a -> Bool) -> [a] -> [Either e a]
const partition = f => map(fromPredicate(f));

// validate :: (a -> Bool) -> [a] -> Either e [a]
const validate = f => traverse(Either.of, fromPredicate(f));

partition trennt Left/Right-Werte, während validate beim ersten Fehler abbricht. Die Typreihenfolge entscheidet über das Fehlerverhalten.

Die traverse-Implementierung von List für validate:

traverse(of, fn) {
    return this.$value.reduce(
      (f, a) => fn(a).map(b => bs => bs.concat(b)).ap(f),
      of(new List([])),
    );
  }

Ein reduzierender Prozess mit der Funktion (f, a) => fn(a).map(b => bs => bs.concat(b)).ap(f). Sehen wir genauer hin:

1. reduce(..., ...)

Signatur: reduce :: [a] -> (f -> a -> f) -> f -> f. Die Liste wird punktnotiert übergeben.

2. of(new List([]))

Startwert Right([]) :: Either e [a] bestimmt den Ergebnistyp.

3. fn :: Applicative f => a -> f a

In unserem Fall fromPredicate(f) :: a -> Either e a

4. .map(b => bs => bs.concat(b))

Bei Right entsteht Either e (\[a] -> \[a]), bei Left bleibt der Fehler.

5. .ap(f)

Applikation auf f :: Either e [a]. Bei Right wird konkateniert, bei Left bleibt der vorherige Fehlerzustand.

Diese Transformation benötigt nur 6 Codezeilen und funktioniert für alle Applikativen – ein Beleg für die Kraft abstrakter APIs.

Typenwalzer

Zurück zu unseren Beispielen:

// readFile :: FileName -> Task Error String

// firstWords :: String -> String
const firstWords = compose(intercalate(' '), take(3), split(' '));

// tldr :: FileName -> Task Error String
const tldr = compose(map(firstWords), readFile);

traverse(Task.of, tldr, ['file1', 'file2']);
// Task(['hail the monarchy', 'smash the patriarchy']);

Mit traverse statt map bündeln wir Tasks wie mit Promise.all() – aber typpolymorph und wiederverwendbar. Mathematische APIs erfassen häufige Muster allgemein.

Bereinigung des letzten Beispiels:

// getAttribute :: String -> Node -> Maybe String
// $ :: Selector -> IO Node

// getControlNode :: Selector -> IO (Maybe Node)
const getControlNode = compose(chain(traverse(IO.of, $)), map(getAttribute('aria-controls')), $);

Statt map(map($)) verwenden wir chain(traverse(IO.of)) für Typumkehr und IO-Vereinigung via chain.

Gesetz und Ordnung

Bevor Sie diese Gesetze ablehnen: Sie dienen als garantierte Code-Eigenschaften. Softwarearchitektur zielt oft darauf ab, durch Einschränkungen Lösungswege zu lenken.

Interfaces ohne Gesetze sind bloße Indirektion. Mathematische Strukturen benötigen definierte Eigenschaften – ähnlich der Kapselung – zum Schutz und zur Austauschbarkeit.

Kommen Sie, wir erkunden die Gesetze:

Identität

const identity1 = compose(sequence(Identity.of), map(Identity.of));
const identity2 = Identity.of;

// test it out with Right
identity1(Either.of('stuff'));
// Identity(Right('stuff'))

identity2(Either.of('stuff'));
// Identity(Right('stuff'))

Identity in einem Funktor zu sequenzieren sollte äquivalent zum Ausgangszustand sein. Right dient als Testfall. Der Identity-Funktor ist für Gesetze fundamental wie compose.

Komposition

const comp1 = compose(sequence(Compose.of), map(Compose.of));
const comp2 = (Fof, Gof) => compose(Compose.of, map(sequence(Gof)), sequence(Fof));


// Test it out with some types we have lying around
comp1(Identity(Right([true])));
// Compose(Right([Identity(true)]))

comp2(Either.of, Array)(Identity(Right([true])));
// Compose(Right([Identity(true)]))

Funktorkompositionen bleiben unter Traversal erhalten. Bibliotheken wie quickcheck helfen bei der Gesetzesprüfung durch Fuzzing.

Dies ermöglicht Traversals-Fusion zur Performancesteigerung.

Naturalität

const natLaw1 = (of, nt) => compose(nt, sequence(of));
const natLaw2 = (of, nt) => compose(sequence(of), map(nt));

// test with a random natural transformation and our friendly Identity/Right functors.

// maybeToEither :: Maybe a -> Either () a
const maybeToEither = x => (x.$value ? new Right(x.$value) : new Left());

natLaw1(Maybe.of, maybeToEither)(Identity.of(Maybe.of('barlow one')));
// Right(Identity('barlow one'))

natLaw2(Either.of, maybeToEither)(Identity.of(Maybe.of('barlow one')));
// Right(Identity('barlow one'))

Natürliche Transformationen vor/nach Typumstellung müssen äquivalent sein.

Praktische Konsequenz:

traverse(A.of, A.of) === A.of;

Erneut ein Performancevorteil.

Zusammenfassung

Traversable ist ein mächtiges Interface zur Typumordnung. Effektkontrolle durch Reihenfolgeänderung und Entschachtelung ebnet den Weg für join-Operationen. Weiter geht's mit dem mächtigsten Interface: Monoid.

Übungen

Gegeben folgende Elemente:

// httpGet :: Route -> Task Error JSON

// routes :: Map Route Route
const routes = new Map({ '/': '/', '/about': '/about' });

Let's Practice!

Transformieren Sie die Signatur von getJsons mit Traversable zu Map Route Route → Task Error (Map Route JSON) // getJsons :: Map Route Route -> Map Route (Task Error JSON) const getJsons = map(httpGet);

---

Validierungsfunktion:

// validate :: Player -> Either String Player
const validate = player => (player.name ? Either.of(player) : left('must have name'));

Let's Practice!

Aktualisieren Sie mit validate und Traversable die startGame-Signatur, um das Spiel nur bei validen Spielern zu starten // startGame :: [Player] -> [Either Error String] const startGame = compose(map(map(always('game started!'))), map(validate));

---

Dateisystem-Helper:

// readfile :: String -> String -> Task Error String
// readdir :: String -> Task Error [String]

Let's Practice!

Nutzen Sie Traversable zum Entschachteln von Task & Maybe // readFirst :: String -> Task Error (Maybe (Task Error String)) const readFirst = compose(map(map(readfile('utf-8'))), map(safeHead), readdir);