---

Mastering Collection Filtering in Common Lisp: The Ultimate Guide to Keep and Discard

Discover the core of functional programming in Common Lisp by implementing the Strain pattern. This guide breaks down how to build keep (filter) and discard (reject) operations from scratch, teaching you to selectively process collection elements using predicate functions for cleaner, more powerful code.

---

The Data Deluge: Why Manual Filtering is a Dead End

Picture this: you're staring at a massive dataset. It could be thousands of server log entries, a list of user profiles, or raw sensor data. Your mission is to extract specific, meaningful information—find all the error logs, identify users from a certain region, or isolate sensor readings above a critical threshold. The naive approach? A clunky, error-prone loop with a tangled mess of `if` statements.

This manual method is not just tedious; it's fragile. Every new filtering condition adds another layer of complexity, making the code harder to read, debug, and maintain. What if there was a more elegant, declarative way to simply state what you want, and let the language handle the how? This is the promise of functional programming, and in Common Lisp, this powerful pattern is at your fingertips.

In this deep-dive guide, we'll explore the "Strain" pattern—a fundamental concept you'll master in the kodikra.com learning roadmap. We will build two powerful functions, keep and discard, from the ground up. You'll learn not just how to write the code, but why this approach is central to the Lisp philosophy of building expressive, resilient software.

---

What is the Strain Pattern? The Art of Selective Collection Processing

The Strain pattern is a fundamental concept in data processing that involves filtering a collection of items into two distinct groups based on a specific criterion. It's composed of two complementary operations: keep and discard.

• Keep (Filter): This operation takes a collection and a test (a predicate function). It returns a new collection containing only the elements for which the predicate returns true.
• Discard (Reject): This operation is the inverse. It takes the same collection and predicate but returns a new collection containing only the elements for which the predicate returns false.

The key player in this pattern is the predicate. A predicate is simply a function that takes an element as input and returns a boolean value—true (or any non-nil value in Lisp) if the element meets the criteria, and false (nil) otherwise. This separation of the "what to test" (the predicate) from the "how to iterate" (the keep/discard logic) is a cornerstone of functional programming.

Why is This Separation So Powerful?

By decoupling the filtering logic from the condition, you create highly reusable and composable code. Your keep function doesn't care if it's looking for even numbers, strings longer than five characters, or users who are currently active. It only knows how to iterate through a list and apply a test. You can plug in any predicate you can imagine, making your filtering logic incredibly versatile.

This approach promotes immutability. Notice the emphasis on returning a new collection. The original collection is left untouched. This prevents side effects, a common source of bugs in complex applications, leading to more predictable and testable code. This is a core tenet you'll encounter throughout the Common Lisp curriculum at kodikra.com.

---

How to Implement `keep` and `discard` in Common Lisp

Let's roll up our sleeves and build these functions from first principles. The most idiomatic and elegant way to process lists in Lisp is often through recursion. We'll start there, as it beautifully reflects the structure of the list data type itself.

The Core Logic: A Recursive Approach

A list in Lisp can be defined recursively: it's either empty (nil), or it's a "cons cell" containing a head (the first element, or car) and a tail (the rest of the list, or cdr). Our recursive functions will mirror this structure.

The logic for keep will be:

1. Base Case: If the input list is empty, there's nothing to process. Return an empty list.
2. Recursive Step:
   • Look at the first element of the list.
   • Apply the predicate to this element.
   • If the predicate returns true, create a new list by "consing" (adding) this element onto the result of recursively calling keep on the rest of the list.
   • If the predicate returns false, simply ignore the current element and return the result of recursively calling keep on the rest of the list.

The logic for discard is nearly identical, but we flip the condition. We keep the element if the predicate returns false.

ASCII Art Diagram: The Flow of the `keep` Function

This diagram visualizes the decision-making process inside our recursive keep function for each element in the collection.

    ● Start with a list & a predicate
    │
    ▼
