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.

Answer 2

Thanks for your help! After some searches, I also found this answer to be helpful: How can I re-assign a variable in a function in Haskell?

A new variable having the same name is created that shadows the previous one. But the first variable continues to exist and in some cases be still accessible...

So indeed this is far from Prolog and yes the following flag is of precious help:

Prelude> :set -fwarn-name-shadowing