Ich versuche und schaffe es nicht, die traverse
Funktion zu nutzen Data.Traversable
. Ich kann den Punkt nicht erkennen. Kann mir jemand bitte einen imperativen Hintergrund erklären, da ich einen imperativen Hintergrund habe? Pseudocode wäre sehr dankbar. Vielen Dank.
98
Antworten:
traverse
ist dasselbe wiefmap
, außer dass Sie damit auch Effekte ausführen können, während Sie die Datenstruktur neu erstellen.Schauen Sie sich das Beispiel aus der
Data.Traversable
Dokumentation an.Die
Functor
Instanz vonTree
wäre:Es wird der gesamte Baum neu erstellt und
f
auf jeden Wert angewendet.Die
Traversable
Instanz ist fast dieselbe, außer dass die Konstruktoren im anwendungsbezogenen Stil aufgerufen werden. Dies bedeutet, dass wir beim Wiederaufbau des Baums (Nebenwirkungen) haben können. Die Anwendung ist fast die gleiche wie bei Monaden, außer dass die Auswirkungen nicht von früheren Ergebnissen abhängen können. In diesem Beispiel bedeutet dies, dass Sie abhängig von den Ergebnissen der Neuerstellung des linken Zweigs beispielsweise nichts anderes als den rechten Zweig eines Knotens tun können.Aus historischen Gründen
Traversable
enthält die Klasse auch eine monadische Version vontraverse
aufgerufenmapM
. In jeder HinsichtmapM
ist es dasselbe wietraverse
- es existiert als separate Methode, weil esApplicative
erst später zu einer Oberklasse von wurdeMonad
.Wenn Sie dies in einer unreinen Sprache implementieren würden,
fmap
wäre dies dasselbe wietraverse
, da es keine Möglichkeit gibt, Nebenwirkungen zu verhindern. Sie können es nicht als Schleife implementieren, da Sie Ihre Datenstruktur rekursiv durchlaufen müssen. Hier ist ein kleines Beispiel, wie ich es in Javascript machen würde:Wenn Sie es so implementieren, beschränken Sie sich auf die Effekte, die die Sprache zulässt. Wenn Sie zB Nichtdeterminismus wollen (was die Listeninstanz von Anwendungsmodellen ist) und Ihre Sprache nicht eingebaut ist, haben Sie kein Glück.
quelle
Functor
, dem Teil, der nicht parametrisch ist. Der Zustandswert inState
, das Versagen inMaybe
undEither
die Anzahl der Elemente in[]
und natürlich beliebige externe Nebenwirkungen inIO
. Ich mag es nicht als Oberbegriff (wie dieMonoid
Funktionen, die "leer" und "anhängen" verwenden, ist das Konzept allgemeiner als der Begriff zunächst vermuten lässt), aber es ist ziemlich häufig und erfüllt den Zweck gut genug.ap
den vorherigen Ergebnissen abhängen lassen. Ich habe diese Bemerkung entsprechend umformuliert.traverse
verwandelt Dinge in aTraversable
in einTraversable
von Dingen "in" einApplicative
, gegeben eine Funktion, dieApplicative
s aus Dingen macht.Verwenden wir
Maybe
asApplicative
und listen as aufTraversable
. Zuerst brauchen wir die Transformationsfunktion:Wenn also eine Zahl gerade ist, bekommen wir die Hälfte davon (innerhalb von a
Just
), sonst bekommen wirNothing
. Wenn alles "gut" läuft, sieht es so aus:Aber...
Der Grund ist, dass die
<*>
Funktion verwendet wird, um das Ergebnis zu erstellen, und wenn eines der Argumente istNothing
, kehren wirNothing
zurück.Ein anderes Beispiel:
Diese Funktion generiert eine Längenliste
x
mit dem Inhaltx
, zBrep 3
=[3,3,3]
. Was ist das Ergebnis vontraverse rep [1..3]
?Wir bekommen die Teilergebnisse
[1]
,[2,2]
und[3,3,3]
unter Verwendungrep
. Nun ist die Semantik von ListenApplicatives
wird „alle Kombinationen nehmen“, zB(+) <$> [10,20] <*> [3,4]
ist[13,14,23,24]
."Alle Kombinationen" von
[1]
und[2,2]
sind zweimal[1,2]
. Alle Kombinationen sind zweimal[1,2]
und[3,3,3]
sechsmal[1,2,3]
. Also haben wir:quelle
fac n = length $ traverse rep [1..n]
liftA2 (,)
als ob die allgemeinere Form verwendet wirdtraverse
.Ich denke, es ist am einfachsten zu verstehen
sequenceA
,traverse
wie folgt definiert werden kann.sequenceA
sequenziert die Elemente einer Struktur von links nach rechts und gibt eine Struktur mit derselben Form zurück, die die Ergebnisse enthält.Sie können sich auch vorstellen
sequenceA
, die Reihenfolge von zwei Funktoren umzukehren, z. B. von einer Liste von Aktionen in eine Aktion zu wechseln, die eine Liste von Ergebnissen zurückgibt.Nehmen Sie also
traverse
eine Struktur und wenden Sief
an, um jedes Element in der Struktur in eine Anwendung umzuwandeln. Anschließend werden die Auswirkungen dieser Anwendungen von links nach rechts sequenziert, wobei eine Struktur mit derselben Form zurückgegeben wird, die die Ergebnisse enthält.Sie können es auch mit vergleichen
Foldable
, wodurch die zugehörige Funktion definiert wirdtraverse_
.Sie sehen also, dass der Hauptunterschied zwischen
Foldable
und darinTraversable
besteht, dass Sie mit letzterem die Form der Struktur beibehalten können, während Sie mit ersterem das Ergebnis in einen anderen Wert falten müssen.Ein einfaches Beispiel für seine Verwendung ist die Verwendung einer Liste als durchlaufbare Struktur und
IO
als Anwendung:Während dieses Beispiel eher nicht aufregend ist, werden die Dinge interessanter, wenn
traverse
es für andere Arten von Behältern oder für andere Anwendungen verwendet wird.quelle
sequenceA . fmap
für Listen gleichbedeutend mitsequence . map
nicht wahr?IO
Typ kann verwendet werden, um Nebenwirkungen auszudrücken; (2) istIO
zufällig eine Monade, was sich als sehr praktisch herausstellt. Monaden sind nicht wesentlich mit Nebenwirkungen verbunden. Es sollte auch beachtet werden, dass es eine Bedeutung von "Wirkung" gibt, die breiter ist als "Nebenwirkung" im üblichen Sinne - eine, die reine Berechnungen beinhaltet. Zu diesem letzten Punkt, siehe auch Was genau bedeutet „effekt“ bedeuten .Es ist irgendwie so
fmap
, nur dass Sie Effekte innerhalb der Mapper-Funktion ausführen können, wodurch auch der Ergebnistyp geändert wird.Stellen Sie sich eine Liste von Ganzzahlen vor, die Benutzer-IDs in einer Datenbank darstellen :
[1, 2, 3]
. Wenn Siefmap
diese Benutzer-IDs zu Benutzernamen verwenden möchten , können Sie keine herkömmliche verwendenfmap
, da Sie innerhalb der Funktion auf die Datenbank zugreifen müssen, um die Benutzernamen zu lesen (was einen Effekt erfordert - in diesem Fall mithilfe derIO
Monade).Die Unterschrift von
traverse
ist:Mit
traverse
können Sie Effekte ausführen. Daher sieht Ihr Code zum Zuordnen von Benutzer-IDs zu Benutzernamen folgendermaßen aus:Es gibt auch eine Funktion namens
mapM
:Jede Verwendung von
mapM
kann durch ersetzt werdentraverse
, aber nicht umgekehrt.mapM
funktioniert nur für Monaden, währendtraverse
ist aber allgemeiner.Wenn Sie nur einen Effekt erzielen wollen und keinen nützlichen Wert zurückgeben, gibt es
traverse_
undmapM_
Versionen dieser Funktionen, die beide den Rückgabewert der Funktion ignoriert und sind etwas schneller.quelle
traverse
ist die Schleife. Die Implementierung hängt von der zu durchlaufenden Datenstruktur ab. Das könnte eine Liste, Baum, seinMaybe
,Seq
(uss), oder etwas , das eine generische Art und Weise hat der wird über so etwas wie eine for-Schleife oder rekursive Funktion durchlaufen. Ein Array hätte eine for-Schleife, eine Liste eine while-Schleife, einen Baum, entweder etwas Rekursives oder die Kombination eines Stapels mit einer while-Schleife; In funktionalen Sprachen benötigen Sie diese umständlichen Schleifenbefehle jedoch nicht: Sie kombinieren den inneren Teil der Schleife (in Form einer Funktion) direkter und weniger ausführlich mit der Datenstruktur.Mit der
Traversable
Typklasse könnten Sie Ihre Algorithmen wahrscheinlich unabhängiger und vielseitiger schreiben. Aber meiner Erfahrung nachTraversable
wird dies normalerweise nur verwendet, um Algorithmen einfach auf vorhandene Datenstrukturen zu kleben. Es ist sehr schön, keine ähnlichen Funktionen für verschiedene qualifizierte Datentypen schreiben zu müssen.quelle