Analogous to the notion of a shape, a list is an abstract notion. Recall how I built my list of groceries items? I started with a blank list: an empty list! The empty set!
An empty list is a list that has no element.
It is obvious that there are non-empty lists. But what do we mean by a non-empty list? How can we articulate such an obvious notion? Consider for example the following list consisting of three elements.
- milk
- bread
- butter
In the above, we organize the items in a linear fashion with milk being the frst element, bread being the next element following milk and butter being the next element following bread. Is there
any item that follows butter?
Is
- bread
- butter
a list?
Is there a list that follows butter in the above?
A non-empty list is a list that has an element called first and a list called rest.
In the above formulation, the rest of a list is itself a list! The definition of a list is an example of what we call a recursive definition: the list contains a substructure that is isomorphic to itself.
- 1015 reads
