Kann jemand die Verfahrfunktion in Haskell erklären?

98

Ich versuche und schaffe es nicht, die traverseFunktion 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.

Konan
quelle
1
Der Artikel Die Essenz des Iteratormusters könnte hilfreich sein, da er den Begriff der schrittweisen Durchquerung aufbaut. Einige fortgeschrittene Konzepte sind jedoch vorhanden
Jackie

Antworten:

120

traverseist dasselbe wie fmap, 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.TraversableDokumentation an.

 data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)

Die FunctorInstanz von Treewäre:

instance Functor Tree where
  fmap f Empty        = Empty
  fmap f (Leaf x)     = Leaf (f x)
  fmap f (Node l k r) = Node (fmap f l) (f k) (fmap f r)

Es wird der gesamte Baum neu erstellt und fauf jeden Wert angewendet.

instance Traversable Tree where
    traverse f Empty        = pure Empty
    traverse f (Leaf x)     = Leaf <$> f x
    traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r

Die TraversableInstanz 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 Traversableenthält die Klasse auch eine monadische Version von traverseaufgerufen mapM. In jeder Hinsicht mapMist es dasselbe wie traverse- es existiert als separate Methode, weil es Applicativeerst später zu einer Oberklasse von wurde Monad.

Wenn Sie dies in einer unreinen Sprache implementieren würden, fmapwäre dies dasselbe wie traverse, 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:

Node.prototype.traverse = function (f) {
  return new Node(this.l.traverse(f), f(this.k), this.r.traverse(f));
}

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.

Sjoerd Visscher
quelle
11
Was bedeutet der Begriff "Wirkung"?
fehlender Faktor
23
@missingfaktor: Es bedeutet die Strukturinformation von a Functor, dem Teil, der nicht parametrisch ist. Der Zustandswert in State, das Versagen in Maybeund Eitherdie Anzahl der Elemente in []und natürlich beliebige externe Nebenwirkungen in IO. Ich mag es nicht als Oberbegriff (wie die MonoidFunktionen, 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.
CA McCann
@CA McCann: Verstanden. Danke für die Antwort!
fehlender Faktor
1
"Ich bin mir ziemlich sicher, dass du das nicht tun sollst [...]." Auf keinen Fall - es wäre so schlimm, als würde man die Auswirkungen von apden vorherigen Ergebnissen abhängen lassen. Ich habe diese Bemerkung entsprechend umformuliert.
Duplode
2
"Anwendbar ist fast dasselbe wie Monaden, außer dass die Effekte nicht von früheren Ergebnissen abhängen können." ... mit dieser Zeile hat eine Menge Zeug für mich geklickt, danke!
Agam
57

traverseverwandelt Dinge in a Traversablein ein Traversablevon Dingen "in" ein Applicative, gegeben eine Funktion, die Applicatives aus Dingen macht.

Verwenden wir Maybeas Applicativeund listen as auf Traversable. Zuerst brauchen wir die Transformationsfunktion:

half x = if even x then Just (x `div` 2) else Nothing

Wenn also eine Zahl gerade ist, bekommen wir die Hälfte davon (innerhalb von a Just), sonst bekommen wir Nothing. Wenn alles "gut" läuft, sieht es so aus:

traverse half [2,4..10]
--Just [1,2,3,4,5]

Aber...

traverse half [1..10]
-- Nothing

Der Grund ist, dass die <*>Funktion verwendet wird, um das Ergebnis zu erstellen, und wenn eines der Argumente ist Nothing, kehren wir Nothingzurück.

Ein anderes Beispiel:

rep x = replicate x x

Diese Funktion generiert eine Längenliste xmit dem Inhalt x, zB rep 3= [3,3,3]. Was ist das Ergebnis von traverse rep [1..3]?

Wir bekommen die Teilergebnisse [1], [2,2]und [3,3,3]unter Verwendung rep. Nun ist die Semantik von Listen Applicativeswird „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:

traverse rep [1..3]
--[[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3]]
Landei
quelle
1
Ihr Endergebnis erinnert mich daran .
Hugomg
3
@missingno: Ja, sie haben verpasstfac n = length $ traverse rep [1..n]
Landei
1
Eigentlich ist es dort unter "Listencodierungsprogrammierer" (aber unter Verwendung von Listenverständnissen). Diese Website ist umfassend :)
Hugomg
1
@missingno: Hm, es ist nicht genau das gleiche ... beide verlassen sich auf das kartesische Produktverhalten der Listenmonade, aber die Site verwendet jeweils nur zwei, also ist es eher so, liftA2 (,)als ob die allgemeinere Form verwendet wird traverse.
CA McCann
41

