https://wiki.haskell.org/api.php?action=feedcontributions&user=Dainichi&feedformat=atomHaskellWiki - User contributions [en]2019-10-22T15:11:56ZUser contributionsMediaWiki 1.27.4https://wiki.haskell.org/index.php?title=Monomorphism_restriction&diff=41636Monomorphism restriction2011-08-16T06:33:25Z<p>Dainichi: Removing question about creating functions polymorphic in return type</p>
<hr />
<div>The monomorphism restriction is probably the most annoying and controversial feature of Haskell's type system. All seem to agree that it is evil, but whether or not it is considered a necessary evil depends on who you ask.<br />
<br />
The definition of the restriction is fairly technical, but to a first approximation it means that you often cannot overload a function unless you provide an explicit type signature. In summary:<br />
<br />
<haskell><br />
-- This is allowed<br />
f1 x = show x<br />
<br />
-- This is not allowed<br />
f2 = \x -> show x<br />
<br />
-- ...but this is allowed<br />
f3 :: (Show a) => a -> String<br />
f3 = \x -> show x<br />
<br />
-- This is not allowed<br />
f4 = show<br />
<br />
-- ...but this is allowed<br />
f5 :: (Show a) => a -> String<br />
f5 = show<br />
</haskell><br />
<br />
Arguably, these should all be equivalent, but thanks to the monomorphism restriction, they are not.<br />
<br />
The difference between the first and second version is that the first version binds x via a "simple pattern binding" (see section 4.4.3.2 of the Haskell 98 report), and is therefore unrestricted, but the second version does not. The reason why one is allowed and the other is not is that it's considered clear that sharing f1 will not share any computation, and less clear that sharing f2 will have the same effect. If this seems arbitrary, that's because it is. It is difficult to design an objective rule which disallows subjective unexpected behaviour. Some people are going to fall foul of the rule even though they're doing quite reasonable things.<br />
<br />
So why is the restriction imposed? The reasoning behind it is fairly subtle, and is fully explained in the [http://haskell.org/onlinereport/ Haskell 98 report]. Basically, it solves one practical problem (without the restriction, there would be some ambiguous types) and one semantic problem (without the restriction, there would be some repeated evaluation where a programmer might expect the evaluation to be shared). Those who are for the restriction argue that these cases should be dealt with correctly. Those who are against the restriction argue that these cases are so rare that it's not worth sacrificing the type-independence of eta reduction.<br />
<br />
:An example, from [http://research.microsoft.com/~simonpj/papers/history-of-haskell/index.htm A History of Haskell]: Consider the <code>genericLength</code> function, from <code>Data.List</code><br />
<br />
:<haskell><br />
genericLength :: Num a => [b] -> a<br />
</haskell><br />
<br />
:And consider the function:<br />
<br />
<haskell><br />
f xs = (len,len)<br />
where<br />
len = genericLength xs<br />
</haskell><br />
<br />
:<code>len</code> has type <code>Num a => a</code> and, without the monomorphism restriction, it could be computed ''twice''. --[[User:ARG|ARG]]<br />
<br />
----<br />
<br />
It is not clear to me how this whole thing about being computed once or twice works. Isn't type checking/inference something that happens at compile-time and shouldn't have any effect on what happens at run-time, as long as the typecheck passes? [[User:Dainichi|Dainichi]]<br />
<br />
The trouble is that typeclasses essentially introduce additional function parameters -- specifically, the dictionary of code implementing the instances in question. In the case of typeclass polymorphic pattern bindings, you end up turning something that looked like a pattern binding -- a constant that would only ever be evaluated once, into what is really a function binding, something which will not be memoised. [[User:CaleGibbard|CaleGibbard]] 23:46, 1 February 2008 (UTC)<br />
<br />
The type of <code>f</code>, if no signature is given, then the compiler doesn't know that the two elements of the returned pair are of the same type. It's return value will be:<br />
<br />
<haskell><br />
f::(Num a, Num b) => [x] -> (a, b)<br />
</haskell><br />
<br />
This means that <i>while compiling f</i> the compiler is unable to memoise len - clearly if a /= b then different code is executed to compute the first and second appearance of len in the pair. It's possible the compiler could do something more clever <i>when f is actually applied</i> if a == b, but I'm supposing this isn't a straight-forward thing to implement in the compilers. [[User:Dozer|Dozer]] 23:54, 4 February 2008 (GMT)<br />
<br />
Thank you, the nature of the ''problem'' is getting clearer now, but I'm still confused about how the restriction of top level definitions is supposed to ''solve'' this problem. To me, the given example explains why f's type is inferred to be <haskell>Num a => [x] -> (a, a)</haskell>, not <haskell>(Num a, Num b) => [x] -> (a, b)</haskell>, but not why this means that you cannot define top-level overloading outside pattern bindings. Is there an example which makes this clearer?<br />
<br />
Maybe I need to read up on the Hindley–Milner type system, but this seems related to the existence of functions (such as genericLength and read) that are polymorphic in their return type. Would MR need to exist without these functions? <br />
<br />
I'm a bit confused about functions like this, since I somehow feel they belong to more of a system with dependent types. <br />
<br />
--[[User:Dainichi|Dainichi]] 06:53 15 Aug 2011 (UTC)<br />
<br />
<br />
<br />
----<br />
<br />
Oversimplifying the debate somewhat: Those in favour tend to be those who have written Haskell [[Implementations]] and those against tend to be those who have written complex combinator libraries (and hence have hit their collective heads against the restriction all too often). It often boils down to the fact that programmers want to avoid [http://catb.org/esr/jargon/html/L/legalese.html legalese], and language implementors want to avoid [http://catb.org/esr/jargon/html/C/cruft.html cruft].<br />
<br />
In almost all cases, you can get around the restriction by including explicit type declarations. Those who are for the restriction are usually quick to point out that including explicit type declarations is good programming practice anyway. In a few very rare cases, however, you may need to supply a type signature which is not valid Haskell. (Such type signatures require a type system extension such as [[Scoped type variables]].) Unless you're writing some weird combinator libraries, or are in the habit of not writing type declarations, you're unlikely to come across it. Even so, most Haskell [[Implementations]] provide a way to turn the restriction off.<br />
<br />
See also: [http://haskell.org/onlinereport/decls.html#sect4.5.5 Section 4.5.5, Haskell 98 report].<br />
<br />
-- [[Andrew Bromage]]<br />
<br />
Some question or suggestion: As I understand the problem arises from the situation that two different forms of assignment are described by the same notation. There are two forms of assignment, namely the inspection of data structures ("unpacking", "pattern binding") and the definition of functions ("function binding"). Unique examples are:<br />
<br />
<haskell><br />
let f x = y -- function definition<br />
let F x = y -- data structure decomposition<br />
</haskell><br />
<br />
In the first case we have the identifier f starting with lower case. This means this is a function binding. The second assignment starts with F, which must be a constructor. That's why this is a pattern binding. The monomorphism restriction applies only to the pattern binding. I think this was not defined in order to please compiler writers, but has shown to be useful in practice, or am I wrong? But the different handling of these binding types leads to a problem since both types have a common case.<br />
<br />
<haskell><br />
let x = y -- function or pattern binding?<br />
</haskell><br />
<br />
So, what speaks against differentiating the assignments notationally, say<br />
<br />
<haskell><br />
let f x = y -- function definition<br />
let F x <= y -- data structure decomposition<br />
</haskell><br />
<br />
and keep the monomorphism restriction as it is?<br />
<br />
-- [[Henning Thielemann]]<br />
<br />
The problem isn't just pattern bindings, it's that pattern bindings which are typeclass polymorphic are actually function bindings in disguise, since the usual implementation of typeclasses adds parameters to such definitions, to allow the definition to take the typeclass dictionaries involved. Thus, such pattern bindings have different properties with respect to sharing (they're generally less shared than you want). In especially bad cases, without the MR, it is possible to have programs which run exponentially slower without type signatures than when signatures are added. Just distinguishing pattern bindings with a new notation doesn't solve the problem, since they'll have to be converted into function bindings in that case anyway. If you intend to keep the MR, then you don't need to change anything. The issue with the MR is just the fact that it's annoying to have eta-reduction fail in the absence of explicit type signatures, and the fact that it makes otherwise perfectly valid programs fail to compile on speculation that there might be loss of sharing (when there usually isn't, or at least the impact isn't large enough to worry about).<br />
<br />
John Hughes recently advocated the removal of the MR on the Haskell Prime mailing list, and suggested replacing it with two forms of pattern binding: one for call-by-name (polymorphic, not shared), and one for call-by-need (monomorphic, guaranteed shared). This might be similar to what you're suggesting. If you look at it too closely, it seems like a good solution, but the overall impact on Haskell code seems too large to me, to resolve a distinction which it ought to be statically possible to determine.<br />
<br />
I'm of the opinion that it would be better to find a way to restore sharing lost through the typeclass transformation in some way, or else implement typeclasses in an altogether different way which doesn't run into this problem. Additional runtime machinery seems like a likely candidate for this -- the interactions with garbage collection are somewhat subtle, but I think it should be doable. It's also possible to restore the sharing via whole-program analysis, but advocates of separate compilation will probably complain, unless we were to find a mechanism to fix the problem from the object code (and potentially temporaries) at link time.<br />
<br />
:- [[Cale Gibbard]]<br />
<br />
--------------------<br />
I think it'd be useful to collect a set of examples of the Monormorphism Restriction biting people in an unexpected way. This may help to inform the debate over the MR by giving real-life examples. Add more examples here if (an only if) they constitute an unexpected MR-related incident in your life or someone else's. No invented examples! -- [[Simon Peyton Jones]]<br />
<br />
* GHC Trac bug [http://hackage.haskell.org/trac/ghc/ticket/1749 1749]<br />
* In trying to build an editor with undoable actions:<br />
<haskell><br />
class EditAction e a | e -> a where<br />
apply :: a -> e -> a<br />
<br />
data ListAction a = Append a | Remove<br />
<br />
instance EditAction (ListAction a) [a] where<br />
apply list (Append a) = a:list<br />
apply (x:xs) Remove = xs<br />
<br />
-- Apply all the EditActions to the input<br />
--edit :: EditAction e a => a -> [e] -> a -- monomorphism restriction - I have to put this in!<br />
edit = foldl apply<br />
</haskell><br />
<br />
----<br />
Back before forM was in the Control.Monad library, I once spent about 1/2 an hour trying to figure out why my action in the ST monad was having its '<hask>s</hask>' parameter squished to <hask>()</hask>. I tore the code apart for quite a while before discovering that it was that the MR was applying to my definition of <hask>forM</hask>:<br />
<br />
<haskell><br />
forM = flip mapM<br />
</haskell><br />
<br />
----<br />
I recently got tired of typing <hask>print "blah"</hask> in a ghci shell session and tried <hask>let p = print</hask>. Thanks to MR and Haskell defaulting, the type of <hask>p</hask> silently became <hask>() -> IO ()</hask>. No surprise that my new "short" version of print was only capable of printing void values -<br />
<br />
<hask><br />
Prelude> p ()<br />
()<br />
Prelude> p "blah"<br />
<br />
<interactive>:1:2:<br />
Couldn't match expected type `()' against inferred type `[Char]'<br />
In the first argument of `p', namely `"blah"'<br />
In the expression: p "blah"<br />
In the definition of `it': it = p "blah"<br />
</hask><br />
<br />
----<br />
<br />
<haskell><br />
import Graphics.UI.Gtk<br />
import Graphics.UI.Gtk.Glade<br />
<br />
-- xmlGetWidget' :: WidgetClass widget => (GObject -> widget) -> String -> IO widget<br />
xmlGetWidget' = xmlGetWidget undefined<br />
<br />
main :: IO ()<br />
main<br />
= do<br />
initGUI<br />
window <- xmlGetWidget' castToWindow "window1"<br />
button <- xmlGetWidget' castToButton "button1"<br />
widgetShowAll window<br />
mainGUI<br />
</haskell><br />
<br />
If I comment main, I cannot compile this code because of the monomorphism restriction. With main, it'll infer the type:<br />
<br />
<haskell><br />
xmlGetWidget' :: (GObject -> Window) -> String -> IO Window<br />
</haskell><br />
<br />
And give me a type error in the button line. If I uncomment the type signature, it'll work.<br />
<br />
----<br />
<br />
Along the same lines as Simon's question above, does anyone have any real examples of being bitten by the lack of MR? I know what it's for, but I can't really think of any realistic cases when it would be a problem. --pumpkin<br />
<br />
[[Category:Glossary]]<br />
[[Category:Language]]</div>Dainichihttps://wiki.haskell.org/index.php?title=Monomorphism_restriction&diff=41612Monomorphism restriction2011-08-15T07:02:16Z<p>Dainichi: </p>
<hr />
<div>The monomorphism restriction is probably the most annoying and controversial feature of Haskell's type system. All seem to agree that it is evil, but whether or not it is considered a necessary evil depends on who you ask.<br />
<br />
The definition of the restriction is fairly technical, but to a first approximation it means that you often cannot overload a function unless you provide an explicit type signature. In summary:<br />
<br />
<haskell><br />
-- This is allowed<br />
f1 x = show x<br />
<br />
-- This is not allowed<br />
f2 = \x -> show x<br />
<br />
-- ...but this is allowed<br />
f3 :: (Show a) => a -> String<br />
f3 = \x -> show x<br />
<br />
-- This is not allowed<br />
f4 = show<br />
<br />
-- ...but this is allowed<br />
f5 :: (Show a) => a -> String<br />
f5 = show<br />
</haskell><br />
<br />
Arguably, these should all be equivalent, but thanks to the monomorphism restriction, they are not.<br />
<br />
The difference between the first and second version is that the first version binds x via a "simple pattern binding" (see section 4.4.3.2 of the Haskell 98 report), and is therefore unrestricted, but the second version does not. The reason why one is allowed and the other is not is that it's considered clear that sharing f1 will not share any computation, and less clear that sharing f2 will have the same effect. If this seems arbitrary, that's because it is. It is difficult to design an objective rule which disallows subjective unexpected behaviour. Some people are going to fall foul of the rule even though they're doing quite reasonable things.<br />
<br />
So why is the restriction imposed? The reasoning behind it is fairly subtle, and is fully explained in the [http://haskell.org/onlinereport/ Haskell 98 report]. Basically, it solves one practical problem (without the restriction, there would be some ambiguous types) and one semantic problem (without the restriction, there would be some repeated evaluation where a programmer might expect the evaluation to be shared). Those who are for the restriction argue that these cases should be dealt with correctly. Those who are against the restriction argue that these cases are so rare that it's not worth sacrificing the type-independence of eta reduction.<br />
<br />
:An example, from [http://research.microsoft.com/~simonpj/papers/history-of-haskell/index.htm A History of Haskell]: Consider the <code>genericLength</code> function, from <code>Data.List</code><br />
<br />
:<haskell><br />
genericLength :: Num a => [b] -> a<br />
</haskell><br />
<br />
:And consider the function:<br />
<br />
<haskell><br />
f xs = (len,len)<br />
where<br />
len = genericLength xs<br />
</haskell><br />
<br />
:<code>len</code> has type <code>Num a => a</code> and, without the monomorphism restriction, it could be computed ''twice''. --[[User:ARG|ARG]]<br />
<br />
----<br />
<br />
It is not clear to me how this whole thing about being computed once or twice works. Isn't type checking/inference something that happens at compile-time and shouldn't have any effect on what happens at run-time, as long as the typecheck passes? [[User:Dainichi|Dainichi]]<br />
<br />
The trouble is that typeclasses essentially introduce additional function parameters -- specifically, the dictionary of code implementing the instances in question. In the case of typeclass polymorphic pattern bindings, you end up turning something that looked like a pattern binding -- a constant that would only ever be evaluated once, into what is really a function binding, something which will not be memoised. [[User:CaleGibbard|CaleGibbard]] 23:46, 1 February 2008 (UTC)<br />
<br />
The type of <code>f</code>, if no signature is given, then the compiler doesn't know that the two elements of the returned pair are of the same type. It's return value will be:<br />
<br />
<haskell><br />
f::(Num a, Num b) => [x] -> (a, b)<br />
</haskell><br />
<br />
This means that <i>while compiling f</i> the compiler is unable to memoise len - clearly if a /= b then different code is executed to compute the first and second appearance of len in the pair. It's possible the compiler could do something more clever <i>when f is actually applied</i> if a == b, but I'm supposing this isn't a straight-forward thing to implement in the compilers. [[User:Dozer|Dozer]] 23:54, 4 February 2008 (GMT)<br />
<br />
Thank you, the nature of the ''problem'' is getting clearer now, but I'm still confused about how the restriction of top level definitions is supposed to ''solve'' this problem. To me, the given example explains why f's type is inferred to be <haskell>Num a => [x] -> (a, a)</haskell>, not <haskell>(Num a, Num b) => [x] -> (a, b)</haskell>, but not why this means that you cannot define top-level overloading outside pattern bindings. Is there an example which makes this clearer?<br />
<br />
Maybe I need to read up on the Hindley–Milner type system, but this seems related to the existence of functions (such as genericLength and read) whose result type depends on not just the input type, but also the input value and/or the context it is being used in. Would MR need to exist without these functions? <br />
<br />
I'm a bit confused about functions like this, since I feel they belong to more of a system with dependent types. I do not seem to be able to define functions like this myself either. Trying to do<br />
<br />
<haskell><br />
three::Num a => Bool -> a<br />
three b = if b then 3::Int else 3::Double<br />
</haskell><br />
<br />
ghc tells me that "Couldn't match type `Int' with `Double'".<br />
<br />
Sorry if the latter questions are misplaced, I just felt they were related.<br />
<br />
--[[User:Dainichi|Dainichi]] 06:53 15 Aug 2011 (UTC)<br />
<br />
<br />
<br />
----<br />
<br />
Oversimplifying the debate somewhat: Those in favour tend to be those who have written Haskell [[Implementations]] and those against tend to be those who have written complex combinator libraries (and hence have hit their collective heads against the restriction all too often). It often boils down to the fact that programmers want to avoid [http://catb.org/esr/jargon/html/L/legalese.html legalese], and language implementors want to avoid [http://catb.org/esr/jargon/html/C/cruft.html cruft].<br />
<br />
In almost all cases, you can get around the restriction by including explicit type declarations. Those who are for the restriction are usually quick to point out that including explicit type declarations is good programming practice anyway. In a few very rare cases, however, you may need to supply a type signature which is not valid Haskell. (Such type signatures require a type system extension such as [[Scoped type variables]].) Unless you're writing some weird combinator libraries, or are in the habit of not writing type declarations, you're unlikely to come across it. Even so, most Haskell [[Implementations]] provide a way to turn the restriction off.<br />
<br />
See also: [http://haskell.org/onlinereport/decls.html#sect4.5.5 Section 4.5.5, Haskell 98 report].<br />
<br />
-- [[Andrew Bromage]]<br />
<br />
Some question or suggestion: As I understand the problem arises from the situation that two different forms of assignment are described by the same notation. There are two forms of assignment, namely the inspection of data structures ("unpacking", "pattern binding") and the definition of functions ("function binding"). Unique examples are:<br />
<br />
<haskell><br />
let f x = y -- function definition<br />
let F x = y -- data structure decomposition<br />
</haskell><br />
<br />
In the first case we have the identifier f starting with lower case. This means this is a function binding. The second assignment starts with F, which must be a constructor. That's why this is a pattern binding. The monomorphism restriction applies only to the pattern binding. I think this was not defined in order to please compiler writers, but has shown to be useful in practice, or am I wrong? But the different handling of these binding types leads to a problem since both types have a common case.<br />
<br />
<haskell><br />
let x = y -- function or pattern binding?<br />
</haskell><br />
<br />
So, what speaks against differentiating the assignments notationally, say<br />
<br />
<haskell><br />
let f x = y -- function definition<br />
let F x <= y -- data structure decomposition<br />
</haskell><br />
<br />
and keep the monomorphism restriction as it is?<br />
<br />
-- [[Henning Thielemann]]<br />
<br />
The problem isn't just pattern bindings, it's that pattern bindings which are typeclass polymorphic are actually function bindings in disguise, since the usual implementation of typeclasses adds parameters to such definitions, to allow the definition to take the typeclass dictionaries involved. Thus, such pattern bindings have different properties with respect to sharing (they're generally less shared than you want). In especially bad cases, without the MR, it is possible to have programs which run exponentially slower without type signatures than when signatures are added. Just distinguishing pattern bindings with a new notation doesn't solve the problem, since they'll have to be converted into function bindings in that case anyway. If you intend to keep the MR, then you don't need to change anything. The issue with the MR is just the fact that it's annoying to have eta-reduction fail in the absence of explicit type signatures, and the fact that it makes otherwise perfectly valid programs fail to compile on speculation that there might be loss of sharing (when there usually isn't, or at least the impact isn't large enough to worry about).<br />
<br />
John Hughes recently advocated the removal of the MR on the Haskell Prime mailing list, and suggested replacing it with two forms of pattern binding: one for call-by-name (polymorphic, not shared), and one for call-by-need (monomorphic, guaranteed shared). This might be similar to what you're suggesting. If you look at it too closely, it seems like a good solution, but the overall impact on Haskell code seems too large to me, to resolve a distinction which it ought to be statically possible to determine.<br />
<br />
I'm of the opinion that it would be better to find a way to restore sharing lost through the typeclass transformation in some way, or else implement typeclasses in an altogether different way which doesn't run into this problem. Additional runtime machinery seems like a likely candidate for this -- the interactions with garbage collection are somewhat subtle, but I think it should be doable. It's also possible to restore the sharing via whole-program analysis, but advocates of separate compilation will probably complain, unless we were to find a mechanism to fix the problem from the object code (and potentially temporaries) at link time.<br />
<br />
:- [[Cale Gibbard]]<br />
<br />
--------------------<br />
I think it'd be useful to collect a set of examples of the Monormorphism Restriction biting people in an unexpected way. This may help to inform the debate over the MR by giving real-life examples. Add more examples here if (an only if) they constitute an unexpected MR-related incident in your life or someone else's. No invented examples! -- [[Simon Peyton Jones]]<br />
<br />
* GHC Trac bug [http://hackage.haskell.org/trac/ghc/ticket/1749 1749]<br />
* In trying to build an editor with undoable actions:<br />
<haskell><br />
class EditAction e a | e -> a where<br />
apply :: a -> e -> a<br />
<br />
data ListAction a = Append a | Remove<br />
<br />
instance EditAction (ListAction a) [a] where<br />
apply list (Append a) = a:list<br />
apply (x:xs) Remove = xs<br />
<br />
-- Apply all the EditActions to the input<br />
--edit :: EditAction e a => a -> [e] -> a -- monomorphism restriction - I have to put this in!<br />
edit = foldl apply<br />
</haskell><br />
<br />
----<br />
Back before forM was in the Control.Monad library, I once spent about 1/2 an hour trying to figure out why my action in the ST monad was having its '<hask>s</hask>' parameter squished to <hask>()</hask>. I tore the code apart for quite a while before discovering that it was that the MR was applying to my definition of <hask>forM</hask>:<br />
<br />
<haskell><br />
forM = flip mapM<br />
</haskell><br />
<br />
----<br />
I recently got tired of typing <hask>print "blah"</hask> in a ghci shell session and tried <hask>let p = print</hask>. Thanks to MR and Haskell defaulting, the type of <hask>p</hask> silently became <hask>() -> IO ()</hask>. No surprise that my new "short" version of print was only capable of printing void values -<br />
<br />
<hask><br />
Prelude> p ()<br />
()<br />
Prelude> p "blah"<br />
<br />
<interactive>:1:2:<br />
Couldn't match expected type `()' against inferred type `[Char]'<br />
In the first argument of `p', namely `"blah"'<br />
In the expression: p "blah"<br />
In the definition of `it': it = p "blah"<br />
</hask><br />
<br />
----<br />
<br />
<haskell><br />
import Graphics.UI.Gtk<br />
import Graphics.UI.Gtk.Glade<br />
<br />
-- xmlGetWidget' :: WidgetClass widget => (GObject -> widget) -> String -> IO widget<br />
xmlGetWidget' = xmlGetWidget undefined<br />
<br />
main :: IO ()<br />
main<br />
= do<br />
initGUI<br />
window <- xmlGetWidget' castToWindow "window1"<br />
button <- xmlGetWidget' castToButton "button1"<br />
widgetShowAll window<br />
mainGUI<br />
</haskell><br />
<br />
If I comment main, I cannot compile this code because of the monomorphism restriction. With main, it'll infer the type:<br />
<br />
<haskell><br />
xmlGetWidget' :: (GObject -> Window) -> String -> IO Window<br />
</haskell><br />
<br />
And give me a type error in the button line. If I uncomment the type signature, it'll work.<br />
<br />
----<br />
<br />
Along the same lines as Simon's question above, does anyone have any real examples of being bitten by the lack of MR? I know what it's for, but I can't really think of any realistic cases when it would be a problem. --pumpkin<br />
<br />
[[Category:Glossary]]<br />
[[Category:Language]]</div>Dainichihttps://wiki.haskell.org/index.php?title=Monomorphism_restriction&diff=41611Monomorphism restriction2011-08-15T06:57:09Z<p>Dainichi: </p>
<hr />
<div>The monomorphism restriction is probably the most annoying and controversial feature of Haskell's type system. All seem to agree that it is evil, but whether or not it is considered a necessary evil depends on who you ask.<br />
<br />
The definition of the restriction is fairly technical, but to a first approximation it means that you often cannot overload a function unless you provide an explicit type signature. In summary:<br />
<br />
<haskell><br />
-- This is allowed<br />
f1 x = show x<br />
<br />
-- This is not allowed<br />
f2 = \x -> show x<br />
<br />
-- ...but this is allowed<br />
f3 :: (Show a) => a -> String<br />
f3 = \x -> show x<br />
<br />
-- This is not allowed<br />
f4 = show<br />
<br />
-- ...but this is allowed<br />
f5 :: (Show a) => a -> String<br />
f5 = show<br />
</haskell><br />
<br />
Arguably, these should all be equivalent, but thanks to the monomorphism restriction, they are not.<br />
<br />
The difference between the first and second version is that the first version binds x via a "simple pattern binding" (see section 4.4.3.2 of the Haskell 98 report), and is therefore unrestricted, but the second version does not. The reason why one is allowed and the other is not is that it's considered clear that sharing f1 will not share any computation, and less clear that sharing f2 will have the same effect. If this seems arbitrary, that's because it is. It is difficult to design an objective rule which disallows subjective unexpected behaviour. Some people are going to fall foul of the rule even though they're doing quite reasonable things.<br />
<br />
So why is the restriction imposed? The reasoning behind it is fairly subtle, and is fully explained in the [http://haskell.org/onlinereport/ Haskell 98 report]. Basically, it solves one practical problem (without the restriction, there would be some ambiguous types) and one semantic problem (without the restriction, there would be some repeated evaluation where a programmer might expect the evaluation to be shared). Those who are for the restriction argue that these cases should be dealt with correctly. Those who are against the restriction argue that these cases are so rare that it's not worth sacrificing the type-independence of eta reduction.<br />
<br />
:An example, from [http://research.microsoft.com/~simonpj/papers/history-of-haskell/index.htm A History of Haskell]: Consider the <code>genericLength</code> function, from <code>Data.List</code><br />
<br />
:<haskell><br />
genericLength :: Num a => [b] -> a<br />
</haskell><br />
<br />
:And consider the function:<br />
<br />
<haskell><br />
f xs = (len,len)<br />
where<br />
len = genericLength xs<br />
</haskell><br />
<br />
:<code>len</code> has type <code>Num a => a</code> and, without the monomorphism restriction, it could be computed ''twice''. --[[User:ARG|ARG]]<br />
<br />
----<br />
<br />
It is not clear to me how this whole thing about being computed once or twice works. Isn't type checking/inference something that happens at compile-time and shouldn't have any effect on what happens at run-time, as long as the typecheck passes? [[User:Dainichi|Dainichi]]<br />
<br />
The trouble is that typeclasses essentially introduce additional function parameters -- specifically, the dictionary of code implementing the instances in question. In the case of typeclass polymorphic pattern bindings, you end up turning something that looked like a pattern binding -- a constant that would only ever be evaluated once, into what is really a function binding, something which will not be memoised. [[User:CaleGibbard|CaleGibbard]] 23:46, 1 February 2008 (UTC)<br />
<br />
The type of <code>f</code>, if no signature is given, then the compiler doesn't know that the two elements of the returned pair are of the same type. It's return value will be:<br />
<br />
<haskell><br />
f::(Num a, Num b) => [x] -> (a, b)<br />
</haskell><br />
<br />
This means that <i>while compiling f</i> the compiler is unable to memoise len - clearly if a /= b then different code is executed to compute the first and second appearance of len in the pair. It's possible the compiler could do something more clever <i>when f is actually applied</i> if a == b, but I'm supposing this isn't a straight-forward thing to implement in the compilers. [[User:Dozer|Dozer]] 23:54, 4 February 2008 (GMT)<br />
<br />
Thank you, the nature of the ''problem'' is getting clearer now, but I'm still confused about how the restriction of top level definitions is supposed to ''solve'' this problem. To me, the given example explains why f's type is inferred to be <haskell>Num a => [x] -> (a, a)</haskell>, not <haskell>(Num a, Num b) => [x] -> (a, b)</haskell>, but not why this means that you cannot define top-level overloading outside pattern bindings. Is there an example which makes this clearer?<br />
<br />
Maybe I need to read up on the Hindley–Milner type system, but this seems related to the existence of functions (such as genericLength and read) whose result type depends on not just the input type, but also the input ''value''. Would MR need to exist without these functions? <br />
<br />
I'm a bit confused about functions like this, since I feel they belong to more of a system with dependent types. I do not seem to be able to define functions like this myself either. Trying to do<br />
<br />
<haskell><br />
three::Num a => Bool -> a<br />
three b = if b then 3::Int else 3::Double<br />
</haskell><br />
<br />
ghc tells me that "Couldn't match type `Int' with `Double'".<br />
<br />
Sorry if the latter questions are misplaced, I just felt they were related.<br />
<br />
--[[User:Dainichi|Dainichi]] 06:53 15 Aug 2011 (UTC)<br />
<br />
<br />
<br />
----<br />
<br />
Oversimplifying the debate somewhat: Those in favour tend to be those who have written Haskell [[Implementations]] and those against tend to be those who have written complex combinator libraries (and hence have hit their collective heads against the restriction all too often). It often boils down to the fact that programmers want to avoid [http://catb.org/esr/jargon/html/L/legalese.html legalese], and language implementors want to avoid [http://catb.org/esr/jargon/html/C/cruft.html cruft].<br />
<br />
In almost all cases, you can get around the restriction by including explicit type declarations. Those who are for the restriction are usually quick to point out that including explicit type declarations is good programming practice anyway. In a few very rare cases, however, you may need to supply a type signature which is not valid Haskell. (Such type signatures require a type system extension such as [[Scoped type variables]].) Unless you're writing some weird combinator libraries, or are in the habit of not writing type declarations, you're unlikely to come across it. Even so, most Haskell [[Implementations]] provide a way to turn the restriction off.<br />
<br />
See also: [http://haskell.org/onlinereport/decls.html#sect4.5.5 Section 4.5.5, Haskell 98 report].<br />
<br />
-- [[Andrew Bromage]]<br />
<br />
Some question or suggestion: As I understand the problem arises from the situation that two different forms of assignment are described by the same notation. There are two forms of assignment, namely the inspection of data structures ("unpacking", "pattern binding") and the definition of functions ("function binding"). Unique examples are:<br />
<br />
<haskell><br />
let f x = y -- function definition<br />
let F x = y -- data structure decomposition<br />
</haskell><br />
<br />
In the first case we have the identifier f starting with lower case. This means this is a function binding. The second assignment starts with F, which must be a constructor. That's why this is a pattern binding. The monomorphism restriction applies only to the pattern binding. I think this was not defined in order to please compiler writers, but has shown to be useful in practice, or am I wrong? But the different handling of these binding types leads to a problem since both types have a common case.<br />
<br />
<haskell><br />
let x = y -- function or pattern binding?<br />
</haskell><br />
<br />
So, what speaks against differentiating the assignments notationally, say<br />
<br />
<haskell><br />
let f x = y -- function definition<br />
let F x <= y -- data structure decomposition<br />
</haskell><br />
<br />
and keep the monomorphism restriction as it is?<br />
<br />
-- [[Henning Thielemann]]<br />
<br />
The problem isn't just pattern bindings, it's that pattern bindings which are typeclass polymorphic are actually function bindings in disguise, since the usual implementation of typeclasses adds parameters to such definitions, to allow the definition to take the typeclass dictionaries involved. Thus, such pattern bindings have different properties with respect to sharing (they're generally less shared than you want). In especially bad cases, without the MR, it is possible to have programs which run exponentially slower without type signatures than when signatures are added. Just distinguishing pattern bindings with a new notation doesn't solve the problem, since they'll have to be converted into function bindings in that case anyway. If you intend to keep the MR, then you don't need to change anything. The issue with the MR is just the fact that it's annoying to have eta-reduction fail in the absence of explicit type signatures, and the fact that it makes otherwise perfectly valid programs fail to compile on speculation that there might be loss of sharing (when there usually isn't, or at least the impact isn't large enough to worry about).<br />
<br />
John Hughes recently advocated the removal of the MR on the Haskell Prime mailing list, and suggested replacing it with two forms of pattern binding: one for call-by-name (polymorphic, not shared), and one for call-by-need (monomorphic, guaranteed shared). This might be similar to what you're suggesting. If you look at it too closely, it seems like a good solution, but the overall impact on Haskell code seems too large to me, to resolve a distinction which it ought to be statically possible to determine.<br />
<br />
I'm of the opinion that it would be better to find a way to restore sharing lost through the typeclass transformation in some way, or else implement typeclasses in an altogether different way which doesn't run into this problem. Additional runtime machinery seems like a likely candidate for this -- the interactions with garbage collection are somewhat subtle, but I think it should be doable. It's also possible to restore the sharing via whole-program analysis, but advocates of separate compilation will probably complain, unless we were to find a mechanism to fix the problem from the object code (and potentially temporaries) at link time.<br />
<br />
:- [[Cale Gibbard]]<br />
<br />
--------------------<br />
I think it'd be useful to collect a set of examples of the Monormorphism Restriction biting people in an unexpected way. This may help to inform the debate over the MR by giving real-life examples. Add more examples here if (an only if) they constitute an unexpected MR-related incident in your life or someone else's. No invented examples! -- [[Simon Peyton Jones]]<br />
<br />
* GHC Trac bug [http://hackage.haskell.org/trac/ghc/ticket/1749 1749]<br />
* In trying to build an editor with undoable actions:<br />
<haskell><br />
class EditAction e a | e -> a where<br />
apply :: a -> e -> a<br />
<br />
data ListAction a = Append a | Remove<br />
<br />
instance EditAction (ListAction a) [a] where<br />
apply list (Append a) = a:list<br />
apply (x:xs) Remove = xs<br />
<br />
-- Apply all the EditActions to the input<br />
--edit :: EditAction e a => a -> [e] -> a -- monomorphism restriction - I have to put this in!<br />
edit = foldl apply<br />
</haskell><br />
<br />
----<br />
Back before forM was in the Control.Monad library, I once spent about 1/2 an hour trying to figure out why my action in the ST monad was having its '<hask>s</hask>' parameter squished to <hask>()</hask>. I tore the code apart for quite a while before discovering that it was that the MR was applying to my definition of <hask>forM</hask>:<br />
<br />
<haskell><br />
forM = flip mapM<br />
</haskell><br />
<br />
----<br />
I recently got tired of typing <hask>print "blah"</hask> in a ghci shell session and tried <hask>let p = print</hask>. Thanks to MR and Haskell defaulting, the type of <hask>p</hask> silently became <hask>() -> IO ()</hask>. No surprise that my new "short" version of print was only capable of printing void values -<br />
<br />
<hask><br />
Prelude> p ()<br />
()<br />
Prelude> p "blah"<br />
<br />
<interactive>:1:2:<br />
Couldn't match expected type `()' against inferred type `[Char]'<br />
In the first argument of `p', namely `"blah"'<br />
In the expression: p "blah"<br />
In the definition of `it': it = p "blah"<br />
</hask><br />
<br />
----<br />
<br />
<haskell><br />
import Graphics.UI.Gtk<br />
import Graphics.UI.Gtk.Glade<br />
<br />
-- xmlGetWidget' :: WidgetClass widget => (GObject -> widget) -> String -> IO widget<br />
xmlGetWidget' = xmlGetWidget undefined<br />
<br />
main :: IO ()<br />
main<br />
= do<br />
initGUI<br />
window <- xmlGetWidget' castToWindow "window1"<br />
button <- xmlGetWidget' castToButton "button1"<br />
widgetShowAll window<br />
mainGUI<br />
</haskell><br />
<br />
If I comment main, I cannot compile this code because of the monomorphism restriction. With main, it'll infer the type:<br />
<br />
<haskell><br />
xmlGetWidget' :: (GObject -> Window) -> String -> IO Window<br />
</haskell><br />
<br />
And give me a type error in the button line. If I uncomment the type signature, it'll work.<br />
<br />
----<br />
<br />
Along the same lines as Simon's question above, does anyone have any real examples of being bitten by the lack of MR? I know what it's for, but I can't really think of any realistic cases when it would be a problem. --pumpkin<br />
<br />
[[Category:Glossary]]<br />
[[Category:Language]]</div>Dainichihttps://wiki.haskell.org/index.php?title=Monomorphism_restriction&diff=18878Monomorphism restriction2008-02-01T23:39:24Z<p>Dainichi: </p>
<hr />
<div>The monomorphism restriction is probably the most annoying and controversial feature of Haskell's type system. All seem to agree that it is evil, but whether or not it is considered a necessary evil depends on who you ask.<br />
<br />
The definition of the restriction is fairly technical, but to a first approximation it means that you often cannot overload a function unless you provide an explicit type signature. In summary:<br />
<br />
<haskell><br />
-- This is allowed<br />
f1 x = show x<br />
<br />
-- This is not allowed<br />
f2 = \x -> show x<br />
<br />
-- ...but this is allowed<br />
f3 :: (Show a) => a -> String<br />
f3 = \x -> show x<br />
<br />
-- This is not allowed<br />
f4 = show<br />
<br />
-- ...but this is allowed<br />
f5 :: (Show a) => a -> String<br />
f5 = show<br />
</haskell><br />
<br />
''Call me dense but why exactly is the first one OK and the second one not? -- anonymous''<br />
<br />
:''The difference is that the first version binds x via a "simple pattern binding" (see section 4.4.3.2 of the Haskell 98 report), and is therefore unrestricted, but the second version does not. The reason why one is allowed and the other is not is that it's considered clear that sharing f1 will not share any computation, and less clear that sharing f2 will have the same effect. If this seems arbitrary, that's because it is. It is difficult to design an objective rule which disallows subjective unexpected behaviour. Some people are going to fall foul of the rule even though they're doing quite reasonable things. -- [[Andrew Bromage]]''<br />
<br />
Arguably, these should all be equivalent, but thanks to the monomorphism restriction, they are not.<br />
<br />
So why is the restriction imposed? The reasoning behind it is fairly subtle, and is fully explained in the [http://haskell.org/onlinereport/ Haskell 98 report]. Basically, it solves one practical problem (without the restriction, there would be some ambiguous types) and one semantic problem (without the restriction, there would be some repeated evaluation where a programmer might expect the evaluation to be shared). Those who are for the restriction argue that these cases should be dealt with correctly. Those who are against the restriction argue that these cases are so rare that it's not worth sacrificing the type-independence of eta reduction.<br />
<br />
:An example, from [http://research.microsoft.com/~simonpj/papers/history-of-haskell/index.htm A History of Haskell]: Consider the <code>genericLength</code> function, from <code>Data.List</code><br />
<br />
:<haskell><br />
genericLength :: Num a => [b] -> a<br />
</haskell><br />
<br />
:And consider the function:<br />
<br />
<haskell><br />
f xs = (len,len)<br />
where<br />
len = genericLength xs<br />
</haskell><br />
<br />
:<code>len</code> has type <code>Num a => a</code> and, without the monomorphism restriction, it could be computed ''twice''. --[[User:ARG|ARG]]<br />
<br />
''It is not clear to me how this whole thing about being computed once or twice works. Isn't type checking/inference something that happens at compile-time and shouldn't have any effect on what happens at run-time, as long as the typecheck passes? --dainichi''<br />
<br />
Oversimplifying the debate somewhat: Those in favour tend to be those who have written Haskell [[Implementations]] and those against tend to be those who have written complex combinator libraries (and hence have hit their collective heads against the restriction all too often). It often boils down to the fact that programmers want to avoid [http://catb.org/esr/jargon/html/L/legalese.html legalese], and language implementors want to avoid [http://catb.org/esr/jargon/html/C/cruft.html cruft].<br />
<br />
In almost all cases, you can get around the restriction by including explicit type declarations. Those who are for the restriction are usually quick to point out that including explicit type declarations is good programming practice anyway. In a few very rare cases, however, you may need to supply a type signature which is not valid Haskell. (Such type signatures require a type system extension such as [[ScopedTypeVariables]].) Unless you're writing some weird combinator libraries, or are in the habit of not writing type declarations, you're unlikely to come across it. Even so, most Haskell [[Implementations]] provide a way to turn the restriction off.<br />
<br />
See also: [http://haskell.org/onlinereport/decls.html#sect4.5.5 Section 4.5.5, Haskell 98 report].<br />
<br />
-- [[Andrew Bromage]]<br />
<br />
Some question or suggestion: As I understand the problem arises from the situation that two different forms of assignment are described by the same notation. There are two forms of assignment, namely the inspection of data structures ("unpacking", "pattern binding") and the definition of functions ("function binding"). Unique examples are:<br />
<br />
<haskell><br />
let f x = y -- function definition<br />
let F x = y -- data structure decomposition<br />
</haskell><br />
<br />
In the first case we have the identifier f starting with lower case. This means this is a function binding. The second assignment starts with F, which must be a constructor. That's why this is a pattern binding. The monomorphism restriction applies only to the pattern binding. I think this was not defined in order to please compiler writers, but has shown to be useful in practice, or am I wrong? But the different handling of these binding types leads to a problem since both types have a common case.<br />
<br />
<haskell><br />
let x = y -- function or pattern binding?<br />
</haskell><br />
<br />
So, what speaks against differentiating the assignments notationally, say<br />
<br />
<haskell><br />
let f x = y -- function definition<br />
let F x <= y -- data structure decomposition<br />
</haskell><br />
<br />
and keep the monomorphism restriction as it is?<br />
<br />
-- [[Henning Thielemann]]<br />
<br />
The problem isn't just pattern bindings, it's that pattern bindings which are typeclass polymorphic are actually function bindings in disguise, since the usual implementation of typeclasses adds parameters to such definitions, to allow the definition to take the typeclass dictionaries involved. Thus, such pattern bindings have different properties with respect to sharing (they're generally less shared than you want). In especially bad cases, without the MR, it is possible to have programs which run exponentially slower without type signatures than when signatures are added. Just distinguishing pattern bindings with a new notation doesn't solve the problem, since they'll have to be converted into function bindings in that case anyway. If you intend to keep the MR, then you don't need to change anything. The issue with the MR is just the fact that it's annoying to have eta-reduction fail in the absence of explicit type signatures, and the fact that it makes otherwise perfectly valid programs fail to compile on speculation that there might be loss of sharing (when there usually isn't, or at least the impact isn't large enough to worry about).<br />
<br />
John Hughes recently advocated the removal of the MR on the Haskell Prime mailing list, and suggested replacing it with two forms of pattern binding: one for call-by-name (polymorphic, not shared), and one for call-by-need (monomorphic, guaranteed shared). This might be similar to what you're suggesting. If you look at it too closely, it seems like a good solution, but the overall impact on Haskell code seems too large to me, to resolve a distinction which it ought to be statically possible to determine.<br />
<br />
I'm of the opinion that it would be better to find a way to restore sharing lost through the typeclass transformation in some way, or else implement typeclasses in an altogether different way which doesn't run into this problem. Additional runtime machinery seems like a likely candidate for this -- the interactions with garbage collection are somewhat subtle, but I think it should be doable. It's also possible to restore the sharing via whole-program analysis, but advocates of separate compilation will probably complain, unless we were to find a mechanism to fix the problem from the object code (and potentially temporaries) at link time.<br />
<br />
:- [[Cale Gibbard]]<br />
<br />
--------------------<br />
I think it'd be useful to collect a set of examples of the Monormorphism Restriction biting people in an unexpected way. This may help to inform the debate over the MR by giving real-life examples. Add more examples here if (an only if) they constitute an unexpected MR-related incident in your life or someone else's. No invented examples! -- [[Simon Peyton Jones]]<br />
<br />
* GHC Trac bug [http://hackage.haskell.org/trac/ghc/ticket/1749 1749]<br />
* In trying to build an editor with undoable actions:<br />
<haskell><br />
class EditAction e a | e -> a where<br />
apply :: a -> e -> a<br />
<br />
data ListAction a = Append a | Remove<br />
<br />
instance EditAction (ListAction a) [a] where<br />
apply list (Append a) = a:list<br />
apply (x:xs) Remove = xs<br />
<br />
-- Apply all the EditActions to the input<br />
--edit :: EditAction e a => a -> [e] -> a -- monomorphism restriction - I have to put this in!<br />
edit = foldl apply<br />
</haskell><br />
<br />
[[Category:Glossary]]<br />
[[Category:Language]]</div>Dainichi