Chapter 4
Data structures: Lists



From the concrete to the abstract

This text deliberately works bottom-up conceptually. List functions here are monomorphic and first-order, with the twin abstractions of polymorphism and higher-order functions only introduced in Part II. The justification for this is the feeling that students only appreciate the power and indeed the definitions of the general operations after exposure to a number of concrete examples of their use. Section 4.8 contains an explicit discussion of the similar forms that many list processing functions take, which is a prelude for matters introduced in Part II.

Writing definitions

One piece of advice which seems useful in the early stages of list programming is to consider examples of how the function is intended to work, and using these examples as guides in writing the definitions.

Pattern matching

One difficulty presented by Miranda which would be unfamiliar from a traditional imperative language is pattern matching. In more complex cases it can be hard to know exactly what sort of pattern to use on the left-hand side of an equation; this is the purpose of the discussion on pp 99-101.

List comprehensions

These are introduced only in their one generator forms in Chapter 4; the problem with more complex forms is that complicated nature of their calculation rules. Nonetheless, the material on list comprehensions from Chapter 12 can be introduced here if it is desired.

Functional and imperative programming

It is with the introduction of lists that a strong and useful link can be made to imperative programming. Miranda lists can be used as a design language for pointer-implemented linked lists, and indeed it is possible to transliterate definitions into Pascal-like languages. An implementation of these Pascal functions is provided in the code distribution.

Next Up

Written 18 May 1995.