LISP - Sequence length

Modern Lisp: Understanding Sequence Length

In Common Lisp, a sequence is a collection of ordered elements. This is a general category that includes lists, vectors, and strings. The length function is the universal tool for determining the number of elements in any sequence.

Basic Usage of length

(length sequence)

It returns a non-negative integer representing the number of elements.

Examples Across Sequence Types

;; Length of a list
(length '(a b c d))         ;=> 4

;; Length of a string (which is a vector of characters)
(length "Lisp")              ;=> 4

;; Length of a vector
(length #(10 20 30))         ;=> 3

;; Length of the empty list is 0
(length '())                 ;=> 0
(length nil)                 ;=> 0

Performance Considerations: A Crucial Detail

The performance of length depends on the type of sequence. This is a critical distinction for writing efficient code.

• Vectors and Strings (O(1)): For vectors and strings, getting the length is an O(1) operation (constant time). The size is stored with the data structure, so it can be retrieved instantly.
• Lists (O(n)): For lists, getting the length is an O(n) operation (linear time). Lisp must traverse the entire list from start to finish to count the elements.

Common Pitfall: Calling length on a List in a Loop

Because length is O(n) for lists, calling it repeatedly on a long list inside a loop can severely degrade performance.

(defun process-long-list (my-list)
  ;; --- INEFFICIENT ---
  ;; `length` is called on every iteration, re-traversing the list each time.
  (loop for i from 0 below (length my-list)
        do (;; ... some work ...
           ))

  ;; --- EFFICIENT ---
  ;; Store the length in a variable once.
  (let ((len (length my-list)))
    (loop for i from 0 below len
          do (;; ... some work ...
             )))

  ;; --- IDIOMATIC LISP ---
  ;; Even better, iterate directly over the list's elements!
  (loop for element in my-list
        do (;; ... some work with `element` ...
           ))
)

length and Arrays with Fill Pointers

For adjustable arrays with a fill pointer, length behaves differently. It returns the active length (the value of the fill pointer), not the total allocated capacity of the array.

To get the total capacity, you must use array-total-size.

Example: Distinguishing Active Length from Total Size

;; Create a vector with a capacity of 10, but logically empty.
(defvar *my-buffer* (make-array 10 :fill-pointer 0))

;; Check initial state
(print (length *my-buffer*))           ;=> 0 (The active length)
(print (array-total-size *my-buffer*)) ;=> 10 (The allocated capacity)

;; Add an element using `vector-push` (which updates the fill pointer)
(vector-push 'first-element *my-buffer*)

;; Check the new state
(print (length *my-buffer*)) ;=> 1 (The active length has changed)
(print *my-buffer*)          ;=> #(FIRST-ELEMENT)

;; Manually change the active length
(setf (fill-pointer *my-buffer*) 5)

;; Now length reflects the new fill pointer value
(print (length *my-buffer*)) ;=> 5

;; The contents beyond the first element are undefined until set
(print *my-buffer*)          ;=> #(FIRST-ELEMENT #<uninitialized> ...)

Key Takeaways

• length is for sequences: Use it on lists, vectors, and strings.
• Beware of O(n) for lists: Avoid calling length on lists inside loops.
• Fill Pointers change length: For dynamic arrays, length gives the active element count, while array-total-size gives the total capacity.