为什么Haskell模式必须是线性的？

Question

禁止代码示例（我希望能够编写）：

isWaiting :: Eq a => a -> PriorityQueue a -> Bool
isWaiting x EmptyQueue = False
isWaiting x (Push x y p) = True 
isWaiting x (Push z y p) = isWaiting x p 

相同的逻辑，但有效的变体：

isWaiting :: Eq a => a -> PriorityQueue a -> Bool
isWaiting x EmptyQueue = False
isWaiting x (Push z y p) = if x == z then True else isWaiting x p

Answer 1

处理非线性模式将需要确定要匹配的两个项是否相等。通常，我们不能这样做：

areFunctionsEqual :: (Integer->Integer) -> (Integer->Integer) -> Bool
areFunctionsEqual f f = True
areFunctionsEqual _ _ = False

由于我们无法比较函数，因此上述内容实际上是不允许的。

但是，人们可能会奇怪为什么类中的类型不允许这样做Eq，而可判定性不是问题。那将允许一个人写

foo x y x = ...

代替

foo x y z | z==x = ...

这很难证明。有人可能会辩称，第一个非线性模式可能是偶然编写的，并引入了细微的错误。第二个没有那么长，并且可以更好地记录意图。

我认为，这是否是一个好的论点，取决于个人观点。

另一个微妙的论点：

foo x y z | z==x = bar x

在符号上等效于

foo x y z | z==x = bar z

但是这两种变体仍可能导致不同的内存占用，因为在较大的程序中，第一个可能允许z进行垃圾回收，而第二个可能允许x进行垃圾回收。如果，例如，z已经在程序的其他地方引用了，我们想使用第二种形式，那x就是垃圾回收。第一种形式将导致两者x并被z保留在内存中。

如果我们可以写foo x y x = bar x，那将要被垃圾回收？不太清楚。

可以说这是一个很小的要点，因为如果控制垃圾收集如此重要，则仍然可以使用显式变体。

Answer 2

某些具有模式匹配的语言（例如Prolog，Erlang）允许

isWaiting x (Push x y p) = True 

表示仅在两个模式变量x相等时模式才匹配。

Haskell没有。如果愿意，您可以阅读模式匹配-Prolog与Haskell。

使用防护的工作变体的替代方法如下：

isWaiting :: Eq a => a -> PriorityQueue a -> Bool
isWaiting x EmptyQueue = False
isWaiting x (Push z y p)
  | x == z = True
  | otherwise = isWaiting x p

使用(||)运算符而不是if-then-else的代码如下所示：

isWaiting :: Eq a => a -> PriorityQueue a -> Bool
isWaiting x EmptyQueue = False
isWaiting x (Push z y p) = x == z || isWaiting x p

编辑：和使用丹尼尔·瓦格纳的建议推导的Foldable：

{-# LANGUAGE DeriveFoldable #-}

type Priority = ...

data PriorityQueue a
  = EmptyQueue
  | Push a Priority (PriorityQueue a)
  deriving (Foldable)

isWaiting :: Eq a => a -> PriorityQueue a -> Bool
isWaiting = elem