Why is Haskell unable to avoid repeated evaluation without the monomorphism restriction?

Question

I just finished learnyouahaskell the other day, and I was trying to make sense of the Monomorphism Restriction, as described by the Haskell Wiki. I think I understand how the MR can prevent repeated evaluations, but I'm failing to see why those repeated evaluations can't be avoided by far more straightforward means.

The specific example I have in mind is the one used by the wiki:

f xs = (len,len)
  where
    len = genericLength xs

where genericLength is of type Num a => [b] -> a.

Obviously, genericLength xs only needs to be computed once to evaluate (len,len), since it's the same function with the same arguments. And we don't need to see any invocations of f to know that. So why can't Haskell do this optimization without introducing a rule like the MR?

The discussion on that wiki page tells me it has something to do with the fact that Num is a typeclass rather than a concrete type, but even so, shouldn't it be obvious at compile-time that a pure function would return the same value--and thus the same concrete type of Num--when given the same arguments twice?

Answer 1

It's the same function name, with the same arguments, but potentially different return types and implementations, because it's polymorphic. That means if it's called in a context expecting an (Int, MyWeirdCustomNumType) return type, it has to evaluate it twice, because the implementation of (+) in Int is completely different from the implementation of (+) in MyWeirdCustomNumType. You need to run physically different code at some point.

That's why it matters that Num is a type class. It means you have different implementations for different types. It also means if f is in a library, it doesn't know at compile time about all the combinations of types it might need to return.

So, yes, you do need to see the invocations of f to know what return types to use. Most of the time, you would expect them to be the same, which is why they put the monomorphism restriction in by default. It can be turned off for those rare occasions when you don't. In practice, programmers don't tend to leave these sorts of situations up to type inference anyway.