Theme index -- Keyboard shortcut: 'u'  Previous theme in this lecture -- Keyboard shortcut: 'p'  Next slide in this lecture -- Keyboard shortcut: 'n'Expressions, Types, and Functions
6.  Lists

The list data type is the characteristic composite data type in all Lisp languages, and as such also in Scheme. Interesting enough, the surface form of a Lisp program is a list itself. This is an important practical observation. Below, we will study the list data type of Lisp and Scheme.

6.1 Proper lists6.5 Association lists
6.2 Symbolic expressions and improper lists6.6 Property lists
6.3 Practical list construction6.7 Tables as lists of rows
6.4 List functions6.8 Programs represented as lists

6.1.  Proper lists
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

Lists are recursively composed. We start with the main points regarding the recursive construction of 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

Below we illustrate how the list (d c b a) is built. The web version of the material gives the best impression of the construction process, via animation (refresh the web presentation to restart the animation). The paper version of the material only shows the end result of the construction.

Figure 6.1    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.

In the items below we emphasize the decomposition of the cons cell made by (cons e f), where e is an arbitrary expression and f is a list. Notice that we assume that the variable x is bound to (cons e f).

  • Construction of the list structure which we here call x

    • (cons e f)

  • Selection:

    • (car x) => e

    • (cdr x) => 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.

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


6.2.  Symbolic expressions and improper lists
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

As illustrated above, the cons function can be used to construct linear linked lists. It should not come as a surprise, however, that cons can be used to make binary tree structures as well. The reason is that each cons cell can refer to two other cons cells.

The cons function is suitable for definition of binary trees with 'data' in the leaves

In Figure 6.2 we show a binary tree structure made by use of the the cons function. The light blue box labeled Sexpr is a variable, the value of which is the binary tree structure. In Exercise 2.2 you are encouraged to construct the tree.

Figure 6.2    A symbolic expression which illustrates the most general form it can take - a binary tree

In Figure 6.3 we show the exact same structure in a slightly different layout, and with another coloring. This layout emphasizes the understanding of the structure as an improper list. The first element is the green tree, the second is the brown tree, the third is the symbol g, and the improper list element is the symbol h.

Figure 6.3    The same symbolic expression laid out as a list. The expressions is a proper list if and only if h is the empty list. If h is not the empty list, the symbolic expression is an improper list.

As a matter of terminology, we use the name symbolic expressions, or S-expressions, for the structures we have shown above.

Exercise 2.2. Construction of symbolic expressions

Construct the symbolic expressions illustrated on this page via the cons primitive in Scheme. The entities named a through h should be symbols. As a help, the rightmost part of the structure is made by (cons 'g 'h). 'g is equivalent to (quote g), meaning that g is not evaluated, but taken for face value.

Experiment with h being the empty list. Try to use a proper list function, such as length, on your structures.Solution


6.3.  Practical list construction
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

On this page we address topics related to 'practical list construction'. Often, cons is too low level for construction of lists. Instead we use the list function or quoted expressions. A quoted expression is taken for face value; The quote form ´(e) prevents evaluation. The quasiquote form `(e) is a variant of quote, which allows non constant constituents in a quote form. Please notice the use of 'normal quote' and 'back quote' before the parentheses. For details of the quasiquote special form you should consult section 4.2.6 in the Scheme report [Abelson98] .

cons is the basic list constructor function - but it can be applied through a number of other means as well

  • List and S-expression construction:

    • Deep cons expressions

    • Using the list function

    • Using quote or quasiquote also known as backquote



(cons 1 (cons 2 (cons (+ 1 2) '())))
(1 2 3)
(list 1 2 (+ 1 2))
(1 2 3)
(quote (1 2 (+ 1 2)))
(1 2 (+ 1 2))
'(1 2 (+ 1 2))
(1 2 (+ 1 2))
(quasiquote (1 2 (unquote (+ 1 2))))
(1 2 3)
`(1 2 ,(+ 1 2))
(1 2 3)
Table 6.1    Examples of list construction by use of cons , list and quoted list expressions.

