Ich versuche eine Funktion (unten beschrieben) zu implementieren, die zwei Listen (jede oder beide kann unendlich sein) und eine Liste von Tupeln aller möglichen Paare von Elementen zwischen den Listen
zurückgibt %Vor%(z. B. sollte die Ausgabe so sein, muss aber nicht genau so sein)
%Vor%Ich habe angefangen, es so zu implementieren:
%Vor%Ich wollte die Liste in eine Hilfsfunktion füttern, um die Listen zu erzeugen, aber die, die ich erstellt habe, kann nicht kompiliert werden und weiß nicht, wie man mit unendlichen Listen umgeht
Helferfunktion -
%Vor%Dies ist eine großartige Übung!
Wenn wir die Paare Ihrer Eingabe in einer unendlichen Tabelle aufstellen:
%Vor%Der Trick besteht darin, den Tisch in aufwärts diagonalen Streifen zu durchlaufen. Verfolge den Tisch mit deinen Augen. Die Streifen dieser Tabelle sind:
%Vor%Alle Streifen sind endlich, aber jedes Element der Tabelle ist in einem von ihnen. Wenn Sie sie also miteinander verketten, erscheint jedes Element an einer endlichen Position im verketteten Ergebnis.
Hier ist der Spielplan, den ich vorschlagen würde:
Implementieren Sie stripes :: [[a]] -> [[a]] , das die Liste der Streifen aus einem unendlichen Array wie oben extrahiert (beginnen Sie mit der Annahme, dass alle Listen unendlich sind, dh machen Sie sich keine Sorgen um die [] -Fälle; Arbeiten Sie an Listen, die endlich sein können.)
Verwenden Sie stripes , implementieren Sie diagonal :: [[a]] -> [a] , das alle Streifen verkettet (dies ist ein Einzeiler).
Implementieren Sie schließlich Ihre Funktion, indem Sie diagonal einer bestimmten 2D-Tabelle [[(a,b)]] anwenden. Dies ist die Tabelle, mit der ich diese Antwort begonnen habe (und die unter anderem mithilfe eines geschachtelten Listenverständnisses erstellt werden kann).
Anmerkungen:
Der Name zip ist irreführend. Das ist mehr wie ein kartesisches Produkt.
Sie wissen, dass Sie Muster in Mustern zuordnen können, richtig? I.e. wenn f :: [[a]] -> something
Gibt Ihnen x als erstes Element der ersten Zeile, xs ist der Rest der ersten Zeile und xss ist der Rest der Tabelle.
Obwohl dies eine großartige Übung ist, um Listen und Haskell im Allgemeinen zu verstehen, ist es auch eine großartige Übung, um zu verstehen, worum es in der Klasse Applicative geht. Insbesondere die [] -Instanz für Applicative . Ihr zipInf , das Sie wollen, ist genau liftA2 (,)
Wir müssen nur sicherstellen, dass [] ein Applicative ist.
Also ist es ein Applicative . Es macht es vielleicht einfacher zu verstehen, wenn wir unseren Typ ein wenig mit Anmerkungen versehen.
Ja, das ist der gleiche Typ.
%Vor%Sieht so aus, als ob es funktioniert! Sie mussten also nichts tun, um dies zu schreiben, und es ist wohl verständlicher als eine rekursive Definition. Außerdem mussten Sie sich nicht über Randfälle Gedanken machen, wie Sie es bei einer eigenen Lösung tun würden.
Sie können es auch etwas idiomatisch schreiben mit <$> (oder fmap ) und <*> .
Oder Sie könnten die volle Leistung von Monad nutzen (was in diesem Fall ziemlich unnötig ist):
Wenn Sie sich fragen, wie Sie eine andere Semantik von Applicative für [] erhalten könnten, gibt es mindestens eine weitere List-Instanz für Applicative : ZipList
Diese Instanz stellt eine Zipping-Stil-Semantik für ihre Applicative -Instanz bereit.
Beides sind gute Einführungen in die Klasse Applicative , weil sie leicht verfügbar und ziemlich intuitiv sind, Fehler verhindern und zeigen, dass es Fälle gibt, in denen ein einzelner Typ mehr als eine Instanz von a hat Typklasse.
Hier ist die Hilfsfunktion, die Sie gepostet haben:
%Vor%Und hier sind die Syntaxfehler, die es enthält:
Sie haben einen Pfeil in der Anmerkung zum Typ weggelassen; es sollte
sein %Vor%Sie müssen nicht-triviale Muster in Parens einschließen, also sollte die zweite Gleichung beginnen
%Vor% oneList benötigt zwei Argumente, bevor Sie eine Liste zurückgeben, aber in der rechten Spalte der zweiten Gleichung versuchen Sie, sie als Liste zu verwenden, ohne ihr irgendwelche Argumente zu geben
(Übrigens hilft es uns normalerweise, wenn Sie die Fehlermeldungen posten, anstatt nur zu sagen, dass es nicht kompiliert. Vergleichen Sie die Fehler, die ich oben auf die Fehlermeldungen des Compilers hingewiesen habe.)
Aber wie Sie bemerken, ist Ihr Algorithmus falsch.
Ich spüre, dass dies Hausaufgaben sind, also werde ich Ihnen nur einen Hinweis geben.
zipInf sollte
thread und expand sind zwei Hilfsfunktionen, die ich Ihnen mit Typensignaturen
expand ist ziemlich einfach. thread ist, wo Sie vorsichtig sein müssen, um Elemente in der richtigen Reihenfolge einzubeziehen (daher können Sie nicht einfach thread zs = concat zs sagen, obwohl der Typ richtig ist).
Sie müssen oneList auf xs und ys anwenden.
Unbegrenzte Listen funktionieren automatisch, da Haskell faul ist.
WICHTIG: Siehe untenstehenden Kommentar von Will Ness.
Ihre Frage impliziert, dass die Reihenfolge keine Rolle spielt. (Aber da die Listen unendlich sein können, ist die Reihenfolge vielleicht wichtiger, als Sie denken!) Wenn die Reihenfolge keine Rolle spielt und Sie Listen-Comprehensions gefunden haben, ist das ein Ansatz, den Sie verwenden könnten . Hier ist ein Beispiel.
%Vor% Beachten Sie, dass alle Tupel, die 'a' enthalten, zuerst gedruckt werden, dann die mit 'b' und so weiter. Wieso spielt das eine Rolle? Nun, nehmen wir an, die Liste ist unendlich. Eine Abfrage wie diese wird sofort zurückgegeben:
Aber einer wie dieser wird eine LANGE Zeit brauchen:
%Vor%Wenn es auf die Reihenfolge ankommt oder Sie nicht auf Listenkompressen gestoßen sind oder diese nicht verwenden möchten, ist luquis Ansatz wahrscheinlich das, wonach Sie suchen.