# 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.

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.

(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.

(if (null? p) 0

(+ (if (list? (car p))

(deep-list-sum (car p))

(car p))

(deep-list-sum (cdr p)))))

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.

(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`

:

(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:

**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.

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.

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)))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)`

.Finally, define

`pascals-triangle`

with the behavior described above.