Exercise 2.3. Every second element of a list

Write a function, every-second-element, that returns every second element of a list. As examples

  (every-second-element '(a b c)) => (a c)
  (every-second-element '(a b c d)) => (a c)

It is recommended that you formulate a recursive solution. Be sure to consider the basis case(s) carefully.

It is often worthwhile to go for a more general solution than actually needed. Sometimes, in fact, the general solution is simpler than one of the more specialized solutions. Discuss possible generalizations of every-second-element, and implement the one you find most appropriate.



6.4.  List functions
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

On this page we will review a number of important list functions, which are part of Scheme and described in section 6.3.2 of the Scheme report [Abelson98] .

There exists a number of important List functions in Scheme, and we often write other such functions ourselves

  • (null? lst)     A predicate that returns whether lst is empty

  • (list? lst)     A predicate that returns whether lst is a proper list

  • (length lst)     Returns the number of elements in the proper list lst

  • (append lst1 lst2)     Concatenates the elements of two or more lists

  • (reverse lst)     Returns the elements in lst in reverse order

  • (list-ref lst k)     Accesses element number k of the list lst

  • (list-tail lst k)     Returns the k'th tail of the list lst

It should be noticed that the first element is designated as element number 0. Thus (list-ref '(a b c) 1) returns b


6.5.  Association lists
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

Association lists are often used to associate two pieces of data. Association lists in Lisp and Scheme correspond to a particular implementation of associative arrays, cf. [knoopnotes]

An association list is a list of cons pairs

Association lists are used in the same way as associative arrays

In the table below we shows simple examples and applications of association lists. Try them out yourself!



(define computer-prefs 
 '((peter . windows) (lars . mac)
   (paw . linux) (kurt . unix)))
(assq 'lars computer-prefs)
(lars . mac)
(assq 'kurt computer-prefs)
(kurt . unix)
(define computer-prefs-1
 (cons (cons 'lene 'windows) 
((lene . windows)
 (peter . windows) 
 (lars . mac)
 (paw . linux)
 (kurt . unix))
Table 6.2    Examples of association lists. The function assq uses eq? to compare the first parameter with the first element - the key element - in the pairs. As an alternative, we could use the function assoc, which uses equal? for comparison. A better and more general solution would be to pass the comparison function as parameter. Notice in this context, that both assq and assoc are 'traditional Lisp functions' and part of Scheme, as defined in the language report.

Exercise 2.4. Creation of association lists

Program a function pair-up that constructs an association list from a list of keys and a list of values. As an example

  (pair-up '(a b c) (list 1 2 3))

should return

  ((a . 1) (b . 2) (c . 3))

Think of a reasonable solution in case the length of the key list is different from the length of the value list.


Exercise 2.5. Association list and property lists

Association lists have been introduced at this page. An association list is a list of keyword-value pairs (a list of cons cells).

Property lists are closely related to association lists. A property list is a 'flat list' of even length with alternating keys and values.

The property list corresponding to the following association list

  ((a . 1) (b . 2) (c . 3))


  (a 1 b 2 c 3)

Program a function that converts an association list to a property list. Next, program the function that converts a property list to an association list.



6.6.  Property lists
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

Property lists are closely related to association lists. On this page - in Table 6.3 - we compare the two kinds of lists with each other. In Program 6.1 we give examples of property lists from LAML, which uses property lists for attributes in HTML, XML, and CSS.

A property list is a flat, even length list of associations

The HTML/XML/CSS attributes are represented as property lists in LAML documents

Association list

Property list

((peter . "windows")
 (lars . "mac")
 (paw . "linux")
 (kurt . "unix"))
(peter "windows"
 lars "mac"
 paw "linux"
 kurt "unix")
Table 6.3    A comparison between association lists and property lists. In this example we associate keys (represented as symbols) to string values.

(load (string-append laml-dir "laml.scm"))
(laml-style "simple-xhtml1.0-transitional-validating")

(write-html 'raw
 (html 'xmlns ""
   (meta 'http-equiv "Content-Type" 
         'content "text/html; charset=iso-8859-1") 
   (title "Attribute Demo"))
  (body 'id "KN" 'class "generic"

    (p "Here comes a camouflaged link:")

    (p (a 'href "" 'css:text-decoration "none"
          'target "main" "Link to the CS Department"))

    (p "End of document."))))

Program 6.1    A simple LAML document with emphasis on the attributes, represented as property lists.

In the LAML general library there are functions ( alist-to-propertylist and propertylist-to-alist ) that convert between association lists and property lists

You should consult Section 27.2 if you want to learn more about the handling of attributes in LAML.


6.7.  Tables as lists of rows
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

In this material we are especially interested in studying examples from the web domain. In HTML, tables are represented as collections of rows. It is therefore obvious to use lists of lists as a concrete Lisp representation of tables. In Table 6.4 we show such a table, tab1, its rendering, and a number of manipulations of the table (transpositions, row eliminations, and column eliminations). The table operations will be studied in further details in Exercise 4.6 .

It is natural to represent tables as lists of rows, and to represent a row as a list

Tables play an important roles in many web documents

LAML has a strong support of tables



(("This" "is" "first" "row")
 ("This" "is" "second" "row")
 ("This" "is" "third" "row")
 ("This" "is" "fourth" "row")
(show-table tab1)
(show-table (transpose-1 tab1))
(show-table (eliminate-row 2 tab1))
(show-table (eliminate-column 4 tab1))
Table 6.4    Examples of table transposing, row elimination, and column elimination. We will program and illustrate these functions in a later exercise of this material. The function show-table is similar to table-0 from a LAML convenience library. Using higher-order functions it is rather easy to program the show-table function. We will come back to this later in these notes.

In the program below we show a possible implementation of the show-table function, which we used in Table 6.4 The function table-1 is one of the LAML convenience functions, which we have used in the past. There are others and more interesting ways to deal with tables in LAML. You should consult Program 18.6 for details.

(define (show-table rows)
 (let ((row-lgt (length (first rows))))
      (make-list row-lgt 50) 
      (make-list row-lgt green1)
Program 6.2    The function show-table, implemented in terms of a LAML table function.


6.8.  Programs represented as lists
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

The purpose of this section is to remind you that Scheme programs are themselves list structures. At this point of the material, it should not be a big surprise to the readers.

It is a unique property of Lisp that programs are represented as data, using the main data structure of the language: the list

A sample Scheme program from the LAML library:

(define (as-number x)
  (cond ((string? x) (string->number x))
        ((number? x) x)
        ((char? x) (char->integer x))
        ((boolean? x) (if x 1 0))  ; false -> 0, true -> 1
          (string-append "Cannot convert to number "
                         (as-string x))))
Program 6.3    The function from the general library that converts different kinds of data to a number.

Is it possible to access the list source program of a Scheme definition? In other words, is it possible to introspect and reflect about a Scheme program from another Scheme program. Or even more interesting perhaps, is it possible for a function to introspect and affect its own source code? Using the standard Scheme functions the answers are 'no'. However, some Scheme systems allow it nevertheless, through use of non-standard functions. Using more traditional Lisp languages, the answers are 'yes'.

In Scheme it is not intended that the program source should be introspected by the running program

But in other Lisp systems there is easy access to self reflection


6.9.  References
[Abelson98]Richard Kelsey, William Clinger and Jonathan Rees, "Revised^5 Report on the Algorithmic Language Scheme", Higher-Order and Symbolic Computation, Vol. 11, No. 1, August 1998, pp. 7--105.
[Knoopnotes]Associative arrays - OOP (in Danish)

Generated: Tuesday July 2, 2013, 09:14:50
Theme index -- Keyboard shortcut: 'u'  Previous theme in this lecture -- Keyboard shortcut: 'p'  Next slide in this lecture -- Keyboard shortcut: 'n'