Ich bin neu in Haskell und Programmierung. Meine Frage zu Bindung in pattern-matched, rekursive Funktionen. Angenommen, ich habe eine Funktion, die überprüft, ob eine gegebene Liste (x: xs) eine Unterliste einer anderen Liste ist (y: ys). Mein erster Gedanke, den Beispielen in meinem Lehrbuch folgend, war:
%Vor%Dies funktioniert bei Testdaten, z. B.
%Vor%wo ich erwartet habe, dass es scheitert. Ich erwarte, dass es scheitert, seit
%Vor%An diesem Punkt dachte ich, [3] = 3: [] wird mit (x: xs) in der Unterliste verglichen und [4, 1, 2, 3] wird mit (y: ys) in Übereinstimmung gebracht Unterliste. Wie funktioniert die Unterliste dann?
Bearbeiten: Danke an alle hier, ich denke, ich habe mein Problem gelöst. Wie bereits erwähnt, wollte ich ("unterbewusst") eine Unterliste für mich zurückverfolgen. Unter Verwendung der letzten als Leitfaden veröffentlichten Antwort ( BMeph ) entschied ich mich, das Problem anders anzugehen, um das "Bindeproblem", d. H. Das "Zurückverfolgen" -Problem zu lösen.
%Vor%Es funktioniert, weil:
[3] wird als x:xs als 3:[] , [4, 1, 2, 3] entspricht y:ys als 4:[1,2,3]
3/=4 so sublist (x:xs) ys wird ausgewertet, was letztendlich True Ablaufverfolgung:
%Vor% Unterliste prüft, ob die Köpfe der Listen gleich sind. Wenn ja, dann entfernt es sie und geht weiter ( sublist xs ys ). Wenn nein, entfernt es head von der zweiten Liste ( sublist (x:xs) ys ). So "findet" es die folgende Assoziation:
Mit anderen Worten, um sublist [1,2,3] ys für eine Liste ys zu überprüfen, werden Elemente aus ys solange nicht dargestellt. Dann werden die Elemente solange angezeigt, wie sie nicht 2 sind Solange sie nicht 3 sind. Wenn [1,2,3] erschöpft ist, meldet sie True; Wenn ys erschöpft ist, wird False gemeldet.
Debug.Trace ist dein Freund. Mit sublist instrumentiert als
Sie sehen, was passiert, nämlich dass es wiederholt den Kopf der zweiten Liste wegwirft, bis es eine Übereinstimmung findet:
%Vor% Ein weiteres Tool, mit dem Sie sublist richtig implementieren können, ist Test.QuickCheck , eine Bibliothek, die automatisch Testdaten erstellt Zur Überprüfung der von Ihnen angegebenen Eigenschaften.
Angenommen, Sie möchten sublist als xs und ys als Mengen behandeln und bestimmen, ob es sich bei ersterer um eine Teilmenge der letzteren handelt. Wir können Data.Set verwenden um diese Eigenschaft anzugeben:
Dies besagt, dass sublist der Definition auf der rechten Seite entsprechen sollte. Das Präfix prop_ ist eine gängige Konvention zur Benennung von Testeigenschaften, die mit QuickCheck verwendet werden.
Bei der Ausführung wird auch ein Fehlerfall identifiziert:
%Vor% Ich denke, wo Sie vielleicht Missverständnis haben, ist das (als Sie die Funktion zum ersten Mal geschrieben haben), dass Sie in Ihrer Kontrolle x /= y = sublist (x:xs) ys angenommen haben, dass die Funktion zurückverfolgt wäre und wiederhole deine Funktion mit dem Ende der ursprünglichen zweiten Liste, nicht mit dem Ende des Stücks der Liste, das du verwendest, wenn es nicht übereinstimmt.
Eine nette (und beunruhigende) Sache über Haskell ist, wie lächerlich mächtig ist.
Für ein Beispiel, hier ist, was Sie gesucht haben sollten:
%Vor%überprüft alle Teile der ersten Liste. Die "offizielle" Definition für die Funktion (siehe " isInfixOf " in Ihrer Dokumentation hat ein paar zusätzliche Funktionen, die im Grunde dasselbe bedeuten.
Hier ist ein anderer Weg, es zu schreiben, der für meine Augen "erklärender" aussieht:
%Vor% YuppieNetworking und sdcwc haben bereits erklärt, wie das Matching funktioniert. So sucht Ihre sublist nach einer Unterliste im selben Sinne wie Unterfolge (nicht notwendigerweise die gleichen Elemente in einer Zeile, dort kann alles dazwischen sein).
Ich möchte darauf hinweisen, dass Sie häufig eine explizite Rekursion vermeiden können, um unnötige Elemente mit dropWhile aus dem Anfang der Liste zu entfernen. Außerdem möchte ich ein Beispiel geben, wie überprüft werden kann, ob zwei Listen dieselben Präfixe haben (Sie müssen dies prüfen, um zu prüfen, ob die zweite Liste Elemente der ersten Zeile in einer Zeile enthält).
Das erste Beispiel ähnelt Ihrer Funktion, es erlaubt Elemente dazwischen, aber es verwendet dropWhile , um Elemente vor ys zu entfernen:
Das zweite Beispiel sucht nach einer "dichten" Unterliste:
%Vor%Bitte beachten Sie, dass, um zu überprüfen, dass die zweite Liste die erste am Anfang enthält, ich Elemente paarweise paarweise vergleiche (ich zip sie zusammen, um es zu machen).
Es ist einfacher, dies anhand eines Beispiels zu erklären:
%Vor%