对于没有 `otherwise` 子句的 Haskell 函数，模式匹配是非穷尽的

Question

考虑一个函数 disjoint :: (Eq a, Ord a) => [a] -> [a] -> Bool 检查两个排序列表之间是否存在公共元素（如果存在，它 returns False 因为它们 不会't脱节).

disjoint :: (Eq a, Ord a) => [a] -> [a] -> Bool
disjoint [] _ = True
disjoint _ [] = True
disjoint (x:xs) (y:ys)
  | x == y = False
  | x < y = disjoint xs (y:ys)
  | x > y = disjoint (x:xs) ys

在我的 IDE vscode 中，它会产生以下警告：

Pattern match(es) are non-exhaustive
In an equation for ‘disjoint’: Patterns not matched: (_:_) (_:_)compile(-Wincomplete-patterns)

使用 otherwise 子句以不同但相似的方式编写它不会产生错误：

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

第一个代码块“错过”了什么“模式”？换句话说，第一个代码块在哪些参数上会出现问题？

Answer 1

来自@chi的评论:

考虑以下数据类型：

data TT = Bogus 
instance Eq TT where
  Bogus == Bogus = False
instance Ord TT where
  Bogus <= Bogus = False
  Bogus < Bogus = False
  Bogus >= Bogus = False
  Bogus > Bogus = False

Bogus 和 Bogus returns False 之间的任何比较。正因为如此，

> disjoint [Bogus, Bogus] [Bogus, Bogus]
*** Exception: Ch04Book.hs:(25,1)-(30,18): Non-exhaustive patterns in function disjoint

自 comparisons between NaNs always returns False.

运行 disjoint [acos 2] [acos 2] 时引发相同的异常

Sidenote/implication：A类型的typeclassOrd不一定跟在Law of excluded middle之后。请参阅 Bogus，其中 Bogus < Bogus = False 和 Bogus >= Bogus = False 以及 Haskell 都不会抱怨。

Answer 2

Eq 是 Ord 的超类，因此您可以从约束中省略它。

你可以用compare把它变成只有三种情况的data Ordering = LT | EQ | GT，让编译器推断出穷举。

disjoint :: Ord a => [a] -> [a] -> Bool
disjoint [] _ = True
disjoint _ [] = True
disjoint (x:xs) (y:ys) =
  case x `compare` y of
    EQ -> False
    LT -> disjoint xs (y:ys)
    GT -> disjoint (x:xs) ys

对于没有 `otherwise` 子句的 Haskell 函数，模式匹配是非穷尽的

Pattern match(es) are non-exhaustive for Haskell function without `otherwise` clause

haskell

pattern-matching