haskell - What is the monomorphism restriction? -

i'm puzzled how haskell compiler infers types less polymorphic i'd expect, example when using point-free definitions.

it seems issue "monomorphism restriction", on default on older versions of compiler.

consider following haskell program:

{-# language monomorphismrestriction #-}  import data.list(sortby)  plus = (+) plus' x = (+ x)  sort = sortby compare  main =   print $ plus' 1.0 2.0   print $ plus 1.0 2.0   print $ sort [3, 1, 2] 

if compile ghc obtain no erros , output of executable is:

3.0 3.0 [1,2,3] 

if change main body to:

main =   print $ plus' 1.0 2.0   print $ plus (1 :: int) 2   print $ sort [3, 1, 2] 

i no compile time errors , output becomes:

3.0 3 [1,2,3] 

as expected. if try change to:

main =   print $ plus' 1.0 2.0   print $ plus (1 :: int) 2   print $ plus 1.0 2.0   print $ sort [3, 1, 2] 

i type error:

test.hs:13:16:     no instance (fractional int) arising literal ‘1.0’     in first argument of ‘plus’, namely ‘1.0’     in second argument of ‘($)’, namely ‘plus 1.0 2.0’     in stmt of 'do' block: print $ plus 1.0 2.0 

the same happens when trying call sort twice different types:

main =   print $ plus' 1.0 2.0   print $ plus 1.0 2.0   print $ sort [3, 1, 2]   print $ sort "cba" 

produces following error:

test.hs:14:17:     no instance (num char) arising literal ‘3’     in expression: 3     in first argument of ‘sort’, namely ‘[3, 1, 2]’     in second argument of ‘($)’, namely ‘sort [3, 1, 2]’ 

• why ghc think plus isn't polymorphic , requires int argument? reference int in an application of plus, how can matter when definition polymorphic?
• why ghc think sort requires num char instance?

moreover if try place function definitions own module, in:

{-# language monomorphismrestriction #-}  module testmono  import data.list(sortby)  plus = (+) plus' x = (+ x)  sort = sortby compare 

i following error when compiling:

testmono.hs:10:15:     no instance (ord a0) arising use of ‘compare’     type variable ‘a0’ ambiguous     relevant bindings include       sort :: [a0] -> [a0] (bound @ testmono.hs:10:1)     note: there several potential instances:       instance integral => ord (ghc.real.ratio a)         -- defined in ‘ghc.real’       instance ord () -- defined in ‘ghc.classes’       instance (ord a, ord b) => ord (a, b) -- defined in ‘ghc.classes’       ...plus 23 others     in first argument of ‘sortby’, namely ‘compare’     in expression: sortby compare     in equation ‘sort’: sort = sortby compare 

• why isn't ghc able use polymorphic type ord => [a] -> [a] sort?
• and why ghc treat plus , plus' differently? plus should have polymorphic type num => -> -> a , don't see how different type of sort , yet sort raises error.

last thing: if comment definition of sort file compiles. if try load ghci , check types get:

*testmono> :t plus plus :: integer -> integer -> integer *testmono> :t plus' plus' :: num => -> -> 

why isn't type plus polymorphic?

---

^{canonical question monomorphism restriction in haskell discussed in the meta question.}

what monomorphism restriction?

the monomorphism restriction stated haskell wiki is:

a counter-intuitive rule in haskell type inference. if forget provide type signature, rule fill free type variables specific types using "type defaulting" rules.

what means that, in circumstances, if type ambiguous (i.e. polymorphic) compiler choose instantiate type not ambiguous.

how fix it?

first of can explicitly provide type signature , avoid triggering of restriction:

plus :: num => -> -> plus = (+)    -- okay!  -- runs as: prelude> plus 1.0 1 2.0 

alternatively, if defining function, can avoid point-free style, , example write:

plus x y = x + y 

turning off

it possible turn off restriction don't have code fix it. behaviour controlled 2 extensions: monomorphismrestriction enable (which default) while nomonomorphismrestriction disable it.

you can put following line @ top of file:

{-# language nomonomorphismrestriction #-} 

if using ghci can enable extension using :set command:

prelude> :set -xnomonomorphismrestriction 

you can tell ghc enable extension command line:

ghc ... -xnomonomorphismrestriction 

note: should prefer first option on choosing extension via command-line options.

refer ghc's page explanation of , other extensions.

a complete explanation

i'll try summarize below need know understand monomorphism restriction is, why introduced , how behaves.

an example

take following trivial definition:

plus = (+) 

you'd think able replace every occurrence of + plus. in particular since (+) :: num => -> -> a you'd expect have plus :: num => -> -> a.

unfortunately not case. example in try following in ghci:

prelude> let plus = (+) prelude> plus 1.0 1 

we following output:

<interactive>:4:6:     no instance (fractional integer) arising literal ‘1.0’     in first argument of ‘plus’, namely ‘1.0’     in expression: plus 1.0 1     in equation ‘it’: = plus 1.0 1 

^{you may need :set -xmonomorphismrestriction in newer ghci versions.}

and in fact can see type of plus not expect:

prelude> :t plus plus :: integer -> integer -> integer 

what happened compiler saw plus had type num => -> -> a, polymorphic type. happens above definition falls under rules i'll explain later , decided make type monomorphic defaulting type variable a. default integer can see.

note if try compile above code using ghc won't errors. due how ghci handles (and must handle) interactive definitions. every statement entered in ghci must completely type checked before following considered; in other words it's if every statement in separate module. later i'll explain why matter.

some other example

consider following definitions:

f1 x = show x  f2 = \x -> show x  f3 :: (show a) => -> string f3 = \x -> show x  f4 = show  f5 :: (show a) => -> string f5 = show 

we'd expect these functions behave in same way , have same type, i.e. type of show: show => -> string.

yet when compiling above definitions obtain following errors:

test.hs:3:12:     no instance (show a1) arising use of ‘show’     type variable ‘a1’ ambiguous     relevant bindings include       x :: a1 (bound @ blah.hs:3:7)       f2 :: a1 -> string (bound @ blah.hs:3:1)     note: there several potential instances:       instance show double -- defined in ‘ghc.float’       instance show float -- defined in ‘ghc.float’       instance (integral a, show a) => show (ghc.real.ratio a)         -- defined in ‘ghc.real’       ...plus 24 others     in expression: show x     in expression: \ x -> show x     in equation ‘f2’: f2 = \ x -> show x  test.hs:8:6:     no instance (show a0) arising use of ‘show’     type variable ‘a0’ ambiguous     relevant bindings include f4 :: a0 -> string (bound @ blah.hs:8:1)     note: there several potential instances:       instance show double -- defined in ‘ghc.float’       instance show float -- defined in ‘ghc.float’       instance (integral a, show a) => show (ghc.real.ratio a)         -- defined in ‘ghc.real’       ...plus 24 others     in expression: show     in equation ‘f4’: f4 = show 

so f2 , f4 don't compile. when trying define these function in ghci no errors, type f2 , f4 () -> string!

monomorphism restriction makes f2 , f4 require monomorphic type, , different behaviour bewteen ghc , ghci due different defaulting rules.

when happen?

in haskell, defined report, there two distinct type of bindings. function bindings , pattern bindings. function binding nothing else definition of function:

f x = x + 1 

note syntax is:

<identifier> arg1 arg2 ... argn = expr 

^{modulo guards , where declarations. don't matter.}

where there must at least 1 argument.

a pattern binding declaration of form:

<pattern> = expr 

^{again, modulo guards.}

note variables patterns, binding:

plus = (+) 

is pattern binding. it's binding pattern plus (a variable) expression (+).

when pattern binding consists of variable name it's called simple pattern binding.

the monomorphism restriction applies simple pattern bindings!

well, formally should that:

a declaration group minimal set of mutually dependent bindings.

^{section 4.5.1 of report.}

and (section 4.5.5 of report):

a given declaration group unrestricted if , if:

1. every variable in group bound function binding (e.g. f x = x) or simple pattern binding (e.g. plus = (+); section 4.4.3.2 ), and

2. an explicit type signature given every variable in group bound simple pattern binding. (e.g. plus :: num => -> -> a; plus = (+)).

^{examples added me.}

so restricted declaration group group where, either there non-simple pattern bindings (e.g. (x:xs) = f something or (f, g) = ((+), (-))) or there simple pattern binding without type signature (as in plus = (+)).

the monomorphism restriction affects restricted declaration groups.

most of time don't define mutual recursive functions , hence declaration group becomes a binding.

what do?

the monomorphism restriction described 2 rules in section 4.5.5 of report.

first rule

the usual hindley-milner restriction on polymorphism type variables not occur free in environment may generalized. in addition, the constrained type variables of restricted declaration group may not generalized in generalization step group. (recall type variable constrained if must belong type class; see section 4.5.2 .)

the highlighted part monomorphism restriction introduces. says if type polymorphic (i.e. contain type variable) and type variable constrained (i.e. has class constraint on it: e.g. type num => -> -> a polymorphic because contains a , contrained because a has constraint num on it.) then cannot generalized.

in simple words not generalizing means uses of function plus may change type.

if had definitions:

plus = (+)  x :: integer x = plus 1 2  y :: double y = plus 1.0 2 

then you'd type error. because when compiler sees plus called on integer in declaration of x unify type variable a integer , hence type of plus becomes:

integer -> integer -> integer 

but then, when type check definition of y, see plus applied double argument, , types don't match.

note can still use plus without getting error:

plus = (+) x = plus 1.0 2 

in case type of plus first inferred num => -> -> a use in definition of x, 1.0 requires fractional constraint, change fractional => -> -> a.

rationale

the report says:

rule 1 required 2 reasons, both of subtle.

• rule 1 prevents computations being unexpectedly repeated. example, genericlength standard function (in library data.list) type given by

  genericlength :: num => [b] -> 

  now consider following expression:

  let len = genericlength xs in (len, len) 

  it looks if len should computed once, without rule 1 might computed twice, once @ each of 2 different overloadings. if programmer wish computation repeated, explicit type signature may added:

  let len :: num =>     len = genericlength xs in (len, len) 

for point example wiki is, believe, clearer. consider function:

f xs = (len, len)       len = genericlength xs 

if len polymorphic type of f be:

f :: num a, num b => [c] -> (a, b) 

so 2 elements of tuple (len, len) different values! means computation done genericlength must repeated obtain 2 different values.

the rationale here is: code contains one function call, not introducing rule produce two hidden function calls, counter intuitive.

with monomorphism restriction type of f becomes:

f :: num => [b] -> (a, a) 

in way there no need perform computation multiple times.

• rule 1 prevents ambiguity. example, consider declaration group

  [(n,s)] = reads t

  recall reads standard function type given signature

  reads :: (read a) => string -> [(a,string)]

  without rule 1, n assigned type ∀ a. read ⇒ a , s type ∀ a. read ⇒ string. latter invalid type, because inherently ambiguous. not possible determine @ overloading use s, nor can solved adding type signature s. hence, when non-simple pattern bindings used (section 4.4.3.2 ), types inferred monomorphic in constrained type variables, irrespective of whether type signature provided. in case, both n , s monomorphic in a.

well, believe example self-explanatory. there situations when not applying rule results in type ambiguity.

if disable extension suggest above will type error when trying compile above declaration. isn't problem: know when using read have somehow tell compiler type should try parse...

second rule

2. any monomorphic type variables remain when type inference entire module complete, considered ambiguous, , resolved particular types using defaulting rules (section 4.3.4 ).

this means that. if have usual definition:

plus = (+) 

this have type num => -> -> a a monomorphic type variable due rule 1 described above. once whole module inferred compiler choose type replace a according defaulting rules.

the final result is: plus :: integer -> integer -> integer.

note done after whole module inferred.

this means if have following declarations:

plus = (+)  x = plus 1.0 2.0 

inside module, before type defaulting type of plus be: fractional => -> -> a (see rule 1 why happens). @ point, following defaulting rules, a replaced double , have plus :: double -> double -> double , x :: double.

defaulting

as stated before there exist defaulting rules, described in section 4.3.4 of report, inferencer can adopt , replace polymorphic type monomorphic one. happens whenever type ambiguous.

for example in expression:

let x = read "<something>" in show x 

here expression ambiguous because types show , read are:

show :: show => -> string read :: read => string -> 

so x has type read => a. constraint satisfied lot of types: int, double or () example. 1 choose? there's nothing can tell us.

in case can resolve ambiguity telling compiler type want, adding type signature:

let x = read "<something>" :: int in show x 

now problem is: since haskell uses num type class handle numbers, there a lot of cases numerical expressions contain ambiguities.

consider:

show 1 

what should result be?

as before 1 has type num => a , there many type of numbers used. 1 choose?

having compiler error every time use number isn't thing, , hence defaulting rules introduced. rules can controlled using default declaration. specifying default (t1, t2, t3) can change how inferencer defaults different types.

an ambiguous type variable v defaultable if:

• v appears in contraints of kind c v c class (i.e. if appears in: monad (m v) not defaultable).
• at least 1 of these classes num or subclass of num.
• all of these classes defined in prelude or standard library.

a defaultable type variable replaced first type in default list instance of ambiguous variable’s classes.

the default default declaration default (integer, double).

for example:

plus = (+) minus = (-)  x = plus 1.0 1 y = minus 2 1 

the types inferred be:

plus :: fractional => -> -> minus :: num => -> -> 

which, defaulting rules, become:

plus :: double -> double -> double minus :: integer -> integer -> integer 

note explains why in example in question sort definition raises error. type ord => [a] -> [a] cannot defaulted because ord isn't numeric class.

extended defaulting

note ghci comes extended defaulting rules (or herefor ghc8), can enabled in files using extendeddefaultrules extensions.

the defaultable type variables need not only appear in contraints classes standard , there must @ least 1 class among eq, ord, show or num , subclasses.

moreover default default declaration default ((), integer, double).

this may produce odd results. taking example question:

prelude> :set -xmonomorphismrestriction prelude> import data.list(sortby) prelude data.list> let sort = sortby compare prelude data.list> :t sort sort :: [()] -> [()] 

in ghci don't type error ord a constraints results in default of () pretty useless.

useful links

there a lot of resources , discussions monomorphism restriction.

here links find useful , may understand or deep further topic:

• haskell's wiki page: monomorphism restriction
• the report
• an accessible , nice blog post
• sections 6.2 , 6.3 of a history of haskell: being lazy class deals monomorphism restriction , type defaulting