[Haskell-beginners] Is this MR? Type restriction confusion
daniel.is.fischer at web.de
Thu Dec 17 18:45:26 EST 2009
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.
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
>.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.
More information about the Beginners