Express a "case ... of" pattern more elegantly in Haskell

Question

I came across a pattern which I believe can be expressed more elegantly:

I have two functions f1,f2 :: Int -> Int (their impl. is not relevant), and a process :: Int -> Int which does the following:

• if f1 x produces x1 different from x, then repeat the process with x1
• otherwise, if f2 x produces x2 different from x, then repeat the process with x2
• finally, stop the process and return x

My case ... of implementation is the following:

f1 :: Int -> Int
f1 = undefined

f2 :: Int -> Int
f2 = undefined

process :: Int -> Int
process x =
    case f1 x of
        x ->
            case f2 x of
                x -> x
                x' -> process x'
        x' -> process x'

which produces the following warnings:

so.hs:13:17: warning: [-Woverlapping-patterns]
    Pattern match is redundant
    In a case alternative: x' -> ...
   |
13 |                 x' -> process x'
   |                 ^^^^^^^^^^^^^^^^

so.hs:14:9: warning: [-Woverlapping-patterns]
    Pattern match is redundant
    In a case alternative: x' -> ...
   |
14 |         x' -> process x'
   |         ^^^^^^^^^^^^^^^^

Can anyone shed some light as to what patterns are overlapping, and how to implement process more elegantly?

Answer 1

There is no way to write a pattern for "a value equal to the one I have stored in a variable x". This is because pattern matching is the primary way variables are created in Haskell.

process :: Int -> Int
process x =

Here x is a pattern. It's a very simple pattern, since it just matches any possible value for the argument to process, but you could have written a more structured pattern, or even multiple equations for process matching different patterns for that argument. And within the scope of that pattern match (the entire RHS of process), you have x as a local variable referring to the matched value.

    case f1 x of
        x ->

Here x is once again a pattern, and once again it is a very simple pattern matching any possible value that was inspected by the case expression. Then you have x as a new local variable referring to the matched value within the scope of the match (everything the RHS of the -> arrow); and because you have created two local variables with the same name x, the most local one shadows the other in the scope where they both apply (so you have no way of referring to the original x in the RHS of the -> arrow, only the new x that is the result of f applied to the original x).

If you think the pattern x in the case expression ought to mean "match a value equal to x", then why should the pattern x in the function argument mean "match anything and call it x"? You can't have your cake and eat it too¹.

Haskell makes the rule very simple: a variable appearing in a pattern is always the creation of a new variable to refer to the value that matched the pattern. It is never a reference to an existing variable to check if the matched value is equal to it. Only constructors will be "checked to see if they match"; variables are just bound to whatever is there².

The same applies to your inner case, where you meant to test the result to see if it was still x but actually just created yet another x shadowing both of the outer x variables.

This is why the compiler complains about your other pattern matches being redundant. Pattern are checked in order, and the first pattern in each case already matches anything (and calls it x), so the second match in each case will never even be tried.

So, since pattern matching can never test whether a value is equal to a variable, you just need to use a construct other than pattern matching! if ... then ... else ... would work fine. You could also use a guard on a pattern.

---

² At least not if you want to be able to tell what a pattern means locally, without examining all containing scopes including the entire module and all imports. A hypothetical language could decide the meaning of the pattern based on whether there's already a variable of that name in scope, but I think Haskell makes right call here. Unexpected shadowing sometimes causes tricky bugs, but at least some sign of them is always local. It would be a nightmare if you could change a pattern from a catch-all to an equality check by introducing a global scope variable with the same name (possibly not even in the same module or even package!).

---

² This is actually the core reason we have the syntactic distinction between constructors starting with a capital letter and variables starting with a lowercase letter! The language designers wanted it to be easy to tell at a glance which words are constructors to be matched and which are variables to be bound, without having to consider all the constructor names in scope.

Answer 2

Following Ben's advice, I wrote the following:

process :: Int -> Int
process x
    | x /= x1 = process x1
    | x /= x2 = process x2
    | otherwise = x
  where
    x1 = f1 x
    x2 = f2 x