Haskell tuple not matching with function argument

Question

I'm new to Haskell so it may be obvious but I did Prolog extensively so I'm perplex about this one...

When using GHCi, I created the following function (1):

Prelude> let find k t = head [v | (k',v) <- t, k == k'] -- Definiton of find
find :: Eq a1 => a1 -> [(a1, a)] -> a

Prelude> find 2 [(1,11),(2,22)] -- Invocation of find
22

Which is expected. I then tried to remove the k' from the definition:

Prelude> let find2 k t = head [v | (k,v) <- t]
find2 :: t -> [(t1, a)] -> a

Prelude> find2 2 [(1,11),(2,22)]
11

I was then very surprised to see the value 2 actually matched with 1. Just to be sure I was not hoping for the impossible I also try the following in order to confirms that partial matching is possible in Haskell, which looks like it is actually the case:

Prelude> head [v | (2,v) <- [(1,11),(2,22)]]
22

I also noticed a difference in the function declarations. I added the required information so both declarations for find and find2 look exactly the same. But the result is still broken (2,_) matchnig (1,11):

Prelude> let find2 :: Eq a1 => a1 -> [(a1, a)] -> a; find2 k t = head [v | (k,v) <- t]
find2 :: Eq a1 => a1 -> [(a1, a)] -> a

Prelude> find2 2 [(1,11),(2,22)]
11

How can 2 be matching 1 by any mean?

(1) The above function comes from the excellent book "Programming in Haskell" p.93

Answer 1

Yes, Haskell pattern matching is fundamentally different from Prolog pattern matching.

In Haskell, a variable in a pattern refers to a fresh variable that will be bound by the match, never an existing variable that must be matched. So, the expression:

let x = 5 in case (1,2) of (x,y) -> "matched!"   -- gives "matched!"

will always evaluate to "matched!". That's because the x in (x,y) gets freshly bound to 1, not compared with the value of the "existing", outer definition of x, as you can see here:

let x = 5 in case (1,2) of (x,y) -> x     -- gives "1"

The behavior is different for numeric constants:

case (1,2) of (5,y) -> "matched!"    -- match fails

and for other constructors:

case (True,2) of (False,y) -> "match!"   -- match fails

which are not "re-bound" but rather must match for the pattern match to succeed. This is one of many reasons that alphanumeric constructors start with capital letters: otherwise, it would tremendously difficult to determine whether a pattern involved matching to an existing constructor or rebinding to a fresh variable.

This applies to pattern matches in any context, whether it's case expressions as above or function definitions like this:

let x = 5
f x = "hi"     -- defines `f` for any `x`, not just `f 5`

or list comprehensions like your example. In the expression:

[v | (k,v) <- [(1,2),(3,4)]]    -- gives [(1,2),(3,4)]

the variables k and v will always be fresh, so will bind to any of the tuples despite any outer, existing definitions of k or v. If you turn on warnings with -Wall (specifically -Wname-shadowing), this will alert you to the shadowed binding. If you replace k with a constant (or other constructor), it behaves differently:

[v | (3,v) <- [(1,2),(3,4)]]    -- only gives [(3,4)]

You may not like it, but that's just the way Haskell works.