[Haskell-beginners] Is this MR? Type restriction confusion

[Daniel Fischer]

Am Donnerstag 17 Dezember 2009 23:56:13 schrieb Mike Erickson:
> I was trying to convert a function,
>
> f1 x l = map (\y -> y*x) l
>
> to so-called point-free style, but in reducing it I found two
> functions that seemed to work the same, until I discovered they have
> different types, and aren't equivalent:
>
> f1a x = map (*x) -- has type (Num a) => a -> [a] -> [a]
>
> f1b = \x -> map (*x) -- has type Integer -> [Integer] -> [Integer]
>
> Can someone help me understand why the latter has a more restrictive type?

Indeed it's the monomorphism restriction.
In

f1a x = map (*x)

, f1a is bound by a *function binding* (bound name and (>= 1) pattern on the left of '='),
thus it has a polymorphic type. In

f1b = \x -> map (*x)

(btw, you can further point-free this as map . (*)), f1b is bound by a *simple pattern 
binding*, thus the monomorphism restriction says that without a type signature, it must 
have a monomorphic type.
Type inference determines the type (Num a) => a -> [a] -> [a] for the function. This is a 
"type class polymorphic" type [the monomorphism restriction doesn't restrict unconstrained 
types, only if a type class is involved does it kick in], hence by the monomorphism 
restriction, it must have a monomorphic type. The type class is Num, thus by the default 
defaulting rules, for (Num a), a is instantiated as Integer, hence 
f1b :: Integer -> [Integer] -> [Integer]

>
> If I add the type signature "f1b :: (Num a) => a -> [a] -> [a]", they
> are once again equivalent, but am confused about what's going on. If

The monomorphism restriction only applies to functions without a type signature.

> this is MR, what exactly am I overloading here?
>
> I read through http://www.haskell.org/haskellwiki/Monomorphism_restriction
> and
> http://www.cs.auckland.ac.nz/references/haskell/haskell-intro-html/pitfalls
>.html. If anyone has a good reading recommendation here, I'd love to see it.

Read the report:http://haskell.org/onlinereport/decls.html#sect4.5.5
(start at section 4.5.4) and http://haskell.org/onlinereport/decls.html#sect4.4.3 for 
pattern and function bindings. It's a little technical, but with the other resources it 
should be understandable.

In short, if you declare a function point-free and the inferred type involves type 
classes, it cannot be polymorphic unless you give a type signature. Without a type 
signature, the implementation tries to determine a monomorphic type from the inferred 
polymorphic type by the defaulting rules 
(http://haskell.org/onlinereport/decls.html#sect4.3.4). If that succeeds, this type is 
given to the function, otherwise it's a type error and the module doesn't compile.

> Because if this is MR, I'm not understanding what MR is correctly. Also,
> They don't generate a type error, which makes me think it is not MR, but
> something else.
>
> Thanks,
>
> Mike