Lecture overview -- Keyboard shortcut: 'u'  Previous page: Lists [Section] -- Keyboard shortcut: 'p'  Next page: Symbolic expressions and improper lists -- Keyboard shortcut: 'n'  Lecture notes - all slides and notes together  slide -- Keyboard shortcut: 't'  Textbook -- Keyboard shortcut: 'v'  Help page about these notes  Alphabetic index  Course home    Lecture 2 - Page 18 : 46
Functional Programming in Scheme
Expressions, Types, and Functions
Proper lists

A list is recursively composed of a head and a tail, which is a (possibly empty) list itself

The building blocks of lists are the cons cells

Every such cell is allocated by an activation of the cons function

To see this image you must download and install the SVG plugin from Adobe.In Firefox please consultthis page.

An illustration list construction and list selection. We first construct a list (d c b a) and we bind it to the variable lst. Next we select the first element, the tail of lst, the second element, and the second tail of lst.

  • Construction of the list structure which we here call x

    • (cons e f)

The constructor function cons takes an element e and a list f and constructs a new list. As illustrated above cons makes exactly one new cons cell, and no kind of list copying is involved at all.

  • Selection:

    • (car x) => e

    • (cdr x) => f

The selector car returns the first element of the list. A better name of car would be head .

The selector cdr returns the list consisting of all but the first element in the list. A better name of cdr would be tail .

A proper list is always terminated by the empty list
In Scheme the empty list is denoted '(). When we in this context talk about the termination of the list we mean the value we get by following the cdr references to the end of the list structure.