7 - Efficiency

Summary

The question of efficiency has been an ever-present undercurrent in recent discussions, and the time has come to bring this important subject to the surface. The best way to achieve efficiency is, of course, to find a decent algorithm for the problem. That leads us into the larger topic of Algorithm Design, which is not the primary focus of this book. Nevertheless we will touch on some fundamental ideas later on. In the present chapter we concentrate on a more basic question: functional programming allows us to construct elegant expressions and definitions, but do we know what it costs to evaluate them? Alan Perlis, a US computer scientist, once inverted Oscar Wilde's definition of a cynic to assert that a functional programmer was someone who knew the value of everything and the cost of nothing.

Lazy evaluation

We said in Chapter 2 that, under lazy evaluation, an expression such as

sqr (sqr (3+4))

where sqr x = x*x, is reduced to its simplest possible form by applying reduction steps from the outside in. That means the definition of the function sqr is installed first, and its argument is evaluated only when needed. The following evaluation sequence follows this prescription, but is not lazy evaluation:

sqr (sqr (3+4))

= sqr (3+4) ⋆ sqr (3+4)

= ((3+4)⋆(3+4)) ⋆ ((3+4)⋆(3+4))

= …

= 2401

The ellipsis in the penultimate line hides no fewer than four evaluations of 3+4 and two of 7⋆7.