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.

Marielamariele

Perhaps it would help guide our answers if you would show us how you would write an exponential by squaring routine, and then we can explain why the Prelude version is written the way it is. – Stockbroker

@user5402 pseudocode from Wikipedia added – Marielamariele

The exponentiation used in ghc is more complex than the one in the Prelude. The thing is, you don't want extra multiplications. Your has a superfluous multiplication by 1. And the Prelude one is also suboptimal. – Bowie

@Bowie It looks like optimization in Haskell is no trivial matter. And very different from imperative optimizing. – Marielamariele

It's non-trivial in an imperative setting as well. – Bowie

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.

Stockbroker

Your example is exactly how I would have written it (I would have written pow with backtics but that is minor) – Marielamariele

Note also that there is a standard way to transform a non-tail-recursive function to a tail-recursive function, by adding an additional argument to the function. The additional argument is known as an accumulator as values are (kind of) accumulated into it to construct the final result step by step. The argument y of function f plays exaclty this role. I don't immediately have a good reference for the technique, unfortunately. – Barretter

@DominiqueDevriese But the additional stack space would be just O(log N) rigth? – Marielamariele

Why use extra stack when you can write it as a fast loop (ie, tail recursion)? – Bowie

@Bowie Just that the space saving seems not worth so much complexity... maybe, I am very beginner in Haskell, so who I am noone to judge. – Marielamariele

It might not be worth it, but for a library routine I'm willing to spend some extra effort. – Bowie

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.

Franni

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.

Kessinger

You say that f and g are corecursive, that is, one calls the other when needed and viceversa? – Marielamariele

@Marielamariele Corecursion is something else. – Willow

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.

Ludovick

As I mentioned, this avoids checking for zero in the odd case. Whether that's really an advantage is another question. – Franni

The Prelude version is deprecated. For an even more complex one. :) Feel free to improve it, but it must have no extra multiplications. – Bowie