Sublist in Common-lisp: Complete Solution & Deep Dive Guide

Learn Common Lisp from Zero to Hero: The Complete Sublist Problem Guide

A core challenge in programming is determining the relationship between two sequences of data. This guide provides a comprehensive solution in Common Lisp for checking if one list is a sublist, superlist, or equal to another, breaking down the logic from fundamental principles to an elegant, idiomatic implementation.

The Challenge: Untangling List Relationships

Imagine you're processing logs, analyzing genetic data, or validating user input. You often encounter a fundamental task: comparing two lists to see how they relate. Is one list a smaller, contiguous part of the other? Are they identical? Or are they completely different? This is the essence of the sublist problem.

In many imperative languages, this task can lead to a maze of nested loops, index-out-of-bounds errors, and complex state management. But in a language like Common Lisp, designed from the ground up for powerful list manipulation, we can craft a solution that is not only robust but also remarkably clear and expressive. This article will guide you through that process, transforming a potentially tricky problem into a demonstration of Lisp's elegance.

We will build a solution from scratch to solve this classic problem from the exclusive kodikra.com learning curriculum, giving you a deep understanding of sequence manipulation, predicate logic, and functional thinking in Common Lisp.

What Exactly is the Sublist Problem?

The problem asks us to take two lists, let's call them list-a and list-b, and determine their precise relationship based on a set of hierarchical rules. There are four possible outcomes, which must be checked in a specific order.

Equal: list-a and list-b are identical. They have the same elements in the same order and are of the same length. For example, (1 2 3) is equal to (1 2 3).
Superlist: list-a contains list-b as a contiguous block of elements. For example, (1 2 3 4 5) is a superlist of (2 3 4).
Sublist: list-a is contained within list-b as a contiguous block. This is the inverse of the superlist relationship. For example, (2 3 4) is a sublist of (1 2 3 4 5).
Unequal: None of the above conditions are met. The lists share no sublist, superlist, or equality relationship. For example, (1 2 4) and (1 3 4) are unequal.

The key here is the term contiguous. The sub-sequence must appear as an unbroken chain within the larger list. The list (1 3) is not a sublist of (1 2 3) because its elements are not adjacent.

Why This Problem is a Perfect Litmus Test for Lisp Programmers

Solving the sublist problem effectively in Common Lisp is more than just a coding exercise; it's a deep dive into the language's core philosophy. Lisp, an acronym for "List Processing," treats lists as a primary, fundamental data structure. This problem forces you to engage with several key concepts:

Sequence Functions: You'll learn to appreciate the rich library of built-in functions for manipulating sequences, such as length, search, and equal.
Predicate Logic: The solution hinges on creating clear predicate functions (functions that return true or false, conventionally ending in `-p`) to test specific conditions.
Functional Decomposition: The most elegant solution involves breaking the main problem into smaller, manageable helper functions. This is a cornerstone of functional programming.
Iteration and Recursion: You can solve this iteratively (like a "sliding window") or recursively, providing an excellent opportunity to compare and contrast these two powerful programming paradigms.

By mastering this challenge from the kodikra Common Lisp Module 1 roadmap, you build a solid foundation that will serve you well in more complex data manipulation tasks.

How to Strategically Design the Solution

Before writing a single line of code, we must outline our strategy. A brute-force approach could get messy. A better way is to establish a clear decision tree. The order of checks is crucial for both correctness and efficiency.

Our high-level logic will be:

Check for Equality First: This is the simplest and most specific case. If the lists are identical, our job is done.
Compare Lengths: The relative lengths of the lists determine whether we should check for a sublist or a superlist relationship. We can't have a superlist if the container is shorter than the content!
Perform the Containment Check: This is the core of the algorithm. We'll need a robust way to "slide" the smaller list across the larger one, checking for a match at each position.
Default to Unequal: If all other checks fail, the lists are unequal.

Logical Flow Diagram

Here is a visual representation of our decision-making process:

    ● Start with list-a, list-b
    │
    ▼
  ┌───────────────────┐
  │ Compare list-a & b │
  │ using `equal`     │
  └─────────┬─────────┘
            │
            ▼
    ◆ Are they equal?
   ╱                  ╲
 Yes ⟶ [Return :EQUAL]  No
                         │
                         ▼
                  ┌───────────────────┐
                  │ Compare lengths:  │
                  │ len(a) vs len(b)  │
                  └─────────┬─────────┘
            ┌───────────────┴───────────────┐
            │                               │
            ▼                               ▼
    ◆ len(a) > len(b)?               ◆ len(b) > len(a)?
   ╱         ╲                      ╱         ╲
 Yes          No ⟶ (Unequal Case) Yes          No ⟶ (Should not happen)
  │                                │
  ▼                                ▼
