Haskell: Überprüfen Sie, ob die erste Liste ein Präfix der zweiten ist

Question

Ich versuche, ein Programm zu schreiben, das überprüft, ob die erste Liste ein Präfix der zweiten Liste ist. zum Beispiel ist [5,6] das Präfix von [1,5,6,7]. Hier ist mein Arbeitscode, aber im Grunde habe ich keine Idee, wie es geht.

prefix [Int] -> [Int] -> Bool 
prefix [] [] = [] 
prefix y (x:xs) 
| x == y = prefix y xs 
| otherwise = 0 

Hilfe bitte?

Answer 1

Ihr Code macht nicht viel Sinn machen, wenn wir uns die Typen aussehen:

prefix [Int] -> [Int] -> Bool 
prefix [] [] = [] 
prefix y (x:xs) 
| x == y = prefix y xs 
| otherwise = 0 

Da die beiden Argumente sind Listen ([Int]), dies bedeutet also, dass y ist ein [Int], x ist ein Int und xs ist ein [Int]. Aber dann vergleichen Sie x == y, Sie können eine Liste nicht mit einem Element vergleichen. (==) ist definiert als (==) :: Eq a => a -> a -> Bool.

Es gibt auch andere Probleme hier: Sie erhalten eine Liste in der ersten Klausel zurück, aber der Rückgabetyp ist ein Bool und später zurückkehren Sie eine 0 (wieder, es sollte ein Bool sein).

Wenn wir eine Funktion definieren, müssen wir zuerst ein bestimmtes Modell dafür definieren. Wann ist eine Liste l1 ein Präfix einer Liste l2? Bei l1 ist eine leere Liste, dann l1 ist immer ein Präfix, unabhängig von dem Wert der zweiten Liste, so:

prefix [] _ = True 

Bei l1 ist eine Liste (dh (x:xs)), dann ist es nicht ein Präfix in zwei Fällen: (1) in Fall l2 ist eine leere Liste; und (2), falls der erste Punkt von l2 (y in (y:ys)) nicht gleich x, so:

prefix _ [] = False 
prefix (x:xs) (y:ys) | x /= y = False 
        | otherwise = ... 

Nun ist die Frage, was mit prefix (x:xs) (y:ys) bei x == y zu tun ist.In diesem Fall Rekursion wir auf der beide Liste, so das Ergebnis des prefix (x:xs) (y:ys) == prefix xs ys (nur bei x == y), so:

     | otherwise = prefix xs ys 

Oder jetzt in voller Länge:

prefix :: [Int] -> [Int] -> Bool 
prefix [] _ = True 
prefix _ [] = False 
prefix (x:xs) (y:ys) | x /= y = False 
        | otherwise = prefix xs ys 

können wir weiter verallgemeinern den Ausdruck Eq a => [a] -> [a] -> Bool derart, dass sie mit jeder Typ a arbeitet, die eine Eq Instanz (so gibt es eine Instanz definiert (==) über a):

prefix :: Eq a => [a] -> [a] -> Bool 
prefix [] _ = True 
prefix _ [] = False 
prefix (x:xs) (y:ys) | x /= y = False 
        | otherwise = prefix xs ys 

Wir können auch die Bedingungen tauschen, da in der Regel positive Logik einfacher ist, als negative Logik zu verstehen:

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

jetzt können wir weiterhin die Wachen entfernen, und verwenden Sie ein (&&) :: Bool -> Bool -> Bool statt:

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