You are here

What is a list?

10 March, 2015 - 16:48
Available under Creative Commons-ShareAlike 4.0 International License. Download for free at

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?

  • 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.