┌──────────────────┐             ┌──────────────────┐
│ Check if b is in a │             │ Check if a is in b │
└─────────┬────────┘             └─────────┬────────┘
          │                                │
          ▼                                ▼
    ◆ Found?                           ◆ Found?
   ╱        ╲                         ╱        ╲
 Yes         No                     Yes         No
  │           │                      │           │
  ▼           ▼                      ▼           ▼
[Return    [Return                 [Return    [Return
:SUPERLIST] :UNEQUAL]               :SUBLIST]   :UNEQUAL]

The Core Algorithm: The "Sliding Window" Check

The most complex part is checking if a smaller list (the "needle") exists inside a larger list (the "haystack"). We can visualize this as a sliding window. We place the needle at the beginning of the haystack and check for a match. If it doesn't match, we slide the window one position to the right and check again, continuing until we either find a match or run out of haystack.

To implement this, we need a helper function that can answer the question: "Does this list start with the elements of that other list?" Let's call it starts-with-p. Our main search logic will then repeatedly call this helper on successive tails of the haystack.

The Complete Common Lisp Implementation

Here is a full, well-commented implementation that follows our strategic design. It's structured within a package for good practice and uses helper functions to keep the logic clean and readable.


;;; sublist.lisp
;;; This solution is part of the exclusive kodikra.com curriculum.

(defpackage :sublist
  (:use :cl)
  (:export :sublist))

(in-package :sublist)

(defun starts-with-p (list1 list2)
  "Predicate to check if LIST1 starts with the elements of LIST2.
   Returns T if LIST2 is a prefix of LIST1, otherwise NIL."
  (cond
    ((null list2) t) ; An empty list is a prefix of any list.
    ((null list1) nil) ; A non-empty list cannot be a prefix of an empty list.
    ((equal (car list1) (car list2))
     (starts-with-p (cdr list1) (cdr list2))) ; Recurse on the rest of the lists.
    (t nil))) ; Mismatch found.

(defun is-sublist-p (list1 list2)
  "Predicate to check if LIST2 is a contiguous sublist of LIST1.
   This implements the 'sliding window' logic."
  (cond
    ((null list2) t) ; An empty list is always a sublist.
    ((null list1) nil) ; Cannot find a non-empty list in an empty one.
    ((starts-with-p list1 list2) t) ; Found it at the current position.
    (t (is-sublist-p (cdr list1) list2)))) ; Slide the window to the right.

(defun sublist (list1 list2)
  "Determines the relationship between two lists:
   :EQUAL, :SUPERLIST, :SUBLIST, or :UNEQUAL."
  (cond
    ((equal list1 list2) :equal)
    ((> (length list1) (length list2))
     (if (is-sublist-p list1 list2)
         :superlist
         :unequal))
    ((< (length list1) (length list2))
     (if (is-sublist-p list2 list1)
         :sublist
         :unequal))
    (t :unequal)))

In-Depth Code Walkthrough

Let's dissect the code piece by piece to understand how it works together to solve the problem elegantly.

1. Package Definition


(defpackage :sublist
  (:use :cl)
  (:export :sublist))

(in-package :sublist)

We start by defining a package named :sublist. This is standard practice in Common Lisp to avoid name collisions with other code. We specify that it uses the standard :cl (Common Lisp) package and exports only one symbol: our main function, sublist. The in-package form switches the current context into our newly defined package.

2. The `starts-with-p` Helper Function


(defun starts-with-p (list1 list2)
  "Predicate to check if LIST1 starts with the elements of LIST2."
  (cond
    ((null list2) t)
    ((null list1) nil)
    ((equal (car list1) (car list2))
     (starts-with-p (cdr list1) (cdr list2)))
    (t nil)))

This is our first critical building block. It's a recursive function that checks if list1 begins with list2.

