Why do 3 and x (which was assigned 3) have different inferred types in Haskell? [duplicate]

This question already has an answer here: 开发者_Go百科 What is the monomorphism restriction? (1 answer) Closed 7 years ago.

Type inference in Haskell has a bit of a learning curve (to say the least!). A good way to start learning it is with simple examples. So, the following is a bit of a "hello world" for type inference.

Consider the following example:

Prelude> :t 3
3 :: (Num t) => t
Prelude> let x = 3
Prelude> :t x
x :: Integer

The question is thus: Why do 3 and x have different types?

Link Summary:

Read the answers below for the full story; here's just a link summary:

1. GHC type defaulting: Haskell Report section 4.3.4
2. GHCi's extended type defaulting: Using GHCi section 2.4.5
3. Monomorphic Restriction: Haskell wiki

---

There's another factor here, mentioned in some of the links which acfoltzer includes, but it might be worth making explicit here. You're encountering the effect of the monomorphism restriction. When you say

let x = 5

you make a top-level definition of a variable. The MR insists that such definitions, when otherwise unaccompanied by a type signature, should be specialized to a monomorphic value by choosing (hopefully) suitable default instances for the unresolved type variables. By contrast, when you use :t to ask for an inferred type, no such restriction or defaulting is imposed. So

> :t 3
3 :: (Num t) => t

because 3 is indeed overloaded: it is admitted by any numeric type. The defaulting rules choose Integer as the default numeric type, so

> let x = 3
> :t x
x :: Integer

But now let's switch off the MR.

> :set -XNoMonomorphismRestriction
> let y = 3
> :t y
y :: (Num t) => t

Without the MR, the definition is just as polymorphic as it can be, just as overloaded as 3. Just checking...

> :t y * (2.5 :: Float)
y * (2.5 :: Float) :: Float
> :t y * (3 :: Int)
y * (3 :: Int) :: Int

Note that the polymorphic y = 3 is being differently specialized in these uses, according to the fromInteger method supplied with the relevant Num instance. That is, y is not associated with a particular representation of 3, but rather a scheme for constructing representations of 3. Naïvely compiled, that's a recipe for slow, which some people cite as a motivation for the MR.

I'm (locally pretending to be) neutral on the debate about whether the monomorphism restriction is a lesser or greater evil. I always write type signatures for top-level definitions, so there is no ambiguity about what I'm trying to achieve and the MR is beside the point.

When trying to learn how the type system works, it's really useful to separate the aspects of type inference which

1. ‘follow the plan’, specializing polymorphic definitions to particular use cases: a fairly robust matter of constraint-solving, requiring basic unification and instance resolution by backchaining; and

2. ‘guess the plan’, generalizing types to assign a polymorphic type scheme to a definition with no type signature: that's quite fragile, and the more you move past the basic Hindley-Milner discipline, with type classes, with higher-rank polymorphism, with GADTs, the stranger things become.

It's good to learn how the first works, and to understand why the second is difficult. Much of the weirdness in type inference is associated with the second, and with heuristics like the monomorphism restriction trying to deliver useful default behaviour in the face of ambiguity.

---

This occurs because of type defaulting in GHCi, as discussed here, here, here, and here, among others. Unfortunately this seems like something that is difficult to search for, since there are lots of ways to describe this behavior before you know the phrase "type defaulting".

Update: D'oh. Removed poor example.

---

Since nobody else has mentioned why there's a monomorphism restriction, I thought I'd add this bit from A History of Haskell: Being Lazy With Class.

6.2 The monomorphism restriction A major source of controversy in the early stages was the so-called “monomorphism restriction.” Suppose that genericLength has this overloaded type:

genericLength :: Num a => [b] -> a 

Now consider this definition:

f xs = (len, len) 
     where len = genericLength xs 

It looks as if len should be computed only once, but it can actually be computed twice. Why? Because we can infer the type len :: (Num a) => a; when desugared with the dictionary-passing translation, len becomes a function that is called once for each occurrence of len, each of which might used at a different type.

Hughes argued strongly that it was unacceptable to silently duplicate computation in this way. His argument was motivated by a program he had written that ran exponentially slower than he expected. (This was admittedly with a very simple compiler, but we were reluctant to make performance differences as big as this dependent on compiler optimisations.)

Following much debate, the committee adopted the now-notorious monomorphism restriction. Stated briefly, it says that a definition that does not look like a function (i.e. has no arguments on the left-hand side) should be monomorphic in any overloaded type variables. In this example, the rule forces len to be used at the same type at both its occurrences, which solves the performance problem. The programmer can supply an explicit type signature for len if polymorphic behaviour is required.

The monomorphism restriction is manifestly a wart on the language. It seems to bite every new Haskell programmer by giving rise to an unexpected or obscure error message. There has been much discussion of alternatives. The Glasgow Haskell Compiler (GHC, Section 9.1) provides a flag:

-fno-monomorphism-restriction

to suppress the restriction altogether. But in all this time, no truly satisfactory alternative has evolved.

I find the tone of the paper towards the monomorphism restriction is very interesting.