by

Let’s start with lists.

Lists are very important in mathematics — not because lists are especially interesting as a concept, but because they are a basic structure for other, more interesting things.

We start with some examples of lists and introduce some vocabulary.

  1. [2,3,5,7,11,13,17]
  2. [2]
  3. [2,2,2,2,2]
  4. [red, green, blue]
  5. [ ]
  6. [ [ ], 2, red ]

The first list is an ordered list of numbers. There are seven items in this list, so we say that the length of the list is seven. The first item in the list, sometimes called the head item of the list (or simply the head of the list) is the number 2.

The second list contains only a single item (its head) and is this called a singleton list. Its length is one and its head is the number 2.

The third list consists of five copies of the number 2. It has length five and is headed by the number 2. Because all the items in this list are constantly the same, we say this is a constant list.

The fourth list is a list of three colours. Its length is three and its head is the colour red.

The fifth list is a very special list called the empty list. Its length is zero and it contains no items. Since it has no items, there is no first item. The empty list is the only list that has no head.

The sixth is a list of length three. The first item in the list is itself a list (the empty list). Its second item is the number 2. It’s third item is the colour red. Because the items in this list are different kinds of things (list, colour, and number) we call this a heterogenous list (hetero = different), unlike the other lists which are homogenous lists (homo = same).

We can join two lists together to make a new list in an obvious way. We call this list catenation. We will use the infix operator ‘++’ to denote the catenation operation. This is best introduced by examples:

  1. [0,1] ++ [2,3] -> [0,1,2,3]
  2. [2,3] ++ [0,1] -> [2,3,0,1]
  3. [ ] ++ [red, green] -> [red, green]
  4. [red, green] ++ [ ] -> [red, red]
  5. ( [0] ++ [1] ) ++ [2] -> [0,1] ++ [2] -> [0,1,2]
  6. [0] ++ ( [1] ++ [2] ) -> [0,1,2]

These examples illustrate the MONOIDAL properties of list catenation. Examples (3) and (4) illustrate that the empty list serves as a NEUTRAL element for catenation, while examples (5) and (6) illustrate the ASSOCIATIVITY of catenation.

Note that the catenation operation is NOT COMMUTATIVE. This is illustrated by examples (1) and (2). But I will give another example:

  1. [0,1] ++ [0,2] -> [0,1,0,2], but
  2. [0,2] ++ [0,1] -> [0,2,0,1]

Swapping the left and right operands [0,1] and [0,2] clearly yield different results, because the resulting lists [0,1,0,2] and [0,2,0,1] are not the same. Right? RIGHT?

FINALLY, SOME META QUESTIONS TO PONDER..

  • Are the lists [0,1,0,2] and [0,2,0,1] really not the same?
  • Is it clear that they are not the same? (You might ask in response: clear to whom?)
  • If is clear THAT they are not the same, is it clear WHY they are not the same? (You might again ask in response: clear to whom?)

The purpose of this introduction to lists was (in part) to set up these meta questions, and the purpose of these meta questions is to motivate our next topic: the difference between intuitive thinking and rigourous thinking in mathematics and programming.

Leave a comment