Funds defines several “functional” data structures for Common Lisp. Functional data structures, also sometimes known as persistent data structures, are data structures that are immutable, or do not modify their contents. Instead of modifying, they creates a new object which has some changes in it, but is otherwise the same as the old. This may seem inefficient, but the new object is created in such a way that it shares much of its contents with the old object, making this a cheap operation. By using these techniques, functional data structures can come close to providing the same performance as mutable data structures but without the added complexity of mutable state.
One functional data structure that every Lisp programmer is familiar with is the list. While a list can be destructively modified, it isn't in standard usage, and operations on lists produce new lists that share structure with the original list. For instance, you can CONS an element onto the head of a list and the list returned shares the entire old list but with a new head tacked in front of the old one.
Functional data structures are particularly useful for multiprocessing applications as they can remove the danger of one process changing a shared data structure in a way that invalidates that structure for another processes.