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