Skip to content

Changes

Page history
Edit NoMonomorphismRestriction authored by ian@well-typed.com's avatar ian@well-typed.com
Hide whitespace changes
Inline Side-by-side
no-monomorphism-restriction.md
View page @ edce1157
# Proposal: NoMonomorphismRestriction
<table><tr><th> Ticket </th>
<th>[\#131](https://gitlab.haskell.org//haskell/prime/issues/131)</th></tr>
<th> [\#131](https://gitlab.haskell.org//haskell/prime/issues/131)
</th></tr>
<tr><th> Dependencies </th>
<th> none
</th></tr>
......@@ -9,8 +11,10 @@
<th> MonoPatBinds, alternative monomorphism restriction replacement options
</th></tr></table>
## Compiler support
<table><tr><th> GHC </th>
<th> full (`-XNoMonomorphismRestriction -XNoMonoPatBinds`)
</th></tr>
......@@ -30,17 +34,22 @@
<th> full (`-XNoMonomorphismRestriction -XNoMonoPatBinds`)
</th></tr></table>
## Summary
Remove the monomorphism restriction. Bindings are polymorphic unless constrained by a type signature.
## Description
The monomorphism is a frequent source of confusion to Haskell programmers the first times they are caught by it.
It is widely regarded as an ugly part of the language. Arguments for removing it include:
- Removes a wart from the language
- Many implementations don't implement it, or implement it incorrectly, and users haven't found any significant problems as a result
- "As much polymorphism as possible" is in the spirit of Haskell - it is strange to limit polymorphism for performance reasons (indeed, this is arguably a poor compromise)
......@@ -51,91 +60,113 @@ It is widely regarded as an ugly part of the language. Arguments for removing it
There have been 4 other suggestions related to the monomorphism restriction:
[Add a monomorphic \`:=\` operator](monomorphism-restriction/monomorphic-binding-operator)
[Use redundant parens to indicate a monomorphic binding](monomorphism-restriction/monomorphic-binding-syntax)
>
>
> Both of these imply removing the monomorphism restriction for normal bindings.
> They would be separate proposals that depend on this one.
> While it would be nice, if we decide to implement one of these, to do so at the same time as implementing
> NoMonomorphismRestriction, it is not necessary.
>
>
[Enable the monomorphism restriction on a per module basis](monomorphism-restriction/optional)
>
>
> This is an alternative to this proposal. If the monomorphism restriction was on by default, then it would not
> solve the confusion problems, as people unfamiliar with it would not know to turn it off. If it was off by default,
> then people would need to realise that they need to turn it on, at which point adding type signatures instead
> would make it clearer what is going on.
>
>
[Bindings are monomorphic unless constrained by a type signature](monomorphism-restriction/monomorphic-variable-and-pattern-bindings)
>
> Seems against the spirit of Haskell. But see [ Let should not be generalised](http://research.microsoft.com/~simonpj/papers/constraints/index.htm) which argues the case for this approach, at least for nested bindings.
[Bindings are monomorphic unless constrained by a type signature](monomorphism-restriction/monomorphic-variable-and-pattern-bindings)
## Opposition
>
>
> Seems against the spirit of Haskell.
>
>
In the discussion on the mailing list, Simon Peyton Jones wrote:
## References
As many of you will know I am now leaning
strongly towards doing no generalisation whatsoever on nested bindings. See
[ http://research.microsoft.com/\~simonpj/papers/constraints/index.htm](http://research.microsoft.com/~simonpj/papers/constraints/index.htm)
None.
So I'd cut the cake differently:
- top level: generalise, no monomorphism restriction
- nested: do not generalise, monomorphism restriction for every binding
## Report Delta
## References
None.
In [ Section 4.5.5](http://haskell.org/onlinereport/decls.html#sect4.5.5) remove:
## Report Delta
In [ Section 4.5.5](http://haskell.org/onlinereport/decls.html#sect4.5.5) remove:
**The Monomorphism Restriction**
Haskell places certain extra restrictions on the generalization step, beyond the standard Hindley-Milner restriction described above, which further reduces polymorphism in particular cases.
The monomorphism restriction depends on the binding syntax of a variable. Recall that a variable is bound by either a function binding or a pattern binding, and that a simple pattern binding is a pattern binding in which the pattern consists of only a single variable (Section 4.4.3).
The following two rules define the monomorphism restriction:
**The monomorphism restriction**
Rule 1.
We say that a given declaration group is unrestricted if and only if:
(a): every variable in the group is bound by a function binding or a simple pattern binding (Section 4.4.3.2), and
(b): an explicit type signature is given for every variable in the group that is bound by simple pattern binding.
The usual Hindley-Milner restriction on polymorphism is that only type variables that do not occur free in the environment may be generalized. In addition, the constrained type variables of a restricted declaration group may not be generalized in the generalization step for that group. (Recall that a type variable is constrained if it must belong to some type class; see Section 4.5.2.)
Rule 2.
Any monomorphic type variables that remain when type inference for an entire module is complete, are considered ambiguous, and are resolved to particular types using the defaulting rules (Section 4.3.4).
**Motivation**
Rule 1 is required for two reasons, both of which are fairly subtle.
- Rule 1 prevents computations from being unexpectedly repeated. For example, `genericLength` is a standard function (in library `List`) whose type is given by
```wiki
......@@ -167,19 +198,26 @@ Rule 1 is required for two reasons, both of which are fairly subtle.
Without Rule 1, `n` would be assigned the type `forall a. Read a =>a` and `s` the type `forall a. Read a =>String`. The latter is an invalid type, because it is inherently ambiguous. It is not possible to determine at what overloading to use `s`, nor can this be solved by adding a type signature for `s`. Hence, when non-simple pattern bindings are used (Section 4.4.3.2), the types inferred are always monomorphic in their constrained type variables, irrespective of whether a type signature is provided. In this case, both `n` and `s` are monomorphic in `a`.
>
> >
> >
> > The same constraint applies to pattern-bound functions. For example, in
> >
> >
> > ```wiki
> > (f,g) = ((+),(-))
> > ```
> >
> >
> > both `f` and `g` are monomorphic regardless of any type signatures supplied for `f` or `g`.
> >
> >
>
Rule 2 is required because there is no way to enforce monomorphic use of an exported binding, except by performing type inference on modules outside the current module. Rule 2 states that the exact types of all the variables bound in a module must be determined by that module alone, and not by any modules that import it.
```wiki
module M1(len1) where
default( Int, Double )
......@@ -194,13 +232,18 @@ Rule 2 is required because there is no way to enforce monomorphic use of an expo
When type inference on module `M1` is complete, `len1` has the monomorphic type `Num a => a` (by Rule 1). Rule 2 now states that the monomorphic type variable `a` is ambiguous, and must be resolved using the defaulting rules of Section 4.3.4. Hence, `len1` gets type `Int`, and its use in `len2` is type-incorrect. (If the above code is actually what is wanted, a type signature on `len1` would solve the problem.)
This issue does not arise for nested bindings, because their entire scope is visible to the compiler.
**Consequences**
The monomorphism rule has a number of consequences for the programmer. Anything defined with function syntax usually generalizes as a function is expected to. Thus in
```wiki
f x y = x+y
```
......@@ -208,6 +251,7 @@ The monomorphism rule has a number of consequences for the programmer. Anything
the function `f` may be used at any overloading in class `Num`. There is no danger of recomputation here. However, the same function defined with pattern syntax:
```wiki
f = \x -> \y -> x+y
```
......@@ -215,6 +259,7 @@ the function `f` may be used at any overloading in class `Num`. There is no dang
requires a type signature if `f` is to be fully overloaded. Many functions are most naturally defined using simple pattern bindings; the user must be careful to affix these with type signatures to retain full overloading. The standard prelude contains many examples of this:
```wiki
sum :: (Num a) => [a] -> a
sum = foldl (+) 0
......@@ -223,6 +268,7 @@ requires a type signature if `f` is to be fully overloaded. Many functions are m
Rule 1 applies to both top-level and nested definitions. Consider
```wiki
module M where
len1 = genericLength "Hello"
......@@ -233,13 +279,24 @@ Rule 1 applies to both top-level and nested definitions. Consider
Here, type inference finds that `len1` has the monomorphic type `(Num a => a)`; and the type variable `a` is resolved to `Rational` when performing type inference on `len2`.
In [ Section 5](http://haskell.org/onlinereport/modules.html#sect5) replace:
(There are two minor exceptions to this statement. First, default declarations scope over a single module (Section 4.3.4). Second, Rule 2 of the monomorphism restriction (Section 4.5.5) is affected by module boundaries. )
with:
(There is a minor exception to this statement: Default declarations scope over a single module (Section 4.3.4).)