3 - Lists

Summary

In a public lecture, C. A. R. Hoare (1989a) described his algorithm for finding the ith smallest integer in a collection. This algorithm is subtle, but Hoare described it with admirable clarity as a game of solitaire. Each playing card carried an integer. Moving cards from pile to pile by simple rules, the required integer could quickly be found.

Then Hoare changed the rules of the game. Each card occupied a fixed position, and could only be moved if exchanged with another card. This described the algorithm in terms of arrays. Arrays have great efficiency, but they also have a cost. They probably defeated much of the audience, as they defeat experienced programmers. Mills and Linger (1986) claim that programmers become more productive when arrays are restricted to stacks, queues, etc., without subscripting.

Functional programmers often process collections of items using lists. Like Hoare's stacks of cards, lists allow items to be dealt with one at a time, with great clarity. Lists are easy to understand mathematically, and turn out to be more efficient than commonly thought.

Chapter outline

This chapter describes how to program with lists in Standard ml. It presents several examples that would normally involve arrays, such as matrix operations and sorting.

The chapter contains the following sections:

Introduction to lists. The notion of list is introduced. Standard ml operates on lists using pattern-matching.