Warum beschwert sich GHC über nicht erschöpfende Muster?

Question

Wenn ich den folgenden Code mit GHC kompilieren (mit der -Wall flag):

module Main where 

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show) 

insert :: (Ord a) => a -> Tree a -> Tree a 
insert x EmptyTree = Node x EmptyTree EmptyTree 
insert x (Node a left right) 
    | x == a = Node a left right 
    | x < a = Node a (insert x left) right 
    | x > a = Node a left (insert x right) 

main :: IO() 
main = do 
    let nums = [1..10]::[Int] 
    print . foldr insert EmptyTree $ nums 

GHC beklagt, dass Mustervergleich in insert nicht erschöpfend ist:

test.hs|6| 1: 
||  Warning: Pattern match(es) are non-exhaustive 
||    In an equation for `insert': Patterns not matched: _ (Node _ _ _) 

Warum diese Warnung GHC ist die Ausstellung? Es ist ziemlich offensichtlich, dass das Muster, über das sich GHC beklagt, in insert x (Node a left right) gehandhabt wird.

Answer 1

Riccardo ist richtig, GHC schließt nicht, dass Ihre Wachen möglicherweise nicht alle falsch sein können. Also akzeptiere bitte seine Antwort.

Ich werde abschweifen und über Codierungsstil sprechen.

Ihre Motivation für nicht otherwise Verwendung gewesen sein kann, dass es unansehnlich aussieht:

insert :: (Ord a) => a -> Tree a -> Tree a 
insert x EmptyTree = Node x EmptyTree EmptyTree 
insert x (Node a left right) 
    | x == a = Node a left right 
    | x < a  = Node a (insert x left) right 
    | otherwise = Node a left (insert x right) 

Blick auf diesen Code, muss ein Mensch Leser sich bestätigen, dass die endgültige Wache übernimmt genau die Fälle, in denen x > a.

Wir könnten statt es wie folgt schreiben:

insert :: (Ord a) => a -> Tree a -> Tree a 
insert x EmptyTree = Node x EmptyTree EmptyTree 
insert x (Node a left right) = case x `compare` a of 
    EQ -> Node a left right 
    LT -> Node a (insert x left) right 
    GT -> Node a left (insert x right) 

Der Ordering Typ zurück von compare hat nur die drei Werte EQ, LT und GT, so kann GHC bestätigen, dass Sie alle Möglichkeiten abgedeckt haben, und ein menschlicher Leser kann leicht erkennen, dass Sie sie richtig behandelt haben.

Dies ist auch effizienter Code: wir rufen compare einmal, anstatt == anrufen und dann wahrscheinlich auch < aufrufen.

Jetzt werde ich noch etwas abschweifen und über Faulheit reden.

Sie haben wahrscheinlich auch eine ähnliche Funktion wie folgt geschrieben:

contains :: (Ord a) => a -> Tree a -> Bool 
contains _ EmptyTree = False 
contains x (Node a left right) = case x `compare` a of 
    EQ -> True 
    ... 

Wenn x == a, müssen Sie wissen, dass der Baum den Node Konstruktor verwendet, und dass das erste Argument ist zu x gleich. Sie müssen nicht wissen, was einer der Unterbäume ist.

Aber jetzt zurück zu meiner Definition von insert oben. Wenn die angegebene Baumstruktur eine Node ist, gibt sie immer eine Node zurück, deren erstes Argument immer a ist. Aber das steht nicht im Voraus: Stattdessen wertet es x `compare` a aus.

Wir können insert umschreiben den Vergleich so spät wie möglich auszuführen:

insert :: (Ord a) => a -> Tree a -> Tree a 
insert x EmptyTree = Node x EmptyTree EmptyTree 
insert x (Node a left right) = Node a newLeft newRight 
    where comparison = x `compare` a 
     newLeft = if comparison == LT then insert x left else left 
     newRight = if comparison == GT then insert x right else right 

wir die Node a bisschen so schnell wie möglich Nun kehren --- auch wenn der Vergleich einen Fehler wirft! --- und wir führen den Vergleich höchstens einmal durch.

Answer 2

GHC kann nicht ableiten, ob Ihre drei Wächter in der insert x (Node a left right) alle möglichen Fälle abdecken, und folglich wird kein Körper mit insert x (Node a left right) assoziiert werden. Versuchen Sie, die letzte Bedingung x > a durch otherwise (ein Synonim für True) zu ersetzen. In diesem speziellen Fall ist es jedoch wahr, dass die Wachen nicht alle Fälle abdecken, siehe Augusts Beispiel über doppelte Zahlen.

Answer 3

Dies liegt daran, dass die Mustererkennung unvollständig ist. Es gibt keine Garantie dafür, dass eines von x==a, x<a oder x>a gilt. Wenn beispielsweise der Typ Double und x NaN ist, dann ist keiner von ihnen True.