[Haskell-beginners] A neat, simple example of making code more efficient

[Costello, Roger L.]

Hi Folks,

This book [1] has a neat, simple example of making code more efficient.

Suppose you want to create a function, quad, that raises a number to the 4th power.

Example: quad 2 = 2 * 2 * 2 * 2 = 16

The function could be implemented like this:

    quad a = a * a * a * a

That implementation requires three multiplications, which can be pretty expensive, especially with arbitrary numbers.

Let's see if we can make it more efficient, by finding an implementation that uses less multiplications. 

By the associative law we can group the expression:

    (a * a) * (a * a)

Each subexpression performs a square operation:

    (square a) * (square a)

Which is itself a square operation:

    square (square a)

That implementation requires only two multiplications. Let's take an example to see why:

quad 2 = square (square 2)
            = square (2 * 2)        -- First multiplication
            = square (4)              -- Reduction 
            = 4 * 4                       -- Second multiplication
            = 16                           -- Reduction to the answer

Thus, by a little rework the number of multiplications is reduced from three to two. That is a significant efficiency improvement.

Cool, aye?

/Roger

[1] http://www.amazon.com/Introduction-Functional-Programming-using-Haskell/dp/0134843460/ref=sr_1_1?ie=UTF8&qid=1308220033&sr=8-1