Division in Haskell, still don't get it

Question

I still don't understand the division in Haskell. My first intention was to define a funcion like this:

piApprox :: (Integral a, Fractional b) => a -> b
piApprox n = 4 * sum [ (-1)^k / (2*k + 1) | k <- [0..n] ]

It doesn't work. Then, using the signature:

piApprox :: (Fractional a) => Int -> a

but it raises again the "Could not deduce" error.

If I run this code in the interpreter to find out what signature is the best, the result is:

Prelude> let piApprox n = 4 * sum [ (-1)^k / (2*k + 1) | k <- [0..n] ]
Prelude> :t piApprox
piApprox :: (Fractional a, Integral a) => a -> a

which raises "The type variable `a0' is ambiguous" error.

Right now, the only way to make this calculation that I could think of is including the Ratio package and then converting to double by using fromRational.

import Data.Ratio
piApprox n = (fromRational) $ 4 * sum [ (-1)^k % (2*k + 1) | k <- [0..n] ]

It works, but I don't think that's the best approach.

I also thought that even the input and output types were right in the signature, the intermediate operation (-1)^k / (2*k + 1) -- where the division is placed -- might be the problem, so I also defined:

piApprox' :: (Fractional a) => Int -> a
piApprox' n = 4 * sum [ (fromIntegral) $ (-1)^k / (2*k + 1) | k <- [0..n] ]

with no luck. What am I missing here?

Answer 1

This should work:

piApprox n = 4 * sum [ fromIntegral ((-1)^k) / fromIntegral (2*k + 1) | k <- [0..n] ]

The fromIntegral function has a type signature of :

(Integral a, Num b) => a -> b

So it basically converts your Integral type to Num type.

The type of (/) is:

Fractional a => a -> a -> a, so you have to supply Fractional data to it.

The fromIntegral function will exactly achieve this by converting it to a Num type which includes Fractional types.

Answer 2

Your problem is that you're mixing incompatible number types. You said that n is some Integral (specifically, Integer in this case). k <- [0..n] means that k is the same Integral type. Then you use the / division, which is part of the Fractional class. Which means your result would have to be both Integral and Fractional, and I don't think such a type exists.

The solution would be to convert k to your result type before using it with fromIntegral k.

Answer 3

I'd advocate for this signature:

piApprox :: (Fractional r) => Int -> r

The reason being, the "precision" parameter doesn't have any particular "value" meaning, it's just a counter of how many steps you're willing to let the function run. (A better approach might be specifying what deviation to the true value π you want to allow instead of the evaluation depth, but that's more complicated.)

Next, the point where your currect implementation clashes is actually (-1)^k (it requires Integral because the exponentiation is implemented by recursed multiplication). Yes, that's the usual way to denote an alternating sign in maths and science, but if you think about it it's a pretty bad way. You're not really interested in powers here, just in the sign-alternation, and that's far more naturally achieved with cycle [1, -1].

For the multiplication it's different, that doesn't need Integral at all but requires that both arguments have the same type. The natural way to achieve this is, use a Fractional variable right away, rather than converting from a integral one! So instead of [0..n], you could use [0 .. fromIntegral n]. Just one conversion instead of one at each step.

Actually though, it's better not to bound the indices at all! Since this is Haskell, you can define the list as infinite (like what cycle also does). Of course you can't sum an infinite list, but you can simply trim it down right before doing so:

piApprox :: (Fractional r) => Int -> r
piApprox n = 4 * sum (take n [ σ / (2*k + 1) | (σ,k) <- zip (cycle [-1,1]) [0..] ])

Or, perhaps nicer written with the ParallelListComprehensions extension:

piApprox n = (4 *) . sum $
    take n [ σ / (2*k + 1) | σ <- cycle [1, -1]
                           | k <- [0..]
           ]

This does one step less than your implementation because take n [0..] is equivalent to [0..n-1]. I suppose this doesn't matter too much, otherwise it's trivial to fix.

---

Finally: I assume you're aware that this formula is pretty bad in terms of convergence speed!