Search code examples
haskellrecursionpi

Why is this function being called every time I try to get its value?

I have this Haskell code that I wrote to calculate pi using the series π/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9...:

quarterPi total n s = if (n /= total) then s / (2 * n - 1) + quarterPi total (n + 1) (-s) else s / (2 * n - 1)

calcPi n = 4 * quarterPi n 1 1

I ran the code using the GHCi prelude and tried to store an approximation of pi in a variable; something like: *Main> pi = calcPi 666666, which would obviously take many many recursive iterations before finishing the calculation. I understand that the first time I retrieve the value of pi, it will take time to calculate because of lazy evaluation. For some reason though, it always takes a long time; no matter how many times I use the value or output the value on the screen, it takes several seconds to produce a result. Shouldn't it only have to calculate once because of lazy evaluation?

Solution

  • What's biting you here is what's known as the monomorphism restriction – but unusually, it's the lack of the monomorphism restriction, rather than its presence. It turns out pi isn't quite as constant as you expected, because its type is more general than you may have realized.

    If we turn on profiling information at the REPL:

    *Main> :set +s

    Then we can see that pi is recomputed every time, like you said.

    *Main> pi = calcPi 666666
(0.00 secs, 0 bytes)
*Main> pi
3.141591153588293
(0.94 secs, 551,350,552 bytes)
*Main> pi
3.141591153588293
(0.99 secs, 551,300,808 bytes)

    This is because the type of pi is inferred to be type class polymorphic:

    *Main> :t pi
pi :: (Fractional a, Eq a) => a

    So pi is in a certain sense "not really a constant"; there are lots of pis! There's pi :: Double, there's pi :: Float, there's pi :: Complex Double, and so on. And GHC doesn't cache function applications, so pi is recomputed every time.

    In Haskell files, however, the monomorphism restriction is in effect: a variable binding, like x = …, is never inferred to have a type class polymorphic type like C a => …. Such definitions are defaulted, if possible – a process where Haskell makes values polymorphic in standard numeric type classes monomorphic at Integer or Double. This is why you can write x^2 without getting an "ambiguous type variable" error (even though the type of the exponent doesn't influence the type of the output); the 2 is silently inferred to be of type Integer.

    But the monomorphism restriction only applies inside files. In GHCi, it's disabled. If we turn the monomorphism restriction back on:

    *Main> :set -XMonomorphismRestriction

    Then we can define pi', which we'll only need to calculate once.

    *Main> pi' = calcPi 666666
(0.00 secs, 0 bytes)
*Main> pi'
3.141591153588293
(0.87 secs, 551,303,896 bytes)
*Main> pi'
3.141591153588293
(0.00 secs, 315,168 bytes)

    And that's because pi' really is a constant.

    *Main> :t pi'
pi' :: Double

    An additional few notes:

    1. Laziness doesn't have to do with why calculating pi' is fast the second time; this would be true in a strict language too. Laziness is why the lines where we define pi/pi' report "(0.00 secs, 0 bytes)".

    2. It's not clear to me if you thought it might, but Haskell will never cache the recursive calls you're making. Something like calcPi 666666 will always make all 666,666 recursive calls. It's only once you save it explicitly in a variable that you stop recomputation.

    3. The monomorphism restriction and type defaulting are explained in technical language in the Haskell 2010 report: §4.4.5 "The Monomorphism Restriction, and §4.3.4 "Ambiguous Types, and Defaults for Overloaded Numeric Operations". The GHC User's Guide mentions that the monomorphism restriction is disabled in GHCi, and mentions how to re-/dis-enable it: §9.17.1 "Switching off the dreaded Monomorphism Restriction"