---

Flatten Any Nested List in Common Lisp: A Deep Dive into Recursion and Reduction

To flatten a nested list in Common Lisp, you must recursively traverse its structure, collecting all non-list elements (atoms) into a new, single-level list. This process typically involves a recursive function that checks each item, appending atoms to an accumulator and making a recursive call for sub-lists, while also filtering out any nil values.

You've just received a critical shipment of supplies, but there's a logistical nightmare. Everything is packed in boxes, which are inside other boxes, which are themselves nested several layers deep. To be useful, you need every single item laid out and accessible in one place. This real-world problem of unpacking is exactly what developers face when dealing with nested data structures.

In programming, especially in a language like Common Lisp where lists are fundamental, data often arrives in a deeply nested format. Whether it's a configuration file, a complex API response, or a tree structure, you can't process it efficiently until you "unpack" it. This guide will show you how to solve this classic problem, turning a chaotic, multi-layered list into a clean, flat, and usable sequence.

---

What is List Flattening?

In the context of Common Lisp, "list flattening" is the process of taking a complex, nested list and converting it into a simple, single-dimensional list. A nested list is a list that contains other lists as its elements, potentially to any depth.

Consider this nested structure:

(1 (2 3) (4 (5)))

This list has three top-level elements: the number 1, the list (2 3), and the list (4 (5)). The goal of flattening is to produce a new list containing only the non-list elements (called "atoms" in Lisp) in the order they appear.

The flattened version of the list above would be:

(1 2 3 4 5)

A key requirement from the kodikra.com learning path is to also handle and remove nil (or null-like) values during this process. So, an input like (1 (2 nil) ((4)) 5) should result in (1 2 4 5).

---

Why is Flattening a Nested List So Important?

While it might seem like a purely academic exercise, flattening nested data structures is a crucial and practical skill in software development. Many algorithms and data processing pipelines are designed to work on simple, iterable sequences. Nested structures introduce complexity that must be resolved first.

• Data Processing & Analysis: When you parse data from sources like JSON or XML, you often get deeply nested objects. Flattening this data allows you to easily iterate over all values, perform aggregations, or search for specific items without writing complex traversal logic every time.
• Algorithm Input: Many algorithms, from simple statistical calculations (like finding the sum or average) to more complex machine learning feature extractors, expect a flat vector or list of inputs. Flattening is a necessary pre-processing step.
• Simplifying State Management: In applications, complex state can be represented as a nested structure. Flattening it can make it easier to serialize, store, or debug.
• Functional Programming: In the functional paradigm, operations like map, filter, and reduce work most intuitively on flat collections. Transforming data into this shape unlocks the full power of these higher-order functions.

---

How to Flatten a List in Common Lisp: The Core Logic

The solution to this problem hinges on one of the most powerful concepts in computer science: recursion. Because a nested list is a recursive data structure (a list can contain other lists), a recursive function is the most natural way to process it.

The basic algorithm for a recursive flatten function is as follows:

1. Iterate through each element of the input list.
2. For each element, ask: "Is this element an atom (i.e., not a list)?"
3. Base Case: If it is an atom, add it to our result list.
4. Recursive Step: If it is not an atom (meaning it's another list), call the flatten function on this inner list and add its flattened result to our main result.

Let's look at the first ASCII diagram to visualize this recursive flow for an input like (A (B C) D).

● Start with `(A (B C) D)`
│
├─ Process `A`
│  │
│  └─ ◆ Is `A` an atom? → Yes
│     │
│     └─ ✔ Collect `A`
│
├─ Process `(B C)`
│  │
│  └─ ◆ Is `(B C)` an atom? → No
│     │
│     └─  recursing...
│        │
│        ● Start with `(B C)`
│        │
│        ├─ Process `B` → ✔ Collect `B`
│        │
│        └─ Process `C` → ✔ Collect `C`
│        │
│        ● Return `(B C)`
│
├─ Process `D`
│  │
│  └─ ◆ Is `D` an atom? → Yes
│     │
│     └─ ✔ Collect `D`
│
▼
● Final Result: `(A B C D)`

A Solution Using `reduce`

The kodikra.com module provides a concise and highly functional solution using the reduce function. This approach is elegant but packs a lot of logic into a single expression. Let's dissect it piece by piece.

The Full Code

(defpackage :flatten-array
  (:use :cl)
  (:export :flatten))

(in-package :flatten-array)

(defun flatten (nested)
  (remove nil (reduce #'(lambda (acc item)
                          (append acc
                                  (if (atom item)
                                      (list item)
                                      (flatten item))))
                      nested
                      :initial-value (list))))

