Tuesday, February 03, 2009

Monomorphism and Defaulting

Haskell has some ugly corners - not many, but a few. One that many people consider exceptionally ugly is the monomorphism restriction. In this post I'm going to discuss three related issues - Constant Applicative Forms (CAFs), the monomorphism restriction and defaulting. But before we start, lets take a simple example.

Computing Pi

Haskell already provides the pi function which represents the value of pi, but lets assume it didn't. Taking a quick look at Wikipedia we can see that one way of computing Pi is the Gregory-Leibniz series. We can calculate pi as:

pi = (4/1) + (-4/3) + (4/5) + (-4/7) + (4/9) + (-4/11) ...

So let's write that as a Haskell program:

pie = sum $ take 1000000 $ zipWith (/) (iterate negate 4) [1,3..]

Here the constant 1000000 gives the accuracy of our approach, increasing this value will give a higher precision. As it currently stands, the Haskell library says pi = 3.14159265358979 and our program says pie = 3.14159165358977. Thirteen matching digits should be suffient for most uses of pi :-)


The disadvantage of our pie function is that (under Hugs) it takes about 4 seconds to evaluate. If we are performing lots of calculations with pi, calculating pie each time will be a serious problem. CAFs are the solution!

A CAF is a top-level constant, which doesn't take any arguments, and will be computed at most once per program execution. As a slight subtlety, if the constant has class constraints on it (i.e. is Num a => a, instead of a) then it isn't a CAF because the class constraints act like implicit arguments. Our pie function above doesn't take any arguments, so is a CAF.


While pie doesn't have any class constraints, the right-hand side of pie does! Take a look in Hugs:

Main> :t sum $ take 1000000 $ zipWith (/) (iterate negate 4) [1,3..]
:: (Enum a, Fractional a) => a

Main> :t pie
:: Double

The right-hand side works for any Enum and Fractional type, for example Float, but pie is restricted to Double. The reason is the defaulting mechanism in Haskell - if a type can't be nailed down precisely, but is one of a handful of built-in classes, then it will default to a particular type. This feature is handy for working at an interactive environment, but can sometimes be a little unexpected.

Monomorphism restriction

Without defaulting the compiler would infer the type of pie as ::(Enum a, Fractional a) => a. However, such a definition would be rejected by the monomorphism restriction. The monomorphism restriction states that a function with no explicit arguments, but with class constraints, must be given a type annotation. This rejects functions like:

snub = sort . nub

To fix the problem there are two solutions:

snub i_hate_the_evil_mr = (sort . nub) i_hate_the_evil_mr

snub :: Ord a => [a] -> [a]
snub = sort . nub

For a function like pie only the second approach is applicable. The addition of dummy arguments to avoid the monomorphism restriction is sufficiently common that the HLint tool never suggests eta-reduction if the argument is named mr.


So why was the monomorphism restriction first introducted? For a function with no explicit arguments, the programmer might think they had written a CAF, but class constraints may substantially degrade the performance. Defaulting reduces the number of cases where the monomorphism restriction would otherwise bite, but it is still useful to be aware of the ugly corners.

There are proposals afoot to remove the monomorphism restriction and to increase the power of the default mechanism - hopefully both will be included in to Haskell'.


Martijn said...

Is it possible to have a CAF be replaced by its computed value at compile-time?

Martijn said...

Of course this is not desirable if the value is infinite... but for pie it would be fine and save 4 seconds at runtime.

Mathias Stearn said...

In cases where compile time evaluation isn't an option couldn't the Standard just guarantee that pie will be evaluated at most once per type? That seems like the best of both worlds.

As for defaulting, I kind of feel that it should only happen when you use the function. For example, pie would be "(Enum a, Fractional a) => a", but if you used "print pie" it would use the default of Double for the instances of Show, Enum and Fractional. This way you could use pie as any type, but still get easy printing, etc.

Mikhail Glushenkov said...

Hmm, GHC gives me a stack overflow for this function (even with -O2). Why doesn't it execute in constant space?

Unknown said...

@martijn: Without hackery, no. However, there is some hackery available if you're willing. The Template Haskell type class Language.Haskell.TH.Syntax.Lift defines a function lift which can be used thus:

foo = $(lift (CAF GOES HERE))

Of course you can use that splice anywhere, not just for CAFs.

Anonymous said...

Is the original pie function fine as it is? Am I right to think it's CAF already; as it has no class constraints? So we should accept the 4 seconds of evaluation?

Anonymous said...

23Skidoo: it gives a stack overflow because sum is too lazy. Substitute "sum" with "foldl' (+) 0" and it should work.

Anonymous said...

A nit: "Thirteen matching digits should be suffient for most uses of pi" -- actually only 5 digits to the right of the decimal match:

> pi - pie

Neil Mitchell said...

redbeard: Yes,the transformation you suggest of once per type is possible in many cases (its called specialisation), but a Haskell program can have polymorphic recursion, which means there may _not_ be a finite number of types used in the program, and it can't work all cases.

Having defaulting happen only at use seems like a good idea - its certainly going in the right direction.

Anon: 13 matching digits, only 6 of which are consecutive :-) I would have said 12 dp of accuracy if I had it!

Unknown said...

If you stop the calculation of pie after 1e6, you will get an inaccuracy of that size due to the alternating nature of the series.
The average of pie_1000000 and pie_1000001 has a precision of around 5e-13, however.

Very interesting blog. I enjoy reading it. Cheers.

Neil Mitchell said...

Morten: Ah, that's really interesting to know! I'll have to figure out how to do that with the nice list processing style.

Tom Schrijvers said...

Once per type could also be done by need, memoing in fact.

Anonymous said...

> 13 matching digits, only 6 of which are consecutive :-)

I actually laughed out loud at that one...

Eryx said...

I suppose that the two numbers actually match at an infinite number of places...(AFAIK it is believed that pi is a "normal number", and any normal number matches any rational number in 10% of its digits)