┌───────────────────┐
│  Is the list empty? │
└─────────┬─────────┘
          │
  Yes ◀───┴───▶ No
  │           │
  │           ▼
  │   ┌───────────────────┐
  │   │ Get head of list  │
  │   │  (the first item) │
  │   └─────────┬─────────┘
  │             │
  │             ▼
  │      ◆ Apply Predicate to Head
  │     ╱                         ╲
  │  True (Keep it)          False (Ignore it)
  │   │                           │
  │   ▼                           │
  │ ┌───────────────────┐         │
  │ │ Cons head onto the  │         │
  │ │ result of recursive │         │
  │ │ call on tail      │         │
  │ └─────────┬─────────┘         │
  │           │                   │
  │           └─────────┬─────────┘
  │                     │
  │                     ▼
  │      ┌─────────────────────────┐
  │      │ Recurse with tail of list │
  │      └─────────────────────────┘
  │                     │
  └──────────┬──────────┘
             │
             ▼
        ● End (Return final constructed list)

The Solution Code

Here is a complete, well-commented implementation based on the recursive logic. This code is a standard solution for this type of problem in the kodikra learning modules.

;;; This package defines the functions for the Strain module.
(defpackage :strain
  (:use :cl)
  (:export :keep :discard))

(in-package :strain)

(defun keep (predicate list)
  "Returns a new list containing elements from the input list 
   for which the predicate function returns a non-nil (true) value."
  ;; Base case: If the input list is empty, we are done. Return nil (the empty list).
  (if (null list)
      nil
      ;; Recursive step:
      (let ((first-element (car list))
            (rest-of-list (cdr list)))
        ;; Apply the predicate to the first element.
        (if (funcall predicate first-element)
            ;; If the predicate is true, construct a new list by adding the
            ;; first element to the result of processing the rest of the list.
            (cons first-element (keep predicate rest-of-list))
            ;; If the predicate is false, ignore the first element and simply
            ;; continue processing the rest of the list.
            (keep predicate rest-of-list)))))