Code Walkthrough

1. `(defun flatten (nested) ...)`

This defines our main function, flatten, which accepts one argument, nested, representing the list we want to flatten.

2. `(reduce #'(lambda ...) nested :initial-value (list))`

This is the engine of our function. reduce is a powerful higher-order function that iterates over a sequence, applying a function to accumulate a single result.

• #'(lambda (acc item) ...): This is the function that reduce will apply at each step. It takes two arguments: acc (the accumulator, which holds the result so far) and item (the current element from the nested list).
• nested: This is the input list that reduce will iterate over.
• :initial-value (list): This is crucial. It tells reduce to start with an empty list () as the initial value for the accumulator acc.

Let's visualize how `reduce` works with an accumulator.

Input: `(1 (2 3) 4)`
Initial Accumulator `acc`: `()`

  Step 1
    │
    ├─ `item` is `1`
    ├─ `acc` is `()`
    └─ Result: `(1)`
       │
       ▼
  Step 2
    │
    ├─ `item` is `(2 3)`
    ├─ `acc` is `(1)`
    └─ Result: `(1 2 3)`
       │
       ▼
  Step 3
    │
    ├─ `item` is `4`
    ├─ `acc` is `(1 2 3)`
    └─ Result: `(1 2 3 4)`
       │
       ▼
● Final `acc`: `(1 2 3 4)`

3. `(if (atom item) ...)`

Inside the lambda, this is our main decision point. The atom function returns T (true) if its argument is anything other than a cons cell (i.e., not a list). Numbers, symbols, and strings are all atoms.

4. `(list item)` (The "if true" branch)

If item is an atom (like the number 1), we can't just return item. The append function requires both of its arguments to be lists. So, we wrap the atomic item in a new list, e.g., 1 becomes (1). This allows (append acc (list item)) to work correctly, for example, (append '(a b) '(c)) results in (a b c).

5. `(flatten item)` (The "if false" branch)

If item is not an atom, it must be a list. This is our recursive step. We call flatten on this sub-list. The result of this recursive call will be a flattened list, which can then be appended to our accumulator.

6. `(append acc ...)`

The append function takes two or more lists and concatenates them into a single new list. In each step of the reduction, we are appending either the wrapped atom `(list item)` or the result of the recursive call `(flatten item)` to our accumulator `acc`.

7. `(remove nil ...)`

Finally, the entire result of the reduce operation is wrapped in (remove nil ...). The symbol nil is technically an atom in Common Lisp, so it would be collected by our logic. This final step cleans the resulting flat list by removing all occurrences of nil, satisfying the problem's requirements.

An Alternative: A Purely Recursive Approach

While the reduce solution is compact, a more traditional recursive function can sometimes be easier to read and understand for those new to functional programming. This approach typically uses helper functions or loops but can be written directly.

Here is an implementation using a loop and building the result in reverse, which can be more performant due to avoiding repeated calls to append.

