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

9
votes

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

?

7
haskellpattern-matching
When you're pattern matching against numbers, you are using the Eq class. Numeric literals are not constructors. If they were, they couldn't have the type Num a => a. Note that Num requires Eq. If you define a Num instance with a funky Eq instance, pattern matching will behave accordingly (i.e. if (fromInteger 42 :: MyInt) == fromInteger 23 is true, the pattern 23 will also match the value 42 :: MyInt). – sepp2k
Just so you know, not all the 32 bits are available to represent Int. On my machine, maxBound :: Int returns 2147483647, 2^31 - 1. – Wei Hu
Yes I know. But for the context of the question, I just didn't care. – devoured elysium
btw, if you needed Eq for pattern-matching, it would be rather hard to define Eq instances in the first place yourself... ;-) – hvr
@Wei Hu: Actually, they do. Think about it: maxBound = 2147483647 = 2^31 - 1, minBound = -2147483648 = 2^32, than add 0, so you get: 2^31 + 2^31-1 +1 = 2^32, what do you want more? – fuz

7 Answers

12
votes

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.

7
votes

Haskell knows what type constructor was used to construct a particular instance, and that's all it needs in order to pattern match successfully.

7
votes

The thing you're missing is that you're assuming Null is some constant value like in C or Java. It's not — it's a constructor for the Tree type.

Pattern-matches do construction in reverse. Instead of you providing two values to the constructor and it gives you a value of the appropriate type, you provide a value of the type to the constructor and it gives you the constituent values that make up the type. The language knows which branch of the discriminated union was used to construct the value, so it can match against the correct pattern. Thus, there is no need for equality because it's all just constructors and variables — no actual values are being compared (or even necessarily evaluated).

With regards to your edit about Ints:

Yes, Int is basically a type with an obscenely large number of constructors along the lines of -2 | -1 | 0 | 1 | 2 | 3 | 4 …. It's a bit handwavy, but it works in practice.

2
votes

At some point you need pattern matching when you don't want to use Eq. E.g. you could define

isEmpty :: Tree -> Bool
isEmpty Null = True
isEmpty _ = False

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

BTW, you don't need all that cases, just this:

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

Pattern matching depends on the syntax. E.g. if you write a pattern involving constructors, pattern matching by constructors is what you'll get. If you write a pattern involving litteral expressions (and litteral floating point values or integers are just that) you get an equality test (from the Eq class) using whatever overloaded definition of the (==) operator your type may provide.

So if you overload your Fred data type which is of class Num and has a constructor, also called Fred you could define equality against Integers by checking if the given Integer is 1. Now in that weird scenario, unless I'm overlooking something, the following ought to work:

getFred :: Fred -- get a Fred
getFred = Fred -- invoke the Fred constructor

testFred :: Fred -> Bool -- tests if Fred's equality operator considers 1 equal to Fred
testFred 1 = True -- overloaded (==) tests against 1, so should be true
testFred _ = False -- shouldn't happen, then...

isFredOne = testFred $ getFred -- returns True
1
votes

You can think of the data constructors as tags. To do a pattern matching on a value of Tree, the compiled code extracts the tag and just knows which branch to dispatch to. It doesn't care about the real value, so you don't need Eq.

0
votes

I justify this type of thing to myself by saying that pattern matching is core to what Haskell is - the Eq typeclass is not.

So while there are features similar to pattern matching which require Eq, they are not pattern matching and could be implemented on top of pattern matching.