Ich arbeite durch Lernen Sie ein Haskell, und ich bin auf dem Abschnitt über Monoids. In diesem Abschnitt definiert der Autor die foldMap-Methode für einen Baum wie folgt:
%Vor%Was gut funktioniert und ist total baller. Dann sagt er: "Jetzt, wo wir eine faltbare Instanz für unseren Baumtyp haben, bekommen wir foldr und foldl kostenlos!" und zeigt den folgenden Code:
%Vor%Jetzt bin ich verwirrt. Nirgends wurde eine Implementierung für Foldl oder Foldr für Trees geschrieben. Die Funktionen scheinen ähnlich wie die Faltkarte zu funktionieren, aber den anfänglichen Akkumulator als den Kopf des Baumes zu setzen und dann über das entsprechende Monoid zu falten. Aber es kann nicht wirklich so funktionieren, weil foldl und foldr allgemeinere Funktionen als die Monoiden '+' und '*' als Argumente. Wo werden foldl und foldr tatsächlich implementiert, wie funktionieren sie, und warum führt die Definition von foldMap dazu, dass sie existieren?
Sehen Sie sich die Quelle von Foldable an. . Er definiert foldr mit foldMap und umgekehrt, also reicht es aus, die für Sie bequemere zu definieren (obwohl die Implementierung beider Möglichkeiten Ihnen einige Leistungsvorteile bringen kann):
Sehen wir uns an, was hier an einem Beispiel passiert. Nehmen wir an, wir werden eine Liste mit [i, j, k] falten. Die rechte Falte mit f und z ist
Dies kann alternativ als
ausgedrückt werden %Vor% Mit f konvertieren wir jedes Element der Liste in einen Endomorphismus am b und komponieren sie zusammen . Endomorphismen bilden nun ein Monoid, das in Haskell mit Endo ausgedrückt wird: sein mempty ist nur id und mappend ist . . Also können wir es als
und wir können den inneren Teil als foldMap (Endo . f) [i, j, k] ausdrücken.
Zusammenfassend: Die Schlüsselidee ist, dass Endomorphismen über einer Domäne ein Monoid bilden und f :: a -> (b -> b) Elemente von a in Endomorphismen über b abbildet.
Das Gegenteil wird ausgedrückt als
%Vor% Hier haben wir f :: a -> m , wobei m ein Monoid ist, und wenn wir es mit mappend zusammensetzen, erhalten wir mappend . f :: a -> (m -> m) , was ein Element x vom Typ a und eine Funktion für m ergibt. Das konvertiert u :: m in mappend (f u) k . Und dann benutzt es diese Funktion, um alle Elemente der Struktur zu falten.
Von Ссылка :
%Vor% Sie haben also Standardimplementierungen (in diesem Fall sogar zirkulär). Deshalb gibt es einen Kommentar: "Minimale vollständige Definition: foldMap oder foldr." in der Beschreibung der Klasse Foldable type (siehe Ссылка )
Ein einfacheres Beispiel für diese Technik ist die Klasse Eq type, wobei (==) und (/=) in Bezug aufeinander definiert sind, aber natürlich müssen Sie mindestens eine davon in einer Instanz implementieren (sonst Sie erhalten eine Endlosschleife).