Chapter 14
Program behaviour

Aims

• To give a self-contained introduction to fundamental measures of complexity of functions.
• To discuss the different ways in which the efficiency of Miranda definitions can be estimated. In particular, the time and space complexity of functions are defined.
• To estimate the efficiency of a number of programming examples.
• To examine different methods of list folding, and to examine heuristics to choose between competing fold functions.
• To show how definitions can be made more efficient by memoizing the results of intermediate calculations for future (re-)use.

Issues

Notation

I have taken the liberty of using the Miranda operator section notation for functions. A function has linear complexity if it is O(^1). Formally, this is preferable to the traditional O(n) in which n is an implicitly lambda-bound variable. Similar remarks apply to O(^2) and O(2^).

Obviously if students are familiar with the traditional notation, the correspondence should be pointed out. Indeed, an explanation of the difference between the two notations might well be illuminating.

Formalisation

The estimates of complexity in this chapter are, I believe, accurate. It is hard however to give a fully formal system by which complexity can be assessed. The aim of the material here is to help in building students' intuitions about the behaviour of lazy functions written in Miranda.

Up