ZipList kommt mit einem Functor und einer Applicative-Instanz ( Control.Applicative ) aber warum nicht Alternative?
Bool kann auf zwei Arten ein Monoid sein) und deshalb sollte auch keiner die Instanz Ich suchte nach "instance Alternative ZipList" (mit den Anführungszeichen, um den Code zuerst zu finden) und fand nur die Bibliothek, einige Tutorials, Vorlesungsnotizen, aber keine tatsächliche Instanz.
Matt Fenwick sagte, dass ZipList A nur ein Monoid ist, wenn A ist. Siehe hier . Listen sind jedoch Monoids, unabhängig vom Elementtyp.
Diese andere Antwort von AndrewC auf die gleiche Frage diskutiert, wie eine alternative Instanz aussehen könnte. Er sagt
Es gibt zwei sinnvolle Optionen für Zip
[1,3,4] <|> Zip [10,20,30,40]:
Zip [1,3,4], weil es zuerst ist - konsistent mit MaybeZip [10,20,30,40], weil es am längsten ist - konsistent mitZip []wird verworfen
wobei Zip grundsätzlich ZipList ist.
Ich denke, die Antwort sollte Zip [1,3,4,40] sein. Lassen Sie uns eine Instanz sehen:
Die einzige Zip a , die wir erzeugen können, ohne das Typargument a zu kennen, ist Zip [] :: Zip a , also gibt es wenig Auswahl für empty . Wenn die leere Liste das neutrale Element des Monos ist, könnten wir versucht sein, die Listenverkettung zu verwenden. % Co_de% ist jedoch nicht go wegen (++) . Jedes Mal, wenn wir einen Eintrag der ersten Argumentliste verwenden, löschen wir einen der zweiten. Wir haben also eine Art Overlay: Die linke Argumentliste verbirgt den Anfang der rechten (oder die ganze).
Eine Intuition hinter ziplists sind Prozesse: Ein endlicher oder unendlicher Ergebnisstrom. Beim Zippen kombinieren wir Streams, die von der Applicative-Instanz reflektiert werden. Wenn das Ende der Liste erreicht ist, erzeugt der Stream keine weiteren Elemente. Hier kommt die Alternative-Instanz zum Einsatz: Wir können eine Ersetzung benennen, sobald der Standardprozess endet.
Zum Beispiel könnten wir drop 1 schreiben, um jedes Element der ziplist fmap Just foo <|> pure Nothing in ein foo einzufügen und danach mit Just fortzufahren. Die resultierende Ziplist ist unendlich und wird auf einen Standardwert zurückgesetzt, nachdem alle (echten) Werte aufgebraucht wurden. Dies könnte natürlich von Hand gemacht werden, indem eine unendliche Liste innerhalb des Konstruktors Nothing angehängt wird. Das Obige ist jedoch eleganter und setzt keine Kenntnis der Konstrukteure voraus, was zu einer höheren Wiederverwendbarkeit des Codes führt.
Wir brauchen keine Annahme für den Elementtyp (wie ein Monoid selbst). Gleichzeitig ist die Definition nicht trivial (wie Zip wäre). Es verwendet die Listenstruktur durch Mustervergleich für das erste Argument.
Die obige Definition von (<|>) = const ist assoziativ und die leere Liste ist wirklich das leere Element. Wir haben
Damit sind alle Gesetze erfüllt, die Sie fordern können (was nicht für die Listenverkettung gilt).
Diese Instanz ist konsistent mit der für Maybe: Choice ist nach links vorgespannt, aber wenn das linke Argument keinen Wert erzeugen kann, übernimmt das richtige Argument. Die Funktionen
%Vor% sind Morphismen von Alternativen (also <|> und psi x <|> psi y = psi (x <|> y) ).
Bearbeiten: Für die psi x <*> psi y = psi (x <*> y) / some Methoden würde ich raten
Interessant. Ein nicht ganz unzusammenhängender Gedanke: ZipLists können als gewöhnliche Listen mit Elementen angesehen werden, die durch ihren (steigenden) Positionsindex in der Liste markiert sind. Die Zipping-Anwendung verbindet zwei Listen, indem sie gleich indexierte Elemente miteinander verbindet.
Stellen Sie sich Listen mit Elementen vor, die durch (nicht abnehmende) Ord Werte gekennzeichnet sind. Zippery -Anwendung würde Elemente mit gleichen Tags paaren und alle Nichtübereinstimmungen wegwerfen ( es hat seine Verwendung ); zippery alternativer könnte die Reihenfolge erhaltende linksorientierte Vereinigung für Tag-Werte durchführen (Alternative in regulären Listen ist auch eine Art Union).
Dies stimmt voll und ganz mit dem überein, was Sie für indizierte Listen (auch bekannt als ZipLists) vorschlagen.
Also ja, es macht Sinn.
Eine Interpretation einer Werteliste ist Unbestimmtheit, die mit der Monadeninstanz für Listen konsistent ist, aber ZipLists können als synchrone Ströme von Werten interpretiert werden, die nacheinander kombiniert werden.
Bei dieser Stream-Interpretation denken Sie nicht an die gesamte Liste, also ist die Wahl des längsten Streams eindeutig Betrug, und die korrekte Interpretation des Failover von der ersten ZipList zur zweiten ZipList in der Definition <|> würde sei dies während der ersten Runde, wie du in deiner Instanz sagst.
Zippen von zwei Listen zusammen macht das nicht einfach wegen der Typ-Signatur, aber es ist die korrekte Interpretation von <|> .
Wenn Sie zwei Listen zusammenfügen, ist das Ergebnis das Minimum der zwei Längen. Dies liegt daran, dass dies die längste mögliche Liste ist, die die Typ-Signatur erfüllt, ohne ⊥ zu verwenden. Es ist ein Fehler, dies als die kürzeste der beiden Längen zu wählen - es ist die längste mögliche.
Ähnlich sollte <|> die längste mögliche Liste erzeugen und sollte die linke Liste bevorzugen. Offensichtlich sollte es die gesamte linke Liste nehmen und die rechte Liste aufnehmen, wo die linke gelassen wurde, um Synchronisation / Zippiness zu erhalten.
Ihre Instanz ist in Ordnung, aber sie tut etwas, was ZipList nicht tut, wenn (a) die längste Liste anstrebt und (b) Elemente zwischen Quellenlisten mischen.
Das Zippen als Operation endet mit der kürzesten Liste.
Deshalb habe ich in meiner Antwort gefolgert:
Daher ist die einzige sinnvolle alternative Instanz:
%Vor% Dies steht im Einklang mit den alternativen Instanzen für Maybe und Parser, die sagen, dass Sie a ausführen sollten, wenn es nicht fehlschlägt und wenn b , falls dies der Fall ist. Sie können sagen, dass eine kürzere Liste weniger erfolgreich ist als eine längere, aber ich glaube nicht, dass Sie sagen können, dass eine nicht leere Liste ein vollständiger Fehler ist.
empty = Zip [] wird ausgewählt, da es im Elementtyp der Liste polymorph sein muss und die einzige solche Liste []
Aus Gründen der Ausgewogenheit glaube ich nicht, dass dein Fall schrecklich ist, ich denke, das ist sauberer, aber hey ho, rolle dein eigenes, wie du es brauchst!
Meine leitende Intuition für Alternative kommt von Parsern, die nahelegen, dass, wenn ein Zweig Ihrer Alternative irgendwie fehlschlägt, er ausgelöscht werden sollte, was zu einem Longest -style Alternative führt, das wahrscheinlich nicht besonders nützlich ist. Dies wäre unvoreingenommen (im Gegensatz zu Parsern), scheitert aber an unendlichen Listen.
Andererseits müssen sie nur, wie Sie vorschlagen, eine Monoid bilden. Dein Bild ist so voreingenommen, dass ZipList normalerweise nicht verkörpert - du könntest die reflektierte Version deiner Alternative -Instanz genauso einfach erstellen. Wie Sie bereits gesagt haben, ist dies auch die Konvention mit Maybe , aber ich bin mir nicht sicher, ob es einen Grund für ZipList gibt, dieser Konvention zu folgen.
Es gibt keine vernünftige some oder many Ich glaube nicht, obwohl nur wenige Alternative s diese haben - vielleicht wären sie besser in eine Unterklasse von Alternative isoliert worden.
Ehrlich gesagt, denke ich nicht, dass Ihr Vorschlag ein schlechter Fall ist, aber ich habe kein Vertrauen darauf, dass es die "alternative" Instanz ist, die durch ein ZipList impliziert wird. Vielleicht wäre es am besten zu sehen, wo sonst diese Art von "Extension" -Instanz (Bäume?) Gelten könnte, und sie als Bibliothek zu schreiben.
Es gibt tatsächlich eine sinnvolle Alternative Instanz für ZipList. Es kommt aus ein Papier bei freien Near-Semirings (für die MonadPlus und Alternative Beispiele sind):
Dies ist eine performantere Version des ursprünglichen Codes dafür, der
war %Vor%Tags und Links haskell list applicative typeclass