10.1.1. Conceptual Lists


Abstract data types

An abstract data type consists of a type, a concept of what values of that type represent, and a collection of functions and/or constants of that type. (The collection of features that define the abstract data type are called the interface of the abstract data type.) Any module that uses the data type can only use features that are explicitly mentioned in the interface.

We will begin to look at the concept of a list of integers as an abstract data type. The notation introduced here is not C++ notation, but is strictly for thinking about lists conceptually.


Lists and a notation for writing lists

A list of integers is a sequence of zero or more integers. We will write lists in square brackets, such as [2,4,6]. The order matters; the first member of [2,4,6] is 2, the second member is 4 and the third member is 6. There can be repetitions. For example, [1,1,1,1] is a list of four integers.

List [3] is a list with one integer; it is not the same as the number 3 because it does not have the same type; 3 is a number but [3] is a list. The empty list is written [ ].


Operations on conceptual lists

We will use the following notation for working with conceptual lists. These are the operations of the abstract data type. Notice that all of this is at the conceptual level; it is not C++ notation.

head(L)

The head of a list is the first member of the list. For example, head([2,4,6,8]) = 2. The empty list does not have a head, so head([ ]) is an error.

tail(L)

The tail of a list L is the list that you get by removing the first member of L. For example, tail([2,4,6,8]) = [4,6,8]. Notice that tail([3,6]) = [6]; the tail of a list is always a list. You can take the tail of a singleton list: tail([2]) = [ ]. But the empty list has no tail, and computing tail([ ]) is an error.

h:t

Expression h:t is the list whose head is h and whose tail is t. So
  2:[4,6,8] = [2,4,6,8]
  7:[1,2]   = [7,1,2]
  8:[4]     = [8,4]
  5:[]      = [5]
Notice that the left-hand operand of : is an integer and the right-hand operand is a list. That is a requirement.

Expression h:t just yields the list that you get by adding h to the beginning of t. The : operator always adds one value to the beginning of a list. Don't expect it to do anything else.


isEmpty(L)

isEmpty(L) is true if L is an empty list. We will write this as L == [ ] for ease of readability. But you should understand that this is only used to test whether a list is empty, not to ask whether two arbitrary lists are the same list.

emptyList

Constant emptyList is an empty list. (We write [ ] for it, but it is important to realize that an empty list is a key component of the abstract data type.)


Exercises

  1. What is head([3,2,1])? Answer

  2. What is tail([3,2,1])? Answer

  3. What is 9:[4,7,1]? Answer

  4. What is 2:[]? Answer

  5. What is tail([2])? Answer

  6. Does tail([ ]) have a value? If so, what is it? Answer

  7. Does [2,4,6]:8 have a value? If so, what is it? Answer