Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why do GHC and GHCI differ on type inference?

Tags:

haskell

ghc

ghci

I noticed, when doing a codegolf challenge, that by default, GHC doesn't infer the most general type for variables, leading to type errors when you try to use it with two different types.

For example:

(!) = elem
x = 'l' ! "hello" -- From its use here, GHC assumes (!) :: Char -> [Char] -> Bool
y = 5 ! [3..8] -- Fails because GHC expects these numbers to be of type Char, too

This can be changed using the pragma NoMonomorphismRestriction.

However, typing this into GHCI produces no type error, and :t (!) reveals that here, it assumes (Foldable t, Eq a) => a -> t a -> Bool, even when explicitly run with -XMonomorphismRestriction.

Why do GHC and GHCI differ on assuming the most general type for functions?

(Also, why have it enabled by default anyway? What does it help?)

like image 964
zbw Avatar asked Jan 04 '23 00:01

zbw


1 Answers

The background of why the committee made this decision is given, in the designers’ own words, in the article “A History of Haskell: Being Lazy with Class” by Paul Hudak et al.

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.

[John] 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.

(18, Emphasis added.) Note that John Hughes is a co-author of the article.

like image 148
Davislor Avatar answered Jan 11 '23 22:01

Davislor