Why do Haskell patterns have to be linear?

Handling non-linear patterns would require to decide equality on the two terms which are being matched. In general, we can't do this:

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

The above can not really be allowed since we can't compare functions.

One might however wonder why that is not allowed for types in the Eq class, where decidability is not an issue. That would allow one to write

foo x y x = ...

instead of

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

This is harder to justify. One might argue that the first non linear pattern might be written by accident, and introduce subtle bugs. The second is not that longer, and better documents the intent.

Whether this is a good argument or not is a matter of personal opinion, I think.

---

Another subtle argument:

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

is denotationally equivalent to

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

but the two variants might still lead to different memory footprints, since in a larger program the first one might allow z to be garbage collected, while the second one would allow x to be garbage collected. If, say, z is already referred to elsewhere in the program, we want to use the second form, so that x is garbage collected. The first form would lead to both x and z to be kept in memory.

If we could write foo x y x = bar x, which is going to be garbage collected? Not so clear.

This is arguably a very a minor point, since one could still use the explicit variant, if controlling garbage collection is that important.

Some languages with pattern matching (e.g. Prolog, Erlang) allow for

isWaiting x (Push x y p) = True 

to mean that the pattern only matches when the two pattern variables x are equivalent.

Haskell doesn't. You can read up on Pattern Matching - Prolog vs. Haskell if you like.

---

An alternative to your working variant that uses guards looks like:

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

And one that uses the (||) operator instead of if-then-else looks like:

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

Edit: And one that uses Daniel Wagner's proposal of deriving 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