**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 :-)

**CAFs**

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.

**Defaulting**

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`.

**Conclusion**

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'.

## 14 comments:

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

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

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.

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

@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.

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?

Paul

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

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

1.0000000187915248e-6

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!

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.

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

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

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

I actually laughed out loud at that one...

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)

Post a Comment