Go to the first, previous, next, last section, table of contents.


list functions overview

A List, in the computer science sense of the term, consists of a sequence of cells, each of which has two pointers, one to a value, one to the next cell in the list:

           +--------------+
List  -->  |   car     -------------> first value
           |--------------|
           |   cdr   |    |
           +-------- | ---+
                     |
                     V
           +--------------+
           |   car     -------------> second value
           |--------------|
           |   cdr   |    |
           +-------- | ---+
                     |
                     V
           +--------------+
           |   car     -------------> third value
           |--------------|
           |   cdr        |
           +--------------+

The List data structure is logically a binary tree (or graph -- the pointers are permitted to form loops) but is usually interpreted as a sequence. Since the values may themselves be Lists, arbitrary logical tree structures may easily be constructed.

Lists are used very heavily in classical artificial intelligence programming and such offshoots as expert systems and functional programming languages.

Muq will eventually have a full complement of List functions, but for now has just the following (partly because many others are more appropriately coded in-db).

List cells are logically vectors of length two, but it is worth making them a different data type, if only to facilitate more appropriate prettyprinting of List structures. In additiona, CommonLisp requires that they be separate data types.


Go to the first, previous, next, last section, table of contents.