Prelude exponentiation is hard to understand

Question

I was reading the Haskell Prelude and finding it pretty understandable, then I stumbled upon the exponention definition:

(^)              :: (Num a, Integral b) => a -> b -> a
x ^ 0            =  1
x ^ n | n > 0    =  f x (n-1) x
                         where f _ 0 y = y
                         f x n y = g x n  where
                                g x n | even n  = g (x*x) (n `quot` 2)
                                     | otherwise = f x (n-1) (x*y)
_ ^ _            = error "Prelude.^: negative exponent"

I do not understand the need for two nested wheres.

What I understood so far:

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

The base must be a number and the exponent intege, ok.

x ^ 0            =  1

Base case, easy.

g x n | even n  = g (x*x) (n `quot` 2)
      | otherwise = f x (n-1) (x*y)

Exponention by squaring... kind of ... Why is the f helper needed? Why are f and g given single letter names? Is it just optimization, am I missing something obvious?

 _ ^ _            = error "Prelude.^: negative exponent"

N > 0 was checked before, N is negative if we arrived here, so error.

---

My implementation would be a direct translation to code of:

Function exp-by-squaring(x, n )
    if n < 0 then return exp-by-squaring(1 / x, - n );
    else if n = 0 then return 1; else if n = 1 then return x ;
    else if n is even then return exp-by-squaring(x * x, n / 2);
    else if n is odd then return x * exp-by-squaring(x * x, (n - 1) / 2).

Pseudocode from wikipedia.

Answer 1

To illustrate what @dfeuer is saying, note that the way f is written it either:

1. f returns a value
2. or, f calls itself with new arguments

Hence f is tail recursive and therefore can easily be transformed into a loop.

On the other hand, consider this alternate implementation of exponentiation by squaring:

-- assume n >= 0
exp x 0 = 1
exp x n | even n    = exp (x*x) (n `quot` 2)
        | otherwise = x * exp x (n-1)

The problem here is that in the otherwise clause the last operation performed is a multiplication. So exp either:

1. returns 1
2. calls itself with new arguments
3. calls itself with some new arguments and multiplies the result by x.

exp is not tail recursive and therefore cannot by transformed into a loop.

Answer 2

f is indeed an optimization. The naive approach would be "top down", calculating x^(n `div` 2) and then squaring the result. The downside of this approach is that it builds a stack of intermediate computations. What f lets this implementation do is to first square x (a single multiplication) and then raise the result to the reduced exponent, tail recursively. The end result is that the function will likely operate entirely in machine registers. g seems to help avoid checking for the end of the loop when the exponent is even, but I'm not really sure if it's a good idea.

Answer 3

As far as I understand it exponentiation is solved by squaring as long as the exponent is even.

This leads to the answer why f is needed in case of an odd number - we use f to return the result in the case of g x 1, in every other odd case we use f to get back in the g-routine.

You can see it best I think if you look at an example:

x ^ n | n > 0 = f x (n-1) x
  where f _ 0 y = y
        f x n y = g x n
          where g x n | even n  = g (x*x) (n `quot` 2)
                      | otherwise = f x (n-1) (x*y)

2^6 = -- x = 2, n = 6, 6 > 0 thus we can use the definition
f 2 (6-1) 2 = f 2 5 2 -- (*)
            = g 2 5 -- 5 is odd we are in the "otherwise" branch
            = f 2 4 (2*2) -- note that the second '2' is still in scope from  (*)
            = f 2 4 (4) -- (**) for reasons of better readability evaluate the expressions, be aware that haskell is lazy and wouldn't do that
            = g 2 4
            = g (2*2) (4 `quot` 2) = g 4 2
            = g (4*4) (2 `quot` 2) = g 16 1
            = f 16 0 (16*4) -- note that the 4 comes from the line marked with (**)
            = f 16 0 64 -- which is the base case for f
            = 64

Now to your question of using single letter function names - that's the kind of thing you have to get used to it is a way most people in the community write. It has no effect on the compiler how you name your functions - as long as they start with a lower case letter.

Answer 4

As others noted, the function is written using tail-recursion for efficiency.

However, note that one could remove the innermost where while preserving tail-recursion as follows: instead of

x ^ n | n > 0 =  f x (n-1) x
      where f _ 0 y = y
            f x n y = g x n
              where g x n | even n  = g (x*x) (n `quot` 2)
                          | otherwise = f x (n-1) (x*y)

we can use

x ^ n | n > 0 =  f x (n-1) x
      where f _ 0 y = y
            f x n y | even n    = f (x*x) (n `quot` 2) y
                    | otherwise = f x (n-1) (x*y)

which is also arguably more readable.

I have however no idea why the authors of the Prelude chose their variant.