https://wiki.haskell.org/api.php?action=feedcontributions&user=Drostie&feedformat=atomHaskellWiki - User contributions [en]2020-06-01T17:03:33ZUser contributionsMediaWiki 1.27.4https://wiki.haskell.org/index.php?title=Monomorphism_restriction&diff=59514Monomorphism restriction2015-03-10T16:41:22Z<p>Drostie: This page is so important that it deserves a more conversational introductory paragraph.</p>
<hr />
<div>The "monomorphism restriction" is a counter-intuitive rule in Haskell type inference. If you forget to provide a type signature, sometimes this rule will fill the free type variables with specific types using "type defaulting" rules. The resulting type signature is always less polymorphic than you'd expect, so often this results in the compiler throwing type errors at you in situations where you expected it to infer a perfectly sane type for a polymorphic expression.<br />
<br />
A simple example is <code>plus = (+)</code>. Without an explicit signature for <code>plus</code>, the compiler will not infer the type <code>(+) :: (Num a) => a -> a -> a</code> for `plus`, but will apply defaulting rules to specify <code>plus :: Integer -> Integer -> Integer</code>. When applied to <code>plus 3.5 2.7</code>, GHCi will then produce the somewhat-misleading-looking error, <code>No instance for (Fractional Integer) arising from the literal ‘3.5’</code>. <br />
<br />
The restriction is turned on by default in compiled modules, and turned off by default at the GHCi prompt (since GHC 7.8.1). You can override these defaults by using the MonomorphismRestriction and NoMonomorphismRestriction [[Language_Pragmas|language pragmas]].<br />
<br />
The exact definition of the restriction is fairly technical;<br />
it can be found in<br />
[http://www.haskell.org/onlinereport/haskell2010/haskellch4.html#x10-930004.5.5 section 4.5.5 of the Haskell 2010 Report].<br />
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 yields f1 :: (Show x) => x -> String<br />
f1 x = show x<br />
<br />
-- But this doesn't. Instead, f2 :: () -> String<br />
f2 = \x -> show x<br />
<br />
-- ...but we can fix that with an explicit type signature.<br />
f3 :: (Show a) => a -> String<br />
f3 = \x -> show x<br />
<br />
-- Similarly this produces () -> String<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 "function binding" (see<br />
[http://www.haskell.org/onlinereport/haskell2010/haskellch4.html#x10-830004.4.3 section 4.4.3 of the Haskell 2010 Report]),<br />
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 />
The monomorphism restriction is probably the most annoying and controversial feature of Haskell's type system.<br />
All seem to agree that it is evil - it is commonly called "The Dreaded Monomorphism Restriction" - but whether or not it is considered a necessary evil depends on who you ask.<br />
<br />
So why is the restriction imposed? The reasoning behind it is fairly subtle, and is fully explained in<br />
[http://www.haskell.org/onlinereport/haskell2010/haskellch4.html#x10-930004.5.5 section 4.5.5 of the Haskell 2010 Report].<br />
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<br />
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 />
(This introductory section slightly expanded and re-arranged by [[User:YitzGale|YitzGale]].)<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 />
The following compiles for me on ghc 7.4.1:<br />
<br />
<haskell><br />
module Main where<br />
import Data.List<br />
<br />
main = putStrLn $ show (f [])<br />
<br />
f xs = (len,len)<br />
where<br />
len = genericLength xs<br />
</haskell><br />
<br />
If i add <code>f2 = \x -> show x</code>, compilation fails, demonstrating that i still have the monomorphism restriction enabled. <br />
<br />
This is not due to type inference from the putStrLn $ show (f []) doing anything; in fact, this compiles fine:<br />
<br />
<br />
<haskell><br />
module Main where<br />
import Data.List<br />
<br />
main = putStrLn ""<br />
<br />
f xs = (len,len)<br />
where<br />
len = genericLength xs<br />
<br />
-- f2 = \x -> show x <br />
</haskell><br />
<br />
whereas this fails to compile:<br />
<br />
<haskell><br />
module Main where<br />
import Data.List<br />
<br />
main = putStrLn ""<br />
<br />
--f xs = (len,len)<br />
-- where<br />
-- len = genericLength xs<br />
<br />
f2 = \x -> show x<br />
</haskell><br />
<br />
Why does the example from History of Haskell not fail? -- [[BayleShanks]] <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 />
I wasn't expecting the following to fail...<br />
<br />
<haskell><br />
square :: (Num a) => a -> a <br />
square x = x * x <br />
dx = 0.0000001<br />
deriv1 :: (Fractional a) => (a -> a) -> (a -> a)<br />
deriv1 g = (\x -> ((g (x + 2) - (g x)) / dx )) <br />
main = printf "res==%g %g\n" (square 5.12::Double) ((deriv1 square) 2::Float)<br />
</haskell><br />
<br />
and for this to work.<br />
<br />
<haskell><br />
square :: (Num a) => a -> a <br />
square x = x * x <br />
dx = 0.0000001<br />
deriv1 :: (Fractional a) => (a -> a) -> (a -> a)<br />
deriv1 g = (\x -> ((g (x + 2) - (g x)) / 0.0000001 )) <br />
main = printf "res==%g %g\n" (square 5.12::Double) ((deriv1 square) 2::Float)<br />
</haskell><br />
<br />
The fix was to add<br />
<br />
<haskell><br />
dx :: Fractional a => a<br />
</haskell><br />
<br />
--Harry<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>Drostiehttps://wiki.haskell.org/index.php?title=User:Drostie&diff=58996User:Drostie2014-10-14T15:35:14Z<p>Drostie: change headings to Wikipedia syntax rather than Markdown.</p>
<hr />
<div>= CR Drost =<br />
<br />
Hi! My name is Chris. I've got a Master's in physics with a lot of interests in programming language design and software development. Here are some of them:<br />
<br />
== Mathematics ==<br />
One of my primary interests in Haskell is phrasing standard mathematics in its syntax so as to make equations unambiguous, which I feel might make physics a little simpler for college students, since they don't have to "decode" what was meant. There was a nice book called "the Structure and Interpretation of Classical Mechanics" in a similar vein.<br />
<br />
== In-memory Revision Control ==<br />
I'm also interested in "lifting" Darcs, or something like it, out of the IO monad so that you have a revision control system in memory which just happens to be data-serializable. I think that this is the key to bringing a lot of awesome software closer-to-reach for amateur developers, for example Google-Docs-style collaboration, or a document which has a built-in RCS showing you all of the edits that have been made. <br />
<br />
== Spreadsheets done right ==<br />
The idioms that people use with spreadsheets are vastly more constrained than what those spreadsheets actually are capable of; and when people don't use those idioms you get these corporate Excel monsters which are buggy and hard to fix. A good lazy spreadsheet language would be able to rectify this explicitly. Haskell with applicatives would make a great fit for that; we just need the GUI to be relatively awesome, and we'd need to get copy/paste right.<br />
<br />
== Subtyped metadata language ==<br />
I'm reasonably sure that you can use subtyping to do arbitrary metadata (which is close to the way "mixins" work) with a type system. My goal there is to (a) make a programming language which is effortless at expressing metadata; (b) use that language's parse trees as its own data structure, so that every data structure also has metadata associated with it; (c) write the subtype-checker in the language itself; (d) offer a compiler which by default type-checks, but where this can easily be turned off.<br />
<br />
If I were really optimistic I would then say that maybe we could support a really generic polymorphism, where technically 1 is ''defined'' as the Church number but there is metadata which tells the compiler that it's ''okay'' to store it as a bignum, or a long, or an int, or a short, or a byte, or a bit. The idea is that the language would entertain the notion of multiple perspectives on the same data, and would be able to lazily autoconvert between them ("You wanted to compute a multiplication? Okay -- switching to a decimal representation. Oh, now you want to repeat a function that many times? I've got a Church numeral for you...").<br />
<br />
With a dynamically pluggable syntax, ideally we'd be able to translate the abstract parse trees (which are just data structures) from language to language, saying "here is the Python translation of what you wrote, here is the Haskell translation of what you wrote," etc. Then we tell the Pythonistas that they've secretly been programming in the new language all along, and here's a useful subtype-checker which they can use to make their code better -- oh, and if they want to use our libraries, that's cool too.</div>Drostiehttps://wiki.haskell.org/index.php?title=User:Drostie&diff=58995User:Drostie2014-10-14T15:34:09Z<p>Drostie: Created page with "# CR Drost Hi! My name is Chris. I've got a Master's in physics with a lot of interests in programming language design and software development. Here are some of them: ## Ma..."</p>
<hr />
<div># CR Drost<br />
<br />
Hi! My name is Chris. I've got a Master's in physics with a lot of interests in programming language design and software development. Here are some of them:<br />
<br />
## Mathematics<br />
One of my primary interests in Haskell is phrasing standard mathematics in its syntax so as to make equations unambiguous, which I feel might make physics a little simpler for college students, since they don't have to "decode" what was meant. There was a nice book called "the Structure and Interpretation of Classical Mechanics" in a similar vein.<br />
<br />
## In-memory Revision Control<br />
I'm also interested in "lifting" Darcs, or something like it, out of the IO monad so that you have a revision control system in memory which just happens to be data-serializable. I think that this is the key to bringing a lot of awesome software closer-to-reach for amateur developers, for example Google-Docs-style collaboration, or a document which has a built-in RCS showing you all of the edits that have been made. <br />
<br />
## Spreadsheets done right<br />
The idioms that people use with spreadsheets are vastly more constrained than what those spreadsheets actually are capable of; and when people don't use those idioms you get these corporate Excel monsters which are buggy and hard to fix. A good lazy spreadsheet language would be able to rectify this explicitly. Haskell with applicatives would make a great fit for that; we just need the GUI to be relatively awesome, and we'd need to get copy/paste right.<br />
<br />
## Subtyped metadata language<br />
I'm reasonably sure that you can use subtyping to do arbitrary metadata (which is close to the way "mixins" work) with a type system. My goal there is to (a) make a programming language which is effortless at expressing metadata; (b) use that language's parse trees as its own data structure, so that every data structure also has metadata associated with it; (c) write the subtype-checker in the language itself; (d) offer a compiler which by default type-checks, but where this can easily be turned off.<br />
<br />
If I were really optimistic I would then say that maybe we could support a really generic polymorphism, where technically 1 is ''defined'' as the Church number but there is metadata which tells the compiler that it's ''okay'' to store it as a bignum, or a long, or an int, or a short, or a byte, or a bit. The idea is that the language would entertain the notion of multiple perspectives on the same data, and would be able to lazily autoconvert between them ("You wanted to compute a multiplication? Okay -- switching to a decimal representation. Oh, now you want to repeat a function that many times? I've got a Church numeral for you...").<br />
<br />
With a dynamically pluggable syntax, ideally we'd be able to translate the abstract parse trees (which are just data structures) from language to language, saying "here is the Python translation of what you wrote, here is the Haskell translation of what you wrote," etc. Then we tell the Pythonistas that they've secretly been programming in the new language all along, and here's a useful subtype-checker which they can use to make their code better -- oh, and if they want to use our libraries, that's cool too.</div>Drostie