Ausnahme für nicht erschöpfende Muster

Question

Ich habe versucht, diese irgendwie ordentlich/prägnante quicksort Implementierung in GHCi ausgeführt wird:

:{ 
qs(x:xs) = qs left ++ [x] ++ qs right 
    where left = [ y | y <- xs, y < x] 
     right = [ y | y <- xs, y >= x ] 
:} 
print $ qs [1,123,42,90,24,12,3] 

Das Ergebnis ist:

*** Exception: <interactive>:(38,1)-(40,42): Non-exhaustive patterns in function qs 

Wie ist das Verhältnis der „where“ Aussage Um Vollständigkeit zu erreichen - und warum fehlen Fälle?

Answer 1

Die Fehlermeldung Non-exhaustive patterns in function qs bedeutet, dass die Musterübereinstimmungen für qs nicht den gesamten Bereich der Eingänge abdecken qs akzeptiert. In diesem Fall fehlt der Fall für die leere Liste.

:{ 
qs [] = [] 
qs (x:xs) = qs left ++ [x] ++ qs right 
    where left = [ y | y <- xs, y < x] 
     right = [ y | y <- xs, y >= x ] 
:} 

Answer 2

Wie Alec sagte, haben Sie vergessen, die leere Liste zu behandeln.

Um diese Art von Fehler in Zukunft zu vermeiden, empfehle ich dringend, Warnungen unter Verwendung -Wall zu aktivieren. Dadurch überprüft GHC, ob die Muster zur Kompilierungszeit (Definitionszeit) vollständig sind.

Prelude> :set -Wall 
Prelude> :{ 
Prelude| qs(x:xs) = qs left ++ [x] ++ qs right 
Prelude| where left = [ y | y <- xs, y < x] 
Prelude|   right = [ y | y <- xs, y >= x ] 
Prelude| :} 

<interactive>:12:1: warning: [-Wincomplete-patterns] 
    Pattern match(es) are non-exhaustive 
    In an equation for ‘qs’: Patterns not matched: [] 

Wie man sehen kann, weist sie darauf hin, dass [] nicht abgestimmt wurde.

Hier ist ein weiteres Beispiel, wo wir die leere Liste und die Listen beginnend mit x,y behandeln, aber wir vergessen zu handhaben Listen mit einem Element (Muster des Formulars [_]).

Prelude> :{ 
Prelude| f [] = 0 
Prelude| f (x:y:xs) = 0 
Prelude| :} 

<interactive>:18:1: warning: [-Wincomplete-patterns] 
    Pattern match(es) are non-exhaustive 
    In an equation for ‘f’: Patterns not matched: [_] 

Hinzufügen f [x] = 0 würde ausreichen. (Natürlich erhalten wir dann Warnungen für alle unbenutzten Variablen, die in diesen Mustern vorkommen.)