Base Case 1: If list2 (the prefix) is empty (null), it's considered a prefix of any list, so we return t.
Base Case 2: If list1 is empty but list2 is not, a match is impossible, so we return nil.
Recursive Step: If the first elements (car) of both lists are equal, we haven't failed yet. The real test is whether the rest of list1 (its cdr) starts with the rest of list2. So, we call starts-with-p again on the tails of both lists.
Failure Case: If the first elements are not equal, we know immediately that list1 does not start with list2, so we return nil.

3. The `is-sublist-p` Helper Function


(defun is-sublist-p (list1 list2)
  "Predicate to check if LIST2 is a contiguous sublist of LIST1."
  (cond
    ((null list2) t)
    ((null list1) nil)
    ((starts-with-p list1 list2) t)
    (t (is-sublist-p (cdr list1) list2))))

This function implements our "sliding window" search. It checks if list2 appears anywhere inside list1.

It first handles the edge cases of empty lists.
Then, it calls our helper starts-with-p to check for a match at the current position of list1.
If that fails, it makes a recursive call. But notice the key difference: it calls itself with the tail of list1 ((cdr list1)) but the original list2. This is how the "window" slides one position to the right for the next check.

Visualizing the `is-sublist-p` Logic

This diagram shows how `is-sublist-p` searches for `(2 3)` within `(1 2 3 4)`.

    ● Call: is-sublist-p `(1 2 3 4)` `(2 3)`
    │
    ├─ Check 1: starts-with-p `(1 2 3 4)` `(2 3)`?
    │  └─ Returns NIL (1 != 2)
    │
    ▼
    ● Recurse: is-sublist-p `(2 3 4)` `(2 3)`
    │
    ├─ Check 2: starts-with-p `(2 3 4)` `(2 3)`?
    │  ├─ `(car)` comparison: 2 == 2 (T)
    │  └─ Recurse `starts-with-p` on `(3 4)` and `(3)`
    │     ├─ `(car)` comparison: 3 == 3 (T)
    │     └─ Recurse `starts-with-p` on `(4)` and `()`
    │        └─ Base case: second list is NIL ⟶ returns T
    │
    ▼
  ┌───────────┐
  │ Returns T │
  └───────────┘

4. The Main `sublist` Function


(defun sublist (list1 list2)
  "Determines the relationship between two lists..."
  (cond
    ((equal list1 list2) :equal)
    ((> (length list1) (length list2))
     (if (is-sublist-p list1 list2)
         :superlist
         :unequal))
    ((< (length list1) (length list2))
     (if (is-sublist-p list2 list1)
         :sublist
         :unequal))
    (t :unequal)))

This function orchestrates the entire process, implementing our high-level decision tree using a cond form.

First, it checks for perfect equality with (equal list1 list2). If true, it returns :equal and stops.
Next, it compares lengths. If list1 is longer, it has the potential to be a superlist. It calls (is-sublist-p list1 list2) to verify. If that returns true, the result is :superlist; otherwise, it's :unequal.
If list1 is shorter, the logic is inverted. It could be a sublist of list2. It calls (is-sublist-p list2 list1) to check.
Finally, the t clause acts as a catch-all. If the lists have the same length but were not caught by the initial equal check, they must be :unequal.

Alternative Approach: The Power of Idiomatic Lisp

While our manual implementation is fantastic for learning, a seasoned Lisp programmer would likely leverage the powerful built-in search function. It does exactly what our is-sublist-p does, but it's highly optimized and part of the language standard.

Solution Using `search`


;;; A more idiomatic solution using the built-in `search` function.

(defun sublist-idiomatic (list1 list2)
  "Determines the list relationship using the built-in `search` function."
  (cond
    ((equal list1 list2) :equal)
    ;; The `search` function returns the starting index of the sub-sequence
    ;; if found, and NIL otherwise. We just need to check if it's not NIL.
    ((search list2 list1) :superlist) ; Is list2 in list1?
    ((search list1 list2) :sublist)   ; Is list1 in list2?
    (t :unequal)))

This version is incredibly concise and readable. It directly translates our problem statement into Lisp code. However, the order of checks is slightly different. The `search` function is powerful enough that we don't need to pre-check lengths.

Pros & Cons Comparison

Let's compare our two approaches. Both are valid, but they serve different purposes.

