Ich weiß aus der Berechenbarkeitstheorie, dass es möglich ist, die Schnittmenge von zwei unendlichen Listen zu nehmen, aber ich kann keinen Weg finden, es in Haskell auszudrücken.
Die traditionelle Methode schlägt fehl, sobald die zweite Liste unendlich ist, weil Sie Ihre ganze Zeit damit verbringen, sie auf ein nicht übereinstimmendes Element in der ersten Liste zu prüfen.
Beispiel:
%Vor% Dies liefert niemals 1 , da es nie aufhört, ones für das Element 0 zu überprüfen.
Eine erfolgreiche Methode muss sicherstellen, dass jedes Element jeder Liste in endlicher Zeit besucht wird.
Wahrscheinlich wird dies dadurch geschehen, dass beide Listen durchlaufen werden und ungefähr die gleiche Zeit aufgewendet wird, um alle zuvor besuchten Elemente in jeder Liste gegeneinander zu überprüfen.
Wenn möglich, möchte ich auch eine Möglichkeit haben, Duplikate in den Listen zu ignorieren, wie es gelegentlich notwendig ist, aber das ist keine Voraussetzung.
Am Ende habe ich die folgende Implementierung verwendet; eine kleine Änderung der Antwort von David Fletcher:
%Vor%Dies kann mit nub erweitert werden, um Duplikate herauszufiltern:
%Vor% Von der Zeile isect xs = catMaybes . diagonal . map matches
(map matches) ys berechnet eine Liste von Vergleichslisten zwischen Elementen von xs und ys , wobei die Listenindizes die Indizes in ys bzw. xs angeben: dh (map matches) ys !! 3 !! 0 würde den Vergleich von darstellen ys !! 3 mit xs !! 0 , was Nothing wäre, wenn sich diese Werte unterscheiden. Wenn diese Werte identisch sind, wäre Just dieser Wert.
diagonals nimmt eine Liste von Listen und gibt eine Liste von Listen zurück, wobei die n-te Ausgabeliste jeweils ein Element aus den ersten n Listen enthält. Eine andere Möglichkeit, dies zu verstehen, ist, dass (diagonals . map matches) ys !! n Vergleiche zwischen Elementen enthält, deren Indizes in xs und ys zu n addieren.
diagonal ist einfach eine flache Version von diagonals ( diagonal = concat diagonals )
Daher ist (diagonal . map matches) ys eine Liste von Vergleichen zwischen Elementen von xs und ys , wobei die Elemente ungefähr nach der Summe der Indizes der Elemente von ys und xs verglichen werden; das bedeutet, dass frühe Elemente mit späteren Elementen verglichen werden, die die gleiche Priorität haben wie mittlere Elemente, die miteinander verglichen werden.
(catMaybes . diagonal . map matches) ys ist eine Liste von nur den Elementen, die sich in beiden Listen befinden, wobei die Elemente ungefähr nach der Summe der Indizes der beiden verglichenen Elemente sortiert sind.
Hinweis
(diagonal . map (catMaybes . matches)) ys funktioniert nicht : catMaybes . matches liefert nur, wenn eine Übereinstimmung gefunden wird, anstatt auch Nothing bei keiner Übereinstimmung zu liefern, also macht das Interleaving nichts, um die Arbeit zu verteilen.
Im Gegensatz dazu bedeutet in der gewählten Lösung das Interleaving von Nothing und Just Werte von diagonal , dass das Programm seine Aufmerksamkeit auf das "Suchen" nach mehreren verschiedenen Elementen aufteilt und nicht darauf wartet, dass einer erfolgreich ist. Wenn jedoch die Nothing -Werte vor dem Interleaving entfernt werden, kann das Programm zu viel Zeit damit verbringen, auf eine vergebliche Suche nach einem gegebenen Element zu warten.
Daher würden wir auf das gleiche Problem stoßen wie in der ursprünglichen Frage: während ein Element mit keinem Element in der anderen Liste übereinstimmt, wird das Programm hängen bleiben; während die gewählte Lösung nur hängt, während für keine Elemente in einer der beiden Listen Übereinstimmungen gefunden werden.
Verwendung der > Cartesian Product Operator des Universe-Pakets können wir dieses One-Liner schreiben:
%Vor%Probieren Sie es in ghci aus:
%Vor% Diese Implementierung erzeugt keine Duplikate, wenn die Eingabelisten keine haben; aber wenn sie es tun, kannst du deinen Lieblingsdup-Entferner entweder vor oder nach dem Aufruf von isect aktivieren. Mit nub könnten Sie beispielsweise
und heize dann deinen Computer ziemlich gut auf, da es niemals sicher sein kann, dass es irgendwo in dieser zweiten Liste kein 0 gibt, wenn es tief genug aussieht.
Dieser Ansatz ist wesentlich schneller als David Fletchers, produziert viel weniger Duplikate und produziert viel schneller neue Werte als Willem Van Onsem und geht nicht davon aus, dass die Listen nach Freestyle sortiert sind (ist aber auf solchen Listen wesentlich langsamer als Freestyle) ).
Eine Idee könnte sein, inkrementierende Grenzen zu verwenden . Lassen Sie uns zunächst das Problem ein wenig lockern: doppelte Werte sind erlaubt. In diesem Fall könnten Sie verwenden:
%Vor%Mit anderen Worten behaupten wir:
A · B = A <1> <1> <2> <2> <1> ∪ ...
mit A 1 ist eine Menge, die die ersten i Elemente von A enthält (ja, es gibt keine Reihenfolge in einer Menge, aber sagen wir mal Da ist irgendwie eine Bestellung). Wenn die Menge less -Elemente enthält, wird die vollständige Menge zurückgegeben.
Wenn c in A (im Index i ) und in B (im Index ) ist j ), c wird im Segment (nicht im Index) max (i, j) ausgegeben.
Dies erzeugt also immer eine unendliche Liste (mit einer unendlichen Anzahl von Duplikaten) unabhängig davon, ob die gegebenen Listen endlich sind oder nicht. Die einzige Ausnahme ist, wenn Sie es eine leere Liste geben, in diesem Fall wird es ewig dauern. Trotzdem haben wir hier sichergestellt, dass jedes Element in der Kreuzung mindestens einmal emittiert wird.
Das Ergebnis ist endlich (wenn die angegebenen Listen endlich sind)
Jetzt können wir unsere Definition verbessern. Zuerst machen wir eine erweiterte Version von take , takeFinite (lassen Sie uns zuerst eine direkte, aber nicht sehr effiziente Definition geben):
Nun können wir iterativ vertiefen, bis beide -Listen das Ende erreicht haben:
%Vor%Dies wird nun beendet, wenn beide Listen endlich sind, aber immer noch viele Duplikate ergeben. Es gibt definitiv Möglichkeiten, dieses Problem zu lösen (wird aktualisiert, wenn ich mehr Zeit habe).
Hier ist ein Weg. Für jedes x erstellen wir eine Liste von maybes welche hat
Just x nur wo x in ys angezeigt wurde. Dann verschachteln wir alle
diese Listen.
Vielleicht kann es mit einer faireren Verschachtelung verbessert werden - Im folgenden Beispiel ist es schon ziemlich langsam, weil (denke ich) es macht eine exponentielle Menge an Arbeit.
%Vor% Hier ist noch eine weitere Alternative, die Control.Monad.WeightedSearch
Wir definieren zuerst eine Kosten für das Graben innerhalb der Liste. Der Zugang zum Schwanz kostet 1 Einheit mehr. Dies gewährleistet eine faire Planung zwischen den beiden unendlichen Listen.
%Vor%Dann ignorieren wir einfach unendliche Listen.
%Vor% Noch besser mit MonadComprehensions on: