¿Por qué GHC se queja de patrones no exhaustivos?

Question

Cuando puedo compilar el código siguiente con GHC (usando la bandera -Wall):

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 se queja de que la coincidencia de patrones en insert es no exhaustiva:

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

¿Por qué se GHC emite esta advertencia? Es bastante obvio que el patrón por el que se queja GHC se maneja en insert x (Node a left right).

Answer 1

Riccardo está en lo cierto, GHC no infiere que sus protectores no pueden ser todos falsos. Entonces acepta su respuesta por favor.

Voy a hacer una digresión y hablar sobre el estilo de codificación.

Su motivación para no usar otherwise puede haber sido que se ve fea:

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) 

En cuanto a este código, un lector humano debe confirmar a sí mismos que el guardia último acepta precisamente aquellos casos en que x > a.

Podríamos lugar escribirlo así:

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) 

El tipo devuelto por Orderingcompare tiene sólo los tres valores EQ, LT y GT, por lo GHC puede confirmar que ha cubierto todas las posibilidades, y un lector humano puede ver fácilmente que los ha cubierto correctamente.

Este es también un código más eficiente: llamamos compare una vez, en lugar de llamar al == y luego también llamar al <.

Ahora voy a hacer una digresión y hablar de pereza.

Usted probablemente también ha escrito una función similar a esto:

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

Cuando x == a, lo que necesita saber que el árbol utiliza el constructor Node, y que su primer argumento es igual a x. No necesita saber cuáles son los subárboles.

Pero ahora mira atrás a mi definición de insert anterior. Cuando el árbol que se le da es Node, siempre devuelve Node cuyo primer argumento es siempre a. Pero no indica eso por adelantado: en su lugar, evalúa x `compare` a.

Podemos reescribir insert para realizar la comparación lo más tarde posible:

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 

Ahora volvemos el bit Node a tan pronto como sea posible --- incluso si la comparación arroja un error! --- y todavía realizamos la comparación una vez como máximo.

Answer 2

GHC no puede inferir si sus tres protecciones en el insert x (Node a left right) cubren todos los casos posibles y, por lo tanto, no habrá ningún cuerpo asociado con insert x (Node a left right). Intente reemplazar la última condición x > a con otherwise (un sinónimo para True). En este caso específico, sin embargo, es cierto que las protecciones no cubren todos los casos, consulte el ejemplo de augustss sobre números dobles.

Answer 3

Es porque la coincidencia de patrón está incompleta. No hay garantía de que uno de x==a, x<a o x>a tenga. Por ejemplo, si el tipo es Double y x es NaN, ninguno de ellos es True.