5.5 Lists of lists

The elements of a List can be any datatype, including, of course, other Lists. In defining procedures that operate on Lists of Lists, we often use more than one recursive call when we need to go inside the inner Lists.

Example 5.9: Summing Nested Lists

Consider the problem of summing all the numbers in a List of Lists. For example, (nested-list-sum (list (list 1 2 3) (list 4 5 6))) should evaluate to 21. We can define nested-list-sum using list-sum on each List.

(define (nested-list-sum p)
        (if (null? p) 0
                (+ (list-sum (car p))
                (nested-list-sum (cdr p)))))

This works when we know the input is a List of Lists. But, what if the input can contain arbitrarily deeply nested Lists?

To handle this, we need to recursively sum the inner Lists. Each element in our deep List is either a List or a Number. If it is a List, we should add the value of the sum of all elements in the List to the result for the rest of the List. If it is a Number, we should just add the value of the Number to the result for the rest of the List. So, our procedure involves two recursive calls: one for the first element in the List when it is a List, and the other for the rest of the List.

(define (deep-list-sum p)
        (if (null? p) 0
                (+ (if (list? (car p))
                        (deep-list-sum (car p))
                        (car p))
                (deep-list-sum (cdr p)))))
Example 5.10: Flattening Lists

Another way to compute the deep list sum would be to first flatten the List, and then use the list-sum procedure.

Flattening a nested list takes a List of Lists and evaluates to a List containing the elements of the inner Lists. We can define list-flatten by using list-append to append all the inner Lists together.

(define (list-flatten p)
        (if (null? p) null
                (list-append (car p) (list-flatten (cdr p)))))

This flattens a List of Lists into a single List. To completely flatten a deeply nested List, we use multiple recursive calls as we did with deep-list-sum:

(define (deep-list-flatten p)
(if (null? p) null
        (list-append (if (list? (car p))
                (deep-list-flatten (car p))
                (list (car p)))
        (deep-list-flatten (cdr p)))))

Now we can define deep-list-sum as:

(define deep-list-sum (fcompose deep-list-flatten list-sum))

Exercise 5.24. $\left[\star \right]$Define a procedure deep-list-map that behaves similarly to list-map but on deeply nested lists. It should take two parameters, a mapping procedure, and a List (that may contain deeply nested Lists as elements), and output a List with the same structure as the input List with each value mapped using the mapping procedure.

Exercise 5.25. $\left[\star \right]$Define a procedure deep-list-filter that behaves similarly to list-filter but on deeply nested lists.

Exploration 5.1: Pascal’s Triangle

Pascal’s Triangle (named for Blaise Pascal, although known to many others before him) is shown below:

          1          
        1   1        
      1   2   1      
    1   3   3   1    
  1   4   6   4   1  
1   5   10   10   5   1
$\cdots $

Each number in the triangle is the sum of the two numbers immediately above and to the left and right of it. The numbers in Pascal’s Triangle are the coefficients in a binomial expansion. The numbers of the $n^{th}$ row (where the rows are numbered starting from 0) are the coefficients of the binomial expansion of $(x+y)^ n$. For example, $(x+y)^2 = x^2+2xy+y^2$, so the coefficients are 1 2 1, matching the third row in the triangle; from the fifth row, $(x+y)^4 = x^4 + 4x^3y + 6 x^2y^2 + 4xy^3 + y^4$. The values in the triangle also match the number of ways to choose $k$ elements from a set of size $n$ (see Exercise 4.5) — the $k^{th}$ number on the $n^{th}$ row of the triangle gives the number of ways to choose $k$ elements from a set of size $n$. For example, the third number on the fifth ($n$ = 4) row is 6, so there are 6 ways to choose 3 items from a set of size 4.

The goal of this exploration is to define a procedure, pascals-triangle to produce Pascal’s Triangle. The input to your procedure should be the number of rows; the output should be a list, where each element of the list is a list of the numbers on that row of Pascal’s Triangle. For example, (pascals-triangle 0) should produce ((1)) (a list containing one element which is a list containing the number 1), and (pascals-triangle 4) should produce ((1) (1 1) (1 2 1) (1 3 3 1) (1 4 6 4 1)).

Ambitious readers should attempt to define pascals-triangle themselves; the sub-parts below provide some hints for one way to define it.

  1. First, define a procedure expand-row that expands one row in the triangle. It takes a List of numbers as input, and as output produces a List with one more element than the input list. The first number in the output List should be the first number in the input List; the last number in the output List should be the last number in the input List. Every other number in the output List is the sum of two numbers in the input List. The $n^{th}$ number in the output List is the sum of the $n-1^{th}$ and $n^{th}$ numbers in the input List. For example, (expand-row (list 1)) evaluates to (1 1); (expand-row (list 1 1)) evaluates to (1 2 1); and (expand-row (list 1 4 6 4 1)) evaluates to (1 5 10 10 5 1). This is trickier than the recursive list procedures we have seen so far since the base case is not the empty list. It also needs to deal with the first element specially. To define expand-row, it will be helpful to divide it into two procedures, one that deals with the first element of the list, and one that produces the rest of the list: (define (expand-row p) (cons (car p) (expand-row-rest p)))

  2. Define a procedure pascals-triangle-row that takes one input, $n$, and outputs the $n^{th}$ row of Pascal’s Triangle. For example, (pascals-triangle-row 0) evaluates to (1) and (pascals-triangle-row 3) produces (1 3 3 1).

  3. Finally, define pascals-triangle with the behavior described above.