Apropos

14.1 Cons Concepts

A cons is a compound data object having two components called the car and the cdr.

Depending on context, a group of connected conses can be viewed in a variety of different ways. A variety of operations is provided to support each of these various views.

14.1.1 Conses as Trees

A tree is a binary recursive data structure made up of conses and atoms: the conses are themselves also trees (sometimes called “subtrees” or “branches”), and the atoms are terminal nodes (sometimes called leaves). Typically, the leaves represent data while the branches establish some relationship among that data.

14.1.1.1 General Restrictions on Parameters that must be Trees

Except as explicitly stated otherwise, for any standardized function that takes a parameter that is required to be a tree, the consequences are undefined if that tree is circular.

14.1.2 Conses as Lists

A list is a chain of conses in which the car of each cons is an element of the list, and the cdr of each cons is either the next link in the chain or a terminating atom.

A proper list is a list terminated by the empty list. The empty list is a proper list, but is not a cons.

An improper list is a list that is not a proper list; that is, it is a circular list or a dotted list.

A dotted list is a list that has a terminating atom that is not the empty list. A non-nil atom by itself is not considered to be a list of any kind — not even a dotted list.

A circular list is a chain of conses that has no termination because some cons in the chain is the cdr of a later cons.

14.1.2.1 Lists as Association Lists

An association list is a list of conses representing an association of keys with values, where the car of each cons is the key and the cdr is the value associated with that key.

14.1.2.2 Lists as Sets

Lists are sometimes viewed as sets by considering their elements unordered and by assuming there is no duplication of elements.

14.1.2.3 General Restrictions on Parameters that must be Lists

Except as explicitly specified otherwise, any standardized function that takes a parameter that is required to be a list should be prepared to signal an error of type type-error if the value received is a dotted list.

Except as explicitly specified otherwise, for any standardized function that takes a parameter that is required to be a list, the consequences are undefined if that list is circular.