1.1. Familiar Examples

A familiar example is a telephone book: a `value' is an entry for a person or business; the key is the person's name, the data part is the other information (address and phone number). Another example is the tax table issued with the income tax guide: the key is the amount of taxable income, the data parts includes the amount of federal and provincial tax you must pay.

However, these examples are actually sorted lists, not tables in the pure sense we are defining here. The difference is that in a list the elements are arranged in a sequence: there is a first element, a second one, etc. For every element (except the last) there is a unique `next' element.

In a table, there is no order on the elements. There is no notion of `next'. Tables with no particular order arise fairly often in everyday life. A very familiar example is the table for converting between two kinds of units, such as between metric units of measure and English units:

    

The key is the unit of measure that you currently have; the data is the unit in the other system and the conversion formula. There is no particular order to the entries in this table. Although it happens that the entry for kilograms is written directly after the entry for meters, this is an arbitrary ordering which has no intrinsic meaning. Our abstract type `Table' reflects the fact that, in general, there is no intrinsic order among the entries of a table.

A table most closely resembles our abstract type `Collection'. Indeed, there is only one important difference between the two: we had an operation for traversing a collection (MAP). There is no such operation for tables; which means there is no way to examine the entire contents of a Table. You can lookup individuals with the `retrieve' operation - e.g. you can find out how to convert slugs to kilograms - but there is no operation that will list all the values in a table. Indeed there is not even an operation reporting how many values a table contains.