Functions that deal with numbers are naturally functional since numbers are immutable. A list, on the other hand, can be mutated, as you’ve just seen, by **SETF**ing the **CAR**s and **CDR**s of the cons cells that make up its backbone. However, lists can be treated as a functional data type if you consider their value to be determined by the elements they contain. Thus, any list of the form (1 2 3 4) is functionally equivalent to any other list containing those four values, regardless of what cons cells are actually used to represent the list. And any function that takes a list as an argument and returns a value based solely on the contents of the list can likewise be considered functional. For instance, the **REVERSE** sequence function, given the list , always returns a list (4 3 2 1). Different calls to **REVERSE** with functionally equivalent lists as the argument will return functionally equivalent result lists. Another aspect of functional programming, which I’ll discuss in the section “Mapping,” is the use of higher-order functions: functions that treat other functions as data, taking them as arguments or returning them as results.

The reason most list functions are written functionally is it allows them to return results that share cons cells with their arguments. To take a concrete example, the function **APPEND** takes any number of list arguments and returns a new list containing the elements of all its arguments. For instance:

Other functions take similar advantage of lists’ ability to share structure. Some, like , are specified to always return results that share structure in a particular way. Others are simply allowed to return shared structure at the discretion of the implementation.