Haskell - Pattern Matching und Rekursion

Question

Ich bin sowohl neu in Haskell als auch in der Programmierung. Meine Frage bezieht sich auf Binding in gemusterten, rekursiven Funktionen. Angenommen, ich habe eine Funktion, die überprüft, ob eine gegebene Liste (x:xs) eine Teilliste einer anderen Liste (y:ys) ist. Mein erster Gedanke, basierend auf den Beispielen in meinem Lehrbuch, war:

sublist [] ys = True
sublist xs [] = False
sublist (x:xs) (y:ys)
   | x == y = sublist xs ys
   | x /= y = sublist (x:xs) ys

Dies funktioniert mit Testdaten, z.B.,

sublist [1, 2, 3] [1, 2, 4, 1, 2, 3]

wo ich erwartet hatte, dass es scheitern würde. Ich erwarte, dass es scheitern wird, da

sublist [1, 2, 3] [1, 2, 4, 1, 2, 3]
   = sublist [2, 3] [2, 4, 1, 2, 3]
   = sublist [3] [4, 1, 2, 3]

an diesem Punkt, dachte ich, [3] = 3:[] wird mit (x:xs) in sublist abgeglichen, und [4, 1, 2, 3] wird mit (y:ys) in sublist abgeglichen. Wie funktioniert dann sublist?

Bearbeiten: Danke an alle hier, ich glaube, ich habe mein Problem gelöst. Wie festgestellt, wollte ich (subbewusst) dass sublist für mich zurückverfolgt. Unter Verwendung der letzten Antwort (BMeph) als Leitfaden habe ich mich entschieden, das Problem anders anzugehen, um das "Binding-Problem" zu lösen, d.h. das "Backtracking-Problem".

subseq :: (Eq a) => [a] -> [a] -> Bool
subseq [] _ = True
subseq _ [] = False
subseq (x:xs) (y:ys) =

-- subseq' entscheidet, ob die Liste, die an (x:xs) gebunden ist = M, ein Präfix der Liste
-- ist, die an L = (y:ys) gebunden ist; es rekursiert durch L und gibt einen Bool-Wert zurück. subseq
-- rekursiert durch M und L und gibt eine Disjunktion von Bool-Werten zurück.
-- Jeder rekursive Aufruf von subseq übergibt M und ys an subseq', der
-- entscheidet, ob M ein Präfix der **aktuelle Liste gebunden an ys** ist.

   let subseq' :: (Eq a) => [a] -> [a] -> Bool
       subseq' [] _ = True
       subseq' _ [] = False
       subseq' (x:xs) (y:ys) = (x == y) && subseq' xs ys
          in subseq' (x:xs) (y:ys) || subseq (x:xs) ys

Answer 1

Es funktioniert, weil:

• [3] wird als x:xs als 3:[] gematcht,
• [4, 1, 2, 3] wird als y:ys als 4:[1,2,3] gematcht
• 3/=4 also wird sublist (x:xs) ys ausgewertet, was schlussendlich True ergibt

spur:

sublist [1, 2, 3] [1, 2, 4, 1, 2, 3]
   = sublist [2, 3] [2, 4, 1, 2, 3]
   = sublist [3] [4, 1, 2, 3]
   = sublist [3] [1, 2, 3]
   = sublist [3] [2, 3]
   = sublist [3] [3]
   = sublist [] [] = True

Answer 2

  sublist [1, 2, 3] [1, 2, 4, 1, 2, 3]
= sublist [2, 3] [2, 4, 1, 2, 3]
= sublist [3] [4, 1, 2, 3]
= sublist [3] [4, 1, 2, 3]
= sublist (3:[]) (4:[1,2,3])     -- Da 3 /= 4 ist, nehmen wir sublist (x:xs) ys
= sublist (3:[]) [1,2,3]
= sublist (3:[]) (1:[2,3])
= sublist (3:[]) [2,3]
= sublist (3:[]) (2:[3])
= sublist (3:[]) [3]
= sublist [] []
= wahr

sublist überprüft, ob die Köpfe der Listen gleich sind. Wenn ja, entfernt es sie und fährt fort (sublist xs ys). Wenn nicht, wird der Kopf der zweiten Liste entfernt (sublist (x:xs) ys). Auf diese Weise "findet" es die folgende Zuordnung:

 1 2 3
 | | |
 | | \-----\
 | |       |
 1 2 4 1 2 3

Anders ausgedrückt, um sublist [1,2,3] ys für eine Liste ys zu überprüfen, werden Elemente aus ys entfernt, solange sie nicht 1 sind. Dann werden Elemente entfernt, solange sie nicht 2 sind. Dann werden Elemente entfernt, solange sie nicht 3 sind. Wenn [1,2,3] erschöpft ist, gibt es True zurück; wenn ys erschöpft ist, gibt es False zurück.

Answer 3

Debug.Trace ist dein Freund. Mit sublist instrumentiert als

sublist [] ys = trace ("A: [] "           ++ show ys) True
sublist xs [] = trace ("B: " ++ (show xs) ++ " []")   False
sublist (x:xs) (y:ys)
   | x == y = trace (info "C" "==")
              sublist xs ys
   | x /= y = trace (info "D" "/=")
              sublist (x:xs) ys
   where info tag op =
           tag ++ ": " ++ (show x) ++ " " ++ op ++ " " ++ (show y) ++
           "; xs=" ++ (show xs) ++ ", ys=" ++ show ys

du siehst, was passiert, nämlich dass es wiederholt den Anfang der zweiten Liste verwirft, bis es eine Übereinstimmung findet:

