Case on a set ignores equality/inequality

Question

Pattern-matching is based on Eq instance, right? I see that Data.Set.Set implements Eq and

>S.fromList [] == S.fromList [1,2]
False
>S.fromList [1,2] == S.fromList [2,1]
True

which is right. Then why does

case S.fromList [1,2] of mempty -> True

return true? (actually it always evaluates to true). I mean such matching is wrong and we should use S.null as a predicate, but anyway: how does it work and comes to True?

Answer 1

Pattern-matching is based on Eq instance, right?

Wrong. In general^†, pattern matching doesn't have anything to do with ==. Pattern matching is structural deconstruction. This requires having constructors available. Set is internally defined as

data Set a    = Bin {-# UNPACK #-} !Size !a !(Set a) !(Set a)
              | Tip

so you could write

import Data.Set.Internal (Set(..))

case S.fromList [1,2] of Tip -> True

Notice that the LHS of the pattern is uppercase. This means Tip can't be a variable, so the thing you've experiences where it shadows the existing name mempty can't happen.

But you're not supposed to do that. Data.Set does not export the constructors; the implementation is considered too complicated / unstable to be sensible to access for users. Instead you can just do

    if S.null (S.fromList [1,2]) then True
                                 else FLEBLEBLEARG

Arguably, at least for the empty case it would make sense to have the constructor available. You can actually define a usable version of it yourself with -XPatternSynonyms and -XViewPatterns.

---

^†_{The exception are number literals. To match on such a literal, you need to have instances of both Num and Eq, and the pattern match works by first converting the literal to the suitable type and then performing an equality check. Likewise for string literals when -XOverloadedStrings is enabled.}