Recursive List Processing: Lisp vs. Modern Functional Languages

Hello! Welcome to the first lesson in our module on "Recursion and Structural Thinking."

In our previous module, we explored the foundations of functional programming, such as pure functions, immutability, and referential transparency. Now, we'll build on that by diving into recursion, the primary mechanism for iteration and control flow in the functional paradigm.

This lesson focuses on writing recursive functions for list processing. We will:

1. Trace the concept back to its origins in Lisp, understanding how the earliest functional language handled lists.
2. Examine how modern functional languages like Haskell have evolved these ideas, introducing more declarative syntax.
3. Compare these two approaches to see the underlying principles that have remained constant.

Given your background in mathematics and computer science, you'll likely recognize the connection between these recursive definitions and proof by induction, which you've recently been studying.

1. The Genesis: List Processing in Lisp

Functional programming's approach to data processing was born with Lisp (List Processing) in the late 1950s. The foundational paper by John McCarthy, "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I" (1960), laid out a complete mathematical system for this. We'll start by exploring the core ideas from this seminal work.

The fundamental data structure in Lisp is the S-expression (Symbolic expression), which is either an "atom" (an indivisible value like a number or a symbol) or a pair of other S-expressions. This pair structure is called a "cons cell."

To understand how lists are built and manipulated, let's look at the five elementary functions McCarthy defined.

As you've just read, all list operations in Lisp boil down to three essential functions operating on these pairs:

• cons[x, y]: Constructs a new pair (x . y).
• car[p]: Returns the first element of the pair p. (Contents of the Address Register)
• cdr[p]: Returns the second element of the pair p. (Contents of the Decrement Register)

A list is simply a chain of these pairs, where the cdr of each pair points to the next, and the final pair's cdr points to a special atom, NIL (or ()), signifying the end of the list.

For example, the list (A B C) is represented internally as (A . (B . (C . NIL))).

With these building blocks, we can define any list-processing function recursively. The key is to use a conditional expression to distinguish between two cases:

1. The base case: Usually an empty list (NIL).
2. The recursive step: Operating on a non-empty list by using car to get the first element and cdr to get the rest of the list, then calling the function again on the rest of the list.

Let's see how McCarthy defined functions like append.

The definition of append[x; y] is a classic example of this pattern:
append[x; y] = [null[x] → y; T → cons[car[x]; append[cdr[x]; y]]]

In a more modern Lisp dialect like Scheme, this would look like:

(define (append x y)
  (if (null? x)
      y
      (cons (car x) (append (cdr x) y))))

Let's trace (append '(A B) '(C D)):

1. x is '(A B), not null. The result is (cons 'A (append '(B) '(C D))).
2. Inside the recursion, x is '(B), not null. The result is (cons 'B (append '() '(C D))).
3. Inside again, x is '(), which is null. The base case is met, and it returns y, which is '(C D).
4. This result is passed back up. Step 2 becomes (cons 'B '(C D)), which evaluates to '(B C D).
5. This is passed to step 1, which becomes (cons 'A '(B C D)), evaluating to the final result: '(A B C D).

The following resource provides more examples of recursive list functions written in Scheme, which uses the same core car/cdr/cons paradigm.

2. The Modern Approach: Pattern Matching in Haskell

Modern functional languages like Haskell build on these foundational ideas but provide more expressive syntax for deconstructing data. Instead of using functions like car and cdr to pull a list apart, Haskell uses pattern matching.

This video introduces recursion in Haskell and the two main ways of handling conditional logic: guards and pattern matching.

In Haskell, a list has two possible forms, or patterns:

1. []: The empty list (the base case).
2. (x:xs): A non-empty list, where x is the head (like car) and xs is the tail (like cdr).

We can define a function by providing separate equations for each pattern. Let's write a function to calculate the sum of a list of integers:

sumList :: [Int] -> Int
sumList []     = 0
sumList (x:xs) = x + sumList xs