\*Main> sublist \[1, 2, 3\] \[1, 2, 4, 1, 2, 3\]
C: 1 == 1; xs=\[2,3\], ys=\[2,4,1,2,3\]
C: 2 == 2; xs=\[3\], ys=\[4,1,2,3\]
D: 3 /= 4; xs=\[\], ys=\[1,2,3\]
D: 3 /= 1; xs=\[\], ys=\[2,3\]
D: 3 /= 2; xs=\[\], ys=\[3\]
C: 3 == 3; xs=\[\], ys=\[\]
A: \[\] \[\]
True

Ein weiteres Tool, das Ihnen helfen wird, sublist korrekt zu implementieren, ist Test.QuickCheck, eine Bibliothek, die automatisch Testdaten erstellt zur Überprüfung der von Ihnen spezifizierten Eigenschaften.

Zum Beispiel, sagen Sie wollen, dass sublist xs und ys als Mengen betrachtet und bestimmt, ob ersteres eine Teilmenge von letzterem ist. Wir können Data.Set verwenden, um diese Eigenschaft zu spezifizieren:

prop_subsetOf xs ys =
  sublist xs ys == fromList xs `isSubsetOf` fromList ys
  where types = (xs :: [Int], ys :: [Int])

Dies besagt, dass sublist äquivalent zur Definition auf der rechten Seite sein sollte. Das prop_ Präfix ist eine beliebte Konvention zur Benennung von Testeigenschaften, die mit QuickCheck verwendet werden sollen.

Bei der Ausführung wird auch ein Fehlerfall identifiziert:

\*Main> quickCheck prop\_subsetOf 
\*\*\* Failed! Falsifiable (after 6 tests):                  
\[0,0\]
\[0\]

Answer 4

Ich denke, wo Sie vielleicht missverstehen, ist, dass Sie (als Sie die Funktion zuerst geschrieben haben) davon ausgegangen sind, dass in Ihrer Überprüfung x /= y = sublist (x:xs) ys Sie (unterbewusst?) angenommen haben, dass die Funktion backtracken und Ihre Funktion mit dem Schwanz der originalen zweiten Liste noch einmal durchlaufen würde, nicht mit dem Schwanz des jeweiligen Stücks der Liste, das Sie verwenden, wenn es nicht übereinstimmt.

Ein schönes (und beunruhigendes) Ding an Haskell ist einfach, wie absurd leistungsstark es ist.

Als Beispiel hier, wie es aussehen sollte, was Sie wollten:

sublist   []     ys   = True
sublist   xs     []   = False
sublist (x:xs) (y:ys) |   x /= y  = False
                      | otherwise = sublist xs ys || sublist (x:xs) ys

Das wird für alle Teile der ersten Liste überprüfen. Die "offizielle" Definition für die Funktion (suchen Sie "isInfixOf" in Ihrer Dokumentation) hat ein paar zusätzliche Funktionen, die im Grunde dasselbe bedeuten.

Hier ist eine andere Möglichkeit, es zu schreiben, die für mich mehr "erklärend" aussieht:

sublist [] ys = True
sublist xs [] = False
sublist xs ys =  (xs == take (length xs) ys) || sublist xs (tail ys)

Answer 5

YuppieNetworking und sdcwc haben bereits erklärt, wie das Matching funktioniert. Also sucht dein sublist nach einer Teilfolge im selben Sinn wie eine Teilfolge (nicht unbedingt die gleichen Elemente hintereinander, es kann alles dazwischen geben).

Ich möchte darauf hinweisen, dass Sie oft eine explizite Rekursion vermeiden können, um unnötige Elemente vorne aus der Liste zu entfernen, indem Sie dropWhile verwenden. Außerdem wollte ich ein Beispiel geben, wie man überprüft, ob zwei Listen die gleichen Präfixe haben (dies benötigen Sie, um zu überprüfen, ob die zweite Liste Elemente der ersten hintereinander enthält).

Das erste Beispiel ähnelt Ihrer Funktion, es erlaubt Elemente dazwischen, aber es verwendet dropWhile, um Elemente vor ys zu entfernen:

-- Test:
-- map ("foo" `subListOf`) ["kungfoo", "f-o-o!", "bar"] == [True,True,False]

[] `subListOf` _ = True
(x:xs) `subListOf` ys =
  let ys' = dropWhile (/= x) ys     -- finde das erste x in ys
  in  case ys' of
      (_:rest) -> xs `subListOf` rest
      [] -> False

Das zweite Beispiel sucht nach einer "dichten" Teilfolge:

-- Test:
-- map ("foo" `denseSubListOf`) ["kungfoo!", "-f-o-o-"] == [True,False]

[] `denseSubListOf` _ = True
_  `denseSubListOf` [] = False
xs `denseSubListOf` ys =
  let ps = zip xs ys in
  (length ps == length xs && all (uncurry (==)) ps) -- gleicher Präfix von xs und ys
  || xs `denseSubListOf` (tail ys)                  -- oder weiter suchen

Bitte beachten Sie, dass ich zur Überprüfung, ob die zweite Liste alle Elemente der ersten am Anfang enthält, die Elemente paarweise vergleiche (ich zippe sie zusammen, um dies zu tun).

Es ist einfacher zu erklären anhand eines Beispiels:

zip [1,2,3] [1,2,3,4,5]  -- ergibt [(1,1), (2,2), (3,3)], 4 und 5 werden abgeschnitten
uncurry (==)             -- eine Äquivalente von (\(a,b) -> a == b)
all                      -- ergibt True, wenn (uncurry (==)) für alle Paare True ist
length ps == length xs   -- dies soll sicherstellen, dass die rechte Liste lang genug ist