Aspect	Manual Implementation (Recursive Helpers)	Idiomatic Implementation (`search`)
Learning Value	Excellent. Forces you to understand recursion, list traversal (car/cdr), and algorithmic thinking from first principles.	Good. Teaches you to find and use the right tool from the standard library, which is a critical skill.
Conciseness	More verbose. Requires multiple helper functions.	Excellent. Extremely concise and declarative. The code reads like a description of the problem.
Performance	Generally good, but a naive recursive implementation can be slower than a highly optimized C-level built-in.	Excellent. The `search` function is typically implemented at a lower level and is highly optimized for performance.
Readability	Good, if well-structured with helpers. The logic is explicit.	Excellent. Immediately clear to any experienced Lisp programmer what the intent is.

For the kodikra learning path, building the manual version is invaluable. For production code, the idiomatic version using search is almost always the better choice.

Running and Testing Your Code

You can test your solution using a Common Lisp implementation like SBCL (Steel Bank Common Lisp).

1. Save the code above into a file named sublist.lisp.

2. Start your Lisp environment from the terminal:


$ sbcl

3. Load your file into the REPL (Read-Eval-Print Loop):


* (load "sublist.lisp")

4. Now you can call your function with different lists to see the results:


* (in-package :sublist)

* (sublist '(1 2 3) '(1 2 3))
:EQUAL

* (sublist '(1 2 3 4 5) '(2 3 4))
:SUPERLIST

* (sublist '(3 4) '(1 2 3 4 5))
:SUBLIST

* (sublist '(1 2 4) '(1 2 3 5))
:UNEQUAL

* (sublist '(1 2 3) '())
:SUPERLIST

Frequently Asked Questions (FAQ)

What is the difference between `eq`, `eql`, `equal`, and `equalp` in Common Lisp?

This is a crucial concept. equal was chosen for this problem because it correctly compares lists by checking if their structures and elements are the same.

eq: Checks if two arguments are the exact same object in memory (pointer equality). Very fast but rarely used for value comparison.
eql: Like eq, but also works for numbers and characters of the same value. This is the default for many Lisp functions.
equal: Recursively compares lists and strings for structural and element-wise similarity. This is what we need for list comparison.
equalp: A more lenient version of equal that ignores case in strings and treats numbers of different types (e.g., 2 and 2.0) as equal.

Why not use a `for` loop like in Python or Java?

While Common Lisp has powerful imperative looping constructs like loop and dotimes, solving problems with recursion or higher-order functions is often more natural and idiomatic in Lisp. Our recursive solution with cdr neatly expresses the "process the head, recurse on the tail" pattern that is so fundamental to the language. It avoids manual index management entirely.

How does this solution handle empty lists?

It handles them correctly based on the problem's logic. An empty list is considered a sublist of any other list (including another empty list). Our helper functions have base cases like (null list2) to manage this, returning t, which propagates up to the main function to produce results like :SUBLIST or :SUPERLIST.

What is the time complexity of the manual solution?

Let the length of the larger list be N and the smaller list be M. In the worst-case scenario, the is-sublist-p function will iterate through all possible starting positions in the larger list (N - M positions). At each position, the starts-with-p function compares up to M elements. Therefore, the time complexity is approximately O(N * M).

Can this logic be applied to strings as well?

Absolutely. In Common Lisp, strings are a type of sequence, just like lists. The built-in search function works seamlessly with strings to find substrings. Our manual implementation would also work if you treated the strings as lists of characters, but using search is the standard, optimized way to handle substrings.

Conclusion: From Problem to Principle

We've journeyed from a simple problem statement to a robust, well-structured Common Lisp solution. In the process, we've uncovered fundamental principles of the language: the power of functional decomposition, the elegance of recursion for list processing, and the wisdom of leveraging the rich standard library. The sublist problem serves as a perfect microcosm of the Lisp programming experience—a challenge that encourages you to think declaratively and build solutions from small, logical, and reusable parts.

By understanding both the manual "from-scratch" implementation and the idiomatic `search`-based solution, you gain a deeper appreciation for the trade-offs between learning, clarity, and performance. This knowledge is a critical step on your path to becoming a proficient Lisp developer. To continue your journey, you can deep dive into our complete Common Lisp guide and explore other fascinating challenges.

Disclaimer: The code in this article is written against modern Common Lisp standards and tested with SBCL 2.4.0. It is expected to be compatible with other major ANSI Common Lisp implementations.

Published by Kodikra — Your trusted Common-lisp learning resource.

kodikra

Search this blog