Let's break this down:

• sumList :: [Int] -> Int is the type signature. It states that sumList is a function that takes a list of integers and returns an integer.
• sumList [] = 0: This is the first equation. If the input list matches the pattern [] (is empty), the function returns 0. This is our base case.
• sumList (x:xs) = x + sumList xs: This is the second equation. If the input is not empty, it will match the pattern (x:xs). Haskell automatically binds the head of the list to the variable x and the tail to xs. The function then returns the head x plus the result of calling sumList on the tail xs. This is our recursive step.

3. Comparing the Approaches

Let's compare the implementation of a length function in both styles.

Lisp/Scheme Style (Explicit Deconstruction)

(define (length L)
  (if (null? L)
      0
      (+ 1 (length (cdr L)))))

• Base Case Check: (null? L) explicitly checks if the list is empty.
• Deconstruction: We must call cdr to get the rest of the list for the recursive call. car is not needed here, but would be for a function like sum.
• Construction: Not used in this example, but would require cons.

Haskell Style (Declarative Pattern Matching)

length :: [a] -> Int
length []     = 0
length (_:xs) = 1 + length xs

• Base Case Check: Handled implicitly by matching the [] pattern.
• Deconstruction: Handled implicitly by matching the (_:xs) pattern. The head is ignored (using _) and the tail is bound to xs.
• Construction: Not used here, but the same (:) operator is used to construct lists.

The fundamental recursive logic is identical: solve a problem by breaking it into a smaller version of itself until you reach a simple base case. The evolution is in the syntax, which has become more declarative, allowing the programmer to state what the data looks like ([] or x:xs) rather than how to pull it apart (car, cdr).

Practice Problem

To solidify your understanding, think about how you would write a function map. This function takes another function f and a list, and returns a new list where f has been applied to every element. For example, map(square, [1, 2, 3]) would return [1, 4, 9].

Sketch out the implementation in both styles:

1. Lisp/Scheme Style:

   • What is the base case? What should (map f '()) return?
   • In the recursive step, what do you do with (car lst)?
   • How do you combine that result with the recursive call on (cdr lst)?

   (define (my-map f lst)
     (if (null? lst)
         '()
         ;; Your recursive step here, using cons, f, car, and cdr
     ))
   

2. Haskell Style:

   • What is the equation for the empty list pattern, myMap f []?
   • What is the equation for the non-empty list pattern, myMap f (x:xs)? How do you apply f to x and combine it with the recursive call on xs?

   myMap :: (a -> b) -> [a] -> [b]
   myMap f []     = -- Your base case here
   myMap f (x:xs) = -- Your recursive step here, using f, x, xs, and the : operator
   

Take a moment to think through the solutions. The recursive structure is the same in both.

(define (my-map f lst)
  (if (null? lst)
      '()
      (cons (f (car lst)) (my-map f (cdr lst)))))

myMap :: (a -> b) -> [a] -> [b]
myMap f []     = []
myMap f (x:xs) = (f x) : (myMap f xs)

Conclusion

In this lesson, we explored the fundamental pattern of recursive list processing.

Key Takeaways:

• Recursion is the primary control structure for iteration in functional programming.
• The original Lisp approach relies on explicitly deconstructing lists using car (head) and cdr (tail), and building them with cons. The base case is checked with a conditional like if or cond.
• Modern functional languages like Haskell use pattern matching to declaratively deconstruct data. A function is defined with separate equations for different patterns (e.g., [] for empty, (x:xs) for non-empty), which makes the code often cleaner and more readable.
• Despite syntactic differences, the underlying recursive thinking—identifying a base case and a recursive step that moves towards it—is universal.

Next Lesson Preview:

We'll formalize the pattern we've learned today into the concept of structural recursion, which is the natural way to process recursively-defined data types. We'll see that this pattern isn't limited to lists and can be applied to other structures like trees, a concept pioneered by the ML family of languages.