(defun discard (predicate list)
  "Returns a new list containing elements from the input list 
   for which the predicate function returns nil (false)."
  ;; Base case: An empty list results in an empty list.
  (if (null list)
      nil
      ;; Recursive step:
      (let ((first-element (car list))
            (rest-of-list (cdr list)))
        ;; Apply the predicate. We discard when it's true, keep when it's false.
        (if (funcall predicate first-element)
            ;; If the predicate is true, we discard this element and continue
            ;; with the rest of the list.
            (discard predicate rest-of-list)
            ;; If the predicate is false, we keep this element by consing it
            ;; onto the result of processing the rest of the list.
            (cons first-element (discard predicate rest-of-list))))
  )

Code Walkthrough

1. (defpackage :strain ...): We define a package named strain to encapsulate our functions, preventing name clashes with other code. We export keep and discard so they can be used by other parts of a program.
2. (in-package :strain): This command switches the current working environment into our newly defined package.
3. (defun keep (predicate list) ...): We define the function keep, which accepts two arguments: predicate (which must be a function) and list.
4. (if (null list) nil ...): This is our crucial base case. The null function checks if the list is empty. If it is, recursion stops, and we return nil, the empty list.
5. (let ((first-element (car list)) ...): We use a let block to create local variables for clarity. (car list) gets the first element, and (cdr list) gets the rest of the list.
6. (funcall predicate first-element): This is how you invoke a function that's stored in a variable. funcall applies the predicate function to our first-element.
7. (cons first-element (keep ...)): If the predicate is true, cons constructs a new list cell. It places first-element in the car and the result of the recursive call in the cdr. This is how the new list is built up, piece by piece, as the recursion unwinds.
8. (discard predicate rest-of-list): In the discard function, notice the logic is inverted. When the predicate is true, we simply move on to the rest of the list, effectively dropping the current element.

ASCII Art Diagram: The Flow of the `discard` Function

The logic for `discard` is a mirror image of `keep`. The core decision is simply flipped.

    ● Start with a list & a predicate
    │
    ▼
┌───────────────────┐
│  Is the list empty? │
└─────────┬─────────┘
          │
  Yes ◀───┴───▶ No
  │           │
  │           ▼
  │   ┌───────────────────┐
  │   │ Get head of list  │
  │   └─────────┬─────────┘
  │             │
  │             ▼
  │      ◆ Apply Predicate to Head
  │     ╱                         ╲
  │  True (Discard it)      False (Keep it)
  │   │                           │
  │   │                           ▼
  │   │                         ┌───────────────────┐
  │   │                         │ Cons head onto the  │
  │   │                         │ result of recursive │
  │   │                         │ call on tail      │
  │   │                         └─────────┬─────────┘
  │   └─────────┬─────────┘             │
  │             │                       │
  │             ▼                       │
  │      ┌─────────────────────────┐    │
  │      │ Recurse with tail of list │    │
  │      └────────────┬────────────┘    │
  │                   │                 │
  └──────────┬────────┴─────────────────┘
             │
             ▼
        ● End (Return final constructed list)

---

When to Use Strain: Practical Examples

Theory is great, but let's see this pattern in action. We can use anonymous functions (lambda) to define our predicates on the fly.

Example 1: Filtering Numbers

Let's find all the even numbers in a list.

(strain:keep #'evenp '(1 2 3 4 5 6))
;;=> (2 4 6)

(strain:discard #'evenp '(1 2 3 4 5 6))
;;=> (1 3 5)

Here, #'evenp is shorthand for (function evenp). We are passing the built-in evenp function as our predicate.

Example 2: Filtering Strings

Let's keep only the words that have more than 4 letters.

(strain:keep #'(lambda (word) (> (length word) 4))
             '("lisp" "is" "powerful" "and" "expressive"))
;;=> ("powerful" "expressive")

This example uses a lambda to create a quick, unnamed predicate function that checks the length of each string.

Example 3: Filtering Complex Data (Property Lists)

Imagine a list of users, where each user is represented by a property list (plist). We want to find all active users.

(defvar *users*
  '((:name "Alice" :active t)
    (:name "Bob" :active nil)
    (:name "Charlie" :active t)))

(strain:keep #'(lambda (user) (getf user :active)) *users*)
;;=> ((:NAME "Alice" :ACTIVE T) (:NAME "Charlie" :ACTIVE T))

The predicate #'(lambda (user) (getf user :active)) elegantly extracts the value of the :active key for each user and uses it as the boolean test.

---

Where to Go From Here: Alternative Implementations and Lisp's Power Tools

While building functions recursively is a fantastic learning exercise from the kodikra curriculum, it's essential to know the tools provided by the language itself. Professional Common Lisp code often uses built-in functions that are highly optimized and expressive.

The "Real World" Solution: remove-if and remove-if-not

Common Lisp already has the Strain pattern built into its standard library!

• remove-if-not is equivalent to our keep function. It removes elements for which the predicate is false.
• remove-if is equivalent to our discard function. It removes elements for which the predicate is true.

Let's rewrite our examples using the built-ins:

;; Keep even numbers
(remove-if-not #'evenp '(1 2 3 4 5 6))
;;=> (2 4 6)

;; Discard even numbers (or, keep odd numbers)
(remove-if #'evenp '(1 2 3 4 5 6))
;;=> (1 3 5)

These functions are often implemented in highly efficient, low-level code (sometimes C) within the Lisp implementation, making them faster than a typical recursive Lisp function for very large lists.

Pros and Cons of Different Approaches

Let's compare the methods we've discussed. Understanding these trade-offs is key to becoming an expert developer.

Approach	Pros	Cons
Recursive Implementation	Very elegant and idiomatic for Lisp. Clearly models the recursive nature of lists. Excellent for learning core computer science concepts.	Can lead to stack overflow on extremely large lists if not tail-call optimized. Generally slower than optimized built-in functions.
Iterative (e.g., using LOOP)	Avoids stack depth limitations. Can be more performant than recursion in some Lisp implementations. May feel more familiar to programmers from imperative backgrounds.	Can be more verbose and less "Lispy" than recursion or functional built-ins. Requires manual management of the result list.
Built-in Functions (remove-if)	Most idiomatic and preferred method. Highly optimized for performance and memory usage. Extremely concise and readable. Part of the ANSI Common Lisp standard, ensuring portability.	Abstracts away the underlying mechanism, which is why building it yourself first is such a valuable learning exercise.

Future-Proofing Your Code: As Common Lisp implementations continue to evolve, the performance of built-in higher-order functions like remove-if will only improve. Relying on the standard library is the most future-proof and maintainable strategy for application code. The trend in all modern languages (Python, JavaScript, Rust) is towards embracing these functional, declarative patterns for data manipulation.

---

Frequently Asked Questions (FAQ)

What exactly is a "predicate" in Common Lisp?

In Common Lisp, a predicate is any function that is used for its return value in a boolean context. Conventionally, these functions end with the letter 'p' (e.g., numberp, listp, evenp). They return a "true" value (anything other than nil, but typically the symbol T) if the condition is met, and nil (which represents "false") otherwise.

Is recursion or iteration better for filtering in Common Lisp?

For learning, recursion is invaluable for understanding how lists work. For production code, the built-in functions like remove-if are almost always the best choice. They are highly optimized and more declarative. If you were to implement it manually for a specific reason, an iterative approach using the LOOP macro can be very powerful and avoids stack depth issues, but the built-ins are still preferred for clarity and performance.

Why not just modify the original list instead of creating a new one?

This touches on the concept of immutability and pure functions. By creating a new list, you ensure the original data remains unchanged. This prevents "side effects," where a function unexpectedly alters data that other parts of your program rely on. This makes your code far more predictable, easier to debug, and safer for concurrent programming. Common Lisp does provide destructive functions (like delete-if) for performance-critical situations, but they must be used with extreme care.

How do `keep` and `discard` relate to other functional tools like `map` and `reduce`?

They are all fundamental higher-order functions for collection processing.

• Map: Transforms each element in a collection into a new element (e.g., square every number). It produces a new list of the same length.
• Keep/Filter: Selects a subset of elements from a collection. It produces a new list that is shorter or the same length.
• Reduce: Combines all elements of a collection into a single value (e.g., sum all numbers).

Together, they form a powerful toolkit for most common data manipulation tasks.

Can I always use `lambda` functions as predicates?

Absolutely. Using lambda is the perfect way to create simple, one-off predicate functions right where you need them. This is extremely common and idiomatic in Lisp code, as it keeps the specific logic close to its point of use, improving readability for custom filtering criteria.

What's the difference between `remove-if` and `delete-if`?

This is a critical distinction. remove-if is non-destructive; it returns a new list, leaving the original untouched. delete-if is destructive; it is permitted to modify the original list structure to remove the elements. You should only use delete-if when you are certain that no other part of your code holds a reference to the original list and you need to optimize for memory allocation.

---

Conclusion: From Implementation to Mastery

You've now journeyed from the basic concept of filtering to a deep, practical understanding of the Strain pattern in Common Lisp. By building keep and discard from scratch using recursion, you have gained insight into the very fabric of Lisp's primary data structure. More importantly, you've learned the "why" behind functional programming: creating code that is declarative, reusable, and robust by separating data from the logic that operates on it.

While the ultimate goal is to use Common Lisp's powerful built-in functions like remove-if and remove-if-not, the knowledge gained from this exercise in the kodikra.com module is invaluable. It transforms you from someone who simply uses a language to someone who truly understands it.

Disclaimer: All code examples are written for modern Common Lisp implementations (e.g., SBCL 2.4+, CCL 1.12+) and adhere to the ANSI Common Lisp standard.

Ready to tackle the next challenge? Continue your journey on the kodikra learning path or dive deeper into our extensive Common Lisp language guides.

---

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