(defun flatten-recursive (nested)
  (let ((result '()))
    (labels ((flatten-helper (sublist)
               (dolist (item sublist)
                 (cond ((null item)) ; Explicitly ignore nil
                       ((atom item) (push item result))
                       (t (flatten-helper item))))))
      (flatten-helper nested)
      (nreverse result))))

Walkthrough of the Alternative

• (let ((result '())) ...): We initialize a local variable result to an empty list. This will store our flattened elements.
• (labels ((flatten-helper ...))): We define a local helper function. This is a common Lisp idiom for creating recursive functions that don't need to be exposed globally and can access variables from the parent scope (like result).
• (dolist (item sublist) ...): We iterate through each item in the current list being processed.
• (cond ...): This is a multi-branch conditional.
  • ((null item)): If the item is nil, we do nothing, effectively skipping it.
  • ((atom item) (push item result)): If it's an atom, we push it onto our result list. push is efficient as it just adds an element to the front of the list.
  • (t (flatten-helper item)): Otherwise (t), it's a list, so we make a recursive call to our helper.
• (nreverse result): Because we used push, our result list is in reverse order. nreverse is a fast, destructive function that reverses the list in place, giving us the correct final order.

---

Where Do You Apply This Technique?

The skill of flattening data is not confined to Lisp. It's a universal data transformation pattern. You'll find yourself needing it when:

• Parsing S-Expressions: Lisp's own code structure (S-expressions) is a nested list. Flattening can be useful for analyzing code or configuration files written in this format.
• Web Development: Handling complex JSON responses from APIs often requires you to extract all values of a certain key, regardless of how deeply they are nested.
• Tree Traversal: Any tree-like data structure, such as a file system directory, a family tree, or a component hierarchy in a UI framework, can be represented as a nested list. Flattening is equivalent to performing a pre-order traversal and collecting all the leaf nodes.
• Natural Language Processing: Parse trees that represent the grammatical structure of a sentence are inherently nested. Flattening them can help in extracting all words or tokens for further analysis.

---

Pros, Cons, and Performance Considerations

Choosing between the reduce-based solution and the manual recursive one involves trade-offs in readability, conciseness, and performance.

Aspect	reduce with append	Manual Recursion with push/nreverse
Readability	Can be dense and hard to follow for beginners. Highly idiomatic for experienced functional programmers.	Often more explicit and step-by-step, making the logic easier to trace for those less familiar with functional patterns.
Conciseness	Extremely concise. It expresses the entire logic in a single, powerful expression.	More verbose due to the helper function, loop, and explicit variable management.
Performance	Potentially less performant on very large, deeply nested lists. append creates a new list by copying its first argument, which can lead to excessive memory allocation if the accumulator grows large.	Generally more performant. push is a constant-time operation, and nreverse is highly optimized. This avoids the repeated list copying of append.
Stack Safety	Both approaches can potentially lead to a stack overflow on extremely deep (not wide) lists due to deep recursion. Tail-call optimization can mitigate this, but its availability depends on the Lisp implementation.	Same as the `reduce` approach. The `dolist` loop handles width, but deep nesting still relies on the call stack.

For most practical applications, the performance difference is negligible, and the choice comes down to style and readability. The reduce solution is a fantastic demonstration of the functional power of Common Lisp.

---

Frequently Asked Questions (FAQ)

What's the difference between `atom` and `listp` for this problem?

(atom x) returns true if x is not a cons cell (the building block of lists). (listp x) returns true if x is a cons cell or nil. For this problem, (not (listp item)) could almost be a replacement for (atom item), but atom is more direct. Crucially, (atom nil) is true, while (listp nil) is also true, because nil is both an atom and the empty list. Using atom is generally clearer for checking if something is a non-list element.

Why is `append` sometimes considered inefficient?

The append function works by creating a new list. It copies all the elements of its first argument and then points the last element's tail to the second argument. When used in a loop or reduction where the first argument is the growing accumulator, you end up re-copying the entire result list at every step. This leads to quadratic (O(n^2)) complexity in the number of elements, which can be very slow for large lists.

Is there a built-in function to flatten lists in Common Lisp?

No, there is no single function in the ANSI Common Lisp standard for flattening a list of arbitrary depth. This is why it's a common and excellent exercise featured in the kodikra.com curriculum. However, many third-party utility libraries like Alexandria provide a `flatten` function that is highly optimized.

Why do we need to wrap an atom in `(list item)` before appending?

The append function is defined to concatenate lists. If you tried to execute (append '(1 2) 3), it would signal an error because 3 is not a list. By wrapping the atom, (list item), we turn 3 into (3), making the operation valid: (append '(1 2) '(3)) correctly produces (1 2 3).

Can this function handle improper lists (dotted pairs)?

The provided solutions will likely fail or produce unexpected results with improper lists (e.g., (1 2 . 3)). An improper list's `cdr` is an atom, not another list or `nil`. A robust `flatten` function would need to handle this edge case, typically by also checking if the `cdr` of a pair is an atom and collecting it if so. The current logic assumes all non-atoms are proper lists.

How does this compare to flattening in Python or JavaScript?

The core concept of recursion is the same across languages. In Python, you might write a generator function using `yield from` for an elegant solution. In JavaScript, a recursive function checking `Array.isArray()` is common, and newer methods like `Array.prototype.flat(Infinity)` provide a built-in, highly optimized way to achieve the same result.

---

Conclusion: From Chaos to Order

Flattening a nested list is a foundational task that elegantly demonstrates the power of recursion and the functional capabilities of Common Lisp. By understanding how to traverse a recursive data structure, you gain a tool applicable to countless problems, from data processing to algorithm design.

We've explored a concise, functional solution using reduce and a more explicit, performant alternative using manual recursion. Both paths lead to the same destination: transforming a complex, nested structure into a simple, ordered, and usable sequence. Mastering this pattern is a significant step in your journey as a Lisp programmer.

Disclaimer: The code and concepts discussed are based on the ANSI Common Lisp standard. Behavior may vary slightly between different implementations like SBCL, CLISP, or LispWorks, but the core principles remain universal.

Ready to tackle the next challenge? Explore the full Common Lisp learning path on kodikra.com or dive deeper into the language in our comprehensive Common Lisp guide.

---

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