Chapter 14
Program behaviour




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.


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.


Written 18 May 1995.