How can lists share structure in ways that are impossible for arrays in Common Lisp?

user_9113679 0
Viewed 93

I am trying to learn Common Lisp with the book Common Lisp: A gentle introduction to Symbolic Computation. In chapter 13 (the penultimate one), the book covers arrays.

Thus, the author makes a contrast between list and arrays. He says:

Because storage in arrays is contiguous, we can access each element of an array as fast as any other element. With lists, we have to follow a chain of pointers to get from one cons cell to the next, so depending on the length of the list, it can take much, much longer to access the last element than the first. Efficient access is the prime advantage arrays have over lists. Another advantage is that in most implementations, an array uses only half as much memory as a list of equal length. But lists also have some advantages over arrays. Lists of arbitrary length are easily built up element by element, either recursively or iteratively. It is not as easy to grow an array one element at a time. Another advantage of lists is that they can share structure in ways that are impossible for arrays, but we won’t get into the details of that in this book.

I understand all comments but the last intentionally cryptic one:

Another advantage of lists is that they can share structure in ways that are impossible for arrays, but we won’t get into the details of that in this book.

What exactly would be the share of structure which is possible in the list's data structure but impossible in arrays?

Could someone give me an example to illustrate this?

Thanks.

common-lisp list arrays
1 Answers

E.g., create two lists that share the tail:

(defparameter *l1* (list 1 2 3))
(defparameter *l2* (cons 0 (cdr *l1*))) ; (0 2 3)

Now, (eq (cdr *l1*) (cdr *l2*)) is t, and modifying one list can modify the other:

(setf (second *l1*) 10)
; now *l1* is (1 10 3)
; and *l2* is (0 10 3)

Note that arrays can share structure too:

(defparameter *a1* (make-array 10 :initial-contents (loop for i from 1 to 10 collect i)))
; now *A1* is #(1 2 3 4 5 6 7 8 9 10)
(defparameter *a2* (make-array '(2 3) :displaced-to *a1* :displaced-index-offset 3))
; now *A2* refers to a part of *A1*: #2A((4 5 6) (7 8 9))

Now, modifying *a1* also modifies *a2*:

(setf (aref *a1* 6) 123)
; now *a1* is #(1 2 3 4 5 6 123 8 9 10)
; and *a2* is  #2A((4 5 6) (123 8 9))

The difference here between lists and arrays is in the way structure is shared: lists can share tails while arrays can share contiguous memory segments.

user_8507810
Related