How does Haskell do pattern matching without us defining an Eq on our data types?

Question

I have defined a binary tree:

data Tree = Null | Node Tree Int Tree

and have implemented a function that'll yield the sum of the values of all its nodes:

sumOfValues :: Tree -> Int
sumOfValues Null = 0
sumOfValues (Node Null v Null) = v
sumOfValues (Node Null v t2) = v + (sumOfValues t2)
sumOfValues (Node t1 v Null) = v + (sumOfValues t1)
sumOfValues (Node t1 v t2) = v + (sumOfValues t1) + (sumOfValues t2)

It works as expected. I had the idea of also trying to implement it using guards:

sumOfValues2 :: Tree -> Int
sumOfValues2 Null = 0
sumOfValues2 (Node t1 v t2)
    | t1 == Null && t2 == Null  = v
    | t1 == Null            = v + (sumOfValues2 t2)
    |               t2 == Null  = v + (sumOfValues2 t1)
    |   otherwise       = v + (sumOfValues2 t1) + (sumOfValues2 t2)

but this one doesn't work because I haven't implemented Eq, I believe:

No instance for (Eq Tree)
  arising from a use of `==' at zzz3.hs:13:3-12
Possible fix: add an instance declaration for (Eq Tree)
In the first argument of `(&&)', namely `t1 == Null'
In the expression: t1 == Null && t2 == Null
In a stmt of a pattern guard for
             the definition of `sumOfValues2':
        t1 == Null && t2 == Null

The question that has to be made, then, is how can Haskell make pattern matching without knowing when a passed argument matches, without resorting to Eq?

Edit

Your arguments seem to revolve around the fact that Haskell is not indeed comparing the arguments of the function, but instead on the "form" and types of signature to know which sub-function to match. But how about this?

f :: Int -> Int -> Int
f 1 _ = 666
f 2 _ = 777
f _ 1 = 888
f _ _ = 999

When running f 2 9, won't it have to use Eq to know which one of the subfunctions is the right one? All of them are equal (contrary to my initial Tree example when we had Tree/Node/Null). Or is the actual definition of an Int something like

data Int = -2^32 | -109212 ... | 0 | ... +2^32 

?

Answer 1

For pattern matching, Haskell uses the structure of the value and the constructors used. For example, if you evaluate

sumOfValues (Node Null 5 (Node Null 10 Null))

it checks the patterns from top to bottom:

• the first one, Null, doesn't match because it has a different structure

• the second one, (Node Null v Null), doesn't match because the last component, Null, has a different structure than (Node Null 10 Null) (pattern matching proceeds recursively)

• the third one matches with v bound to 5 and t2 bound to (Node Null 10 Null).

Eq and the == operator it defines are an unrelated mechanism; making Tree an instance of Eq won't change how pattern matching works.

I think your thinking here is a bit backward: Pattern matching is the most basic way of using a value in Haskell; except for some basic types like Int, Eq is implemented using pattern matching, not the other way around.

Pattern matching and numbers

It turns out numeric literals are a special case. According to the Haskell report (link):

Matching a numeric, character, or string literal pattern k against a value v succeeds if v == k, where == is overloaded based on the type of the pattern.