Ich denke, es ist am einfachsten zu verstehen sequenceA, traversewie folgt definiert werden kann.

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse f = sequenceA . fmap f

sequenceA sequenziert die Elemente einer Struktur von links nach rechts und gibt eine Struktur mit derselben Form zurück, die die Ergebnisse enthält.

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
sequenceA = traverse id

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 traverseeine Struktur und wenden Sie fan, 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 wird traverse_.

traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()

Sie sehen also, dass der Hauptunterschied zwischen Foldableund darin Traversablebesteht, 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 IOals Anwendung:

λ> import Data.Traversable
λ> let qs = ["name", "quest", "favorite color"]
λ> traverse (\thing -> putStrLn ("What is your " ++ thing ++ "?") *> getLine) qs
What is your name?
Sir Lancelot
What is your quest?
to seek the holy grail
What is your favorite color?
blue
["Sir Lancelot","to seek the holy grail","blue"]

Während dieses Beispiel eher nicht aufregend ist, werden die Dinge interessanter, wenn traversees für andere Arten von Behältern oder für andere Anwendungen verwendet wird.

Hammar
quelle
Traverse ist also einfach eine allgemeinere Form von mapM? In der Tat ist sequenceA . fmapfür Listen gleichbedeutend mit sequence . mapnicht wahr?
Raskell
Was meinst du mit "Sequenzieren von Nebenwirkungen"? Was ist "Nebenwirkung" in Ihrer Antwort? Ich dachte nur, dass Nebenwirkungen nur in Monaden möglich sind. Grüße.
Marek
1
@Marek "Ich dachte nur, dass Nebenwirkungen nur in Monaden möglich sind" - Die Verbindung ist viel lockerer als das: (1) Der IO Typ kann verwendet werden, um Nebenwirkungen auszudrücken; (2) ist IOzufä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 .
Duplode
(Übrigens, @hammar, ich habe mir erlaubt, "Nebenwirkung" in dieser Antwort aus den im obigen Kommentar genannten Gründen in "Wirkung" zu ändern.)
Duplode
17

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 Sie fmapdiese 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 der IOMonade).

Die Unterschrift von traverseist:

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)

Mit traversekönnen Sie Effekte ausführen. Daher sieht Ihr Code zum Zuordnen von Benutzer-IDs zu Benutzernamen folgendermaßen aus:

mapUserIDsToUsernames :: (Num -> IO String) -> [Num] -> IO [String]
mapUserIDsToUsernames fn ids = traverse fn ids

Es gibt auch eine Funktion namens mapM:

mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)

Jede Verwendung von mapMkann durch ersetzt werden traverse, aber nicht umgekehrt. mapMfunktioniert 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_und mapM_Versionen dieser Funktionen, die beide den Rückgabewert der Funktion ignoriert und sind etwas schneller.

Kai Sellgren
quelle
7

traverse ist die Schleife. Die Implementierung hängt von der zu durchlaufenden Datenstruktur ab. Das könnte eine Liste, Baum, sein Maybe, 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 TraversableTypklasse könnten Sie Ihre Algorithmen wahrscheinlich unabhängiger und vielseitiger schreiben. Aber meiner Erfahrung nach Traversablewird 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.

Comonad
quelle