LISP - Merge Sequences

Lisp - Merging and Manipulating Sequences

Common Lisp provides a rich set of functions for operating on sequences. A sequence is an ordered collection of elements, and the two most common types are lists and vectors. This chapter explores modern and idiomatic ways to merge and combine these sequences.

Concatenating Sequences: The Universal Tool

The most powerful and flexible tool for joining sequences is the concatenate function. It can merge multiple sequences of different types into a single new sequence of a specified type. This avoids the need for manual, error-prone functions.

Example: Merging Lists, Vectors, and Strings

(let ((list1 '(1 2 3))
      (vector1 #(4 5 6))
      (list2 '(7 8)))

  ;; Concatenate two lists into a new list
  (print (concatenate 'list list1 list2))
  ;; -> (1 2 3 7 8)

  ;; Concatenate two vectors into a new vector
  (print (concatenate 'vector vector1 #(7 8 9)))
  ;; -> #(4 5 6 7 8 9)

  ;; Concatenate a list and a vector into a new vector
  (print (concatenate 'vector list1 vector1))
  ;; -> #(1 2 3 4 5 6)

  ;; Concatenate strings (which are vectors of characters)
  (print (concatenate 'string "Hello, " "World!"))
  ;; -> "Hello, World!"
)

Best Practice: Prefer concatenate over append when you need to create a new sequence. append is specifically for lists and can be inefficient as it must copy all but the last list argument.

Interleaving Sequences

Interleaving (or zipping) involves creating a new sequence by taking elements from two or more source sequences in alternating order. While there isn’t a single standard function for this, it can be implemented elegantly using recursion or iteration.

Example: Interleaving two lists

A recursive approach is concise and demonstrates core list processing principles.

(defun interleave (list1 list2)
  "Creates a new list by alternating elements from list1 and list2."
  (cond ((null list1) list2)
        ((null list2) list1)
        (t (list* (first list1) (first list2)
                  (interleave (rest list1) (rest list2))))))

(print (interleave '(a c e) '(b d f g h)))
;; -> (A B C D E F G H)

For very long lists, an iterative approach using the powerful loop macro can be more efficient and avoid potential stack overflow issues.

(defun interleave-iterative (list1 list2)
  (loop for i in list1
        for j in list2
        collect i
        collect j))

(print (interleave-iterative '(a c e) '(b d f)))
;; -> (A B C D E F)
;; Note: The loop-based version stops when the shorter list is exhausted.

Merging Sorted Sequences

A common task is to merge two already-sorted sequences into a new, single sorted sequence. The idiomatic and most efficient way to do this is with the built-in merge function.

Example: Merging sorted lists of numbers

(let ((sorted-list1 '(1 5 9))
      (sorted-list2 '(2 3 10 12)))

  (let ((merged-result (merge 'list sorted-list1 sorted-list2 #'<)))
    (print merged-result))
)
;; -> (1 2 3 5 9 10 12)

The merge function is highly flexible:

• Result Type: The first argument specifies the type of the resulting sequence (e.g., 'list or 'vector).
• Predicate: The fourth argument is a predicate function (like #<) that determines the sorting order.
• Key: It also accepts a :key argument for merging sequences of complex objects, just like sort.

Modern Development Workflow

In a real project, you would manage your code using tools like:

• ASDF (Another System Definition Facility): To define your project, its files, and its dependencies.
• Quicklisp: To download and manage third-party libraries.
• A Lisp Implementation: Such as SBCL (Steel Bank Common Lisp) for high performance, or CCL (Clozure CL) for fast compile times.
• An Interactive Environment: Like Emacs with SLIME or VS Code with Alive for a powerful REPL-driven development experience.