Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 38 ยท Lists and Data Structures

Vectors, Arrays and Sequences

Use Common Lisp vectors and multi-dimensional arrays, adjustable vectors with fill pointers, and the generic sequence functions with :key, :test, :start and :end.

Lists are not the only ordered data in Lisp. Vectors (one-dimensional arrays) give you constant-time access by index, and general arrays add more dimensions. Better still, lists, vectors and strings are all sequences, so one family of functions (length, elt, subseq, find, position, remove, sort, reduce, map...) works on all of them. This lesson shows how to create and use arrays and how to master those generic functions.

Vectors

LISP
#(1 2 3)                 ; a literal vector (treat as constant)
(vector 1 2 3)           ; => #(1 2 3)  fresh vector
(make-array 5)           ; => #(0 0 0 0 0) in SBCL (contents unspecified)
(make-array 5 :initial-element 0)           ; => #(0 0 0 0 0)
(make-array 3 :initial-contents '(a b c))   ; => #(A B C)

Read and write elements with aref (0-based) and setf:

LISP
(defparameter *v* (make-array 3 :initial-element 0))
(setf (aref *v* 1) 42)
*v*                      ; => #(0 42 0)
(aref *v* 1)             ; => 42
(length *v*)             ; => 3
(aref *v* 5)             ; ERROR: index out of bounds (SBCL checks)

Indexing a vector is O(1); indexing a list with nth is O(n). Use vectors for random access and lists for building and walking in order.

Adjustable vectors with fill pointers

A plain vector has a fixed size. To grow one, create it adjustable with a fill pointer (the count of elements in use) and use vector-push-extend:

LISP
(defparameter *items*
  (make-array 0 :adjustable t :fill-pointer 0))

(vector-push-extend 'a *items*)
(vector-push-extend 'b *items*)
*items*                   ; => #(A B)
(length *items*)          ; => 2     (the fill pointer)
(vector-pop *items*)      ; => B

Under the hood, SBCL grows the storage geometrically, so appending is amortized O(1). This is Lisp's equivalent of a dynamic array or ArrayList.

Element types

You can promise all elements share a type, enabling compact storage:

LISP
(make-array 4 :element-type 'character :initial-element #\a)  ; => "aaaa"  (a string!)
(make-array 4 :element-type 'bit :initial-element 0)          ; => #*0000  a bit vector
(make-array 3 :element-type 'double-float :initial-element 0d0)

A string is simply a vector of characters, and #*0101 is a literal bit vector.

Multi-dimensional arrays

LISP
(defparameter *grid* (make-array '(2 3) :initial-element 0))   ; 2 rows, 3 columns
(setf (aref *grid* 0 1) 5)
(setf (aref *grid* 1 2) 9)
*grid*                        ; => #2A((0 5 0) (0 0 9))
(aref *grid* 1 2)             ; => 9
(array-dimensions *grid*)     ; => (2 3)
(array-rank *grid*)           ; => 2
(array-total-size *grid*)     ; => 6
(row-major-aref *grid* 4)     ; => 0    flat index into storage

The printed form #2A(...) means "2-dimensional array". There is no built-in matrix multiplication; write loops, or use a library such as lla or magicl.

Loop over every cell with nested dotimes:

LISP
(dotimes (r (array-dimension *grid* 0))
  (dotimes (c (array-dimension *grid* 1))
    (format t "~a " (aref *grid* r c)))
  (terpri))

Sequences: lists, vectors and strings together

sequence is a type that includes lists and vectors (strings are vectors). Functions on sequences work on all of them:

LISP
(length '(1 2 3))        ; => 3
(length #(1 2 3))        ; => 3
(length "abc")           ; => 3
(elt '(a b c) 1)         ; => B     elt works on any sequence (slow on lists)
(elt #(a b c) 1)         ; => B
(subseq '(a b c d) 1 3)  ; => (B C)
(subseq #(a b c d) 1 3)  ; => #(B C)
(reverse "abc")          ; => "cba"
(reverse #(1 2 3))       ; => #(3 2 1)
(concatenate 'list '(1 2) #(3 4))     ; => (1 2 3 4)
(concatenate 'vector '(1 2) '(3 4))   ; => #(1 2 3 4)
(coerce '(1 2 3) 'vector)             ; => #(1 2 3)
(coerce #(1 2 3) 'list)               ; => (1 2 3)
(map 'list #'1+ #(1 2 3))             ; => (2 3 4)
(sort (vector 3 1 2) #'<)             ; => #(1 2 3)

The result type of concatenate, map and coerce is something you choose: 'list, 'vector, 'string.

The search functions from the previous lesson (find, position, count, remove, substitute, reduce, some, every) work on all sequences.

The standard keyword arguments

Almost every sequence function accepts the same options:

Keyword Meaning
:test Function to compare items (default eql)
:key Function applied to each element before comparison
:start, :end Restrict to part of the sequence
:from-end Process from the end (affects which match is found first)
:count Limit how many items remove/substitute change
LISP
(find #\a "banana" :start 2)                  ; => #\a
(position #\a "banana")                       ; => 1
(position #\a "banana" :from-end t)           ; => 5
(position #\a "banana" :start 2 :end 4)       ; => 3
(count 3 '(1 3 2 3 3) :start 2)               ; => 2
(remove 1 '(1 2 1 3 1) :count 2)              ; => (2 3 1)
(find "B" '("a" "b") :test #'string-equal)    ; => "b"
(find 2 #((1 . a) (2 . b)) :key #'car)        ; => (2 . B)
(substitute 0 nil '(1 nil 2 nil))             ; => (1 0 2 0)
(search '(2 3) '(1 2 3 4))                    ; => 1   subsequence search
(mismatch "abcd" "abxy")                      ; => 2   first difference

Learn these keywords once and a few dozen functions are yours.

Stand-in: one function, many sequence kinds

The power of the design is that one find works for everything, parameterized by :key, :test, :start, :end, :from-end. This JavaScript stand-in (not Lisp) implements find and position generically over arrays and strings.

JS Stand-in: generic find/position with keywords

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Choosing a data structure

Need Use
Build incrementally, walk in order, push/pop at the front List
Fast access by index, fixed or growing size Vector (make-array, vector-push-extend)
Rows and columns Two-dimensional array
Text String
Lookup by key Hash table or alist/plist

Most programs use lists first and switch to vectors when profiling shows indexing matters.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which function reads element 2 of a vector v in constant time?

    aref indexes arrays in O(1); nth is for lists.
  2. 2. What do you need to create a vector that can grow with vector-push-extend?

    (make-array 0 :adjustable t :fill-pointer 0) creates a growable vector.
  3. 3. What does (position #\a "banana" :from-end t) return?

    Searching from the end finds the last a at index 5.
  4. 4. What does (concatenate 'vector '(1 2) '(3 4)) return?

    The first argument chooses the result type; here a vector.
  5. 5. What does :key #'car do in (find 2 pairs :key #'car)?

    :key transforms each element before comparing it with the item.

Summary

  • Vectors give O(1) aref; adjustable vectors with fill pointers grow via vector-push-extend.
  • make-array with a list of dimensions makes multi-dimensional arrays; they print as #2A(...).
  • Lists, vectors and strings are all sequences: length, elt, subseq, reverse, find, position, remove, sort, map, reduce work on all.
  • :test, :key, :start, :end, :from-end and :count are shared across sequence functions.
  • Choose the result type with concatenate, map and coerce.

Next: Hash Tables