14

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?

10

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.

  • I hadn't considered the possibility of f [] :: (Int, Float). Now it makes perfect sense. Thank you. – Ixrec May 6 '15 at 21:05
  • 1
    It's the same function name, with the same arguments, but potentially different return types and implementations, because it's polymorphic. I think the better way of looking at it is that the typeclass instance is effectively an extra argument to genericLength and the compiler isn't convinced it's the same arguments in both calls. – Doval May 6 '15 at 21:05
  • Quick side question. If MonomorphismRestriction is turned off, but later on you did something like a = uncurry (==) $ f [1, 2, 3] Would it be able to optimize that call site to only check the length of [1, 2, 3] once? If so then I am really confused as to what the monomorphism restriction is actually buying you, if not then why not? – semicolon Jun 16 '16 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.