1.12 Exercise 1.12

This procedure calculates the value in Pascal’s triangle at depth depth and column column. Both the depth and column are 0-indexed.

(define (pascal-value depth col)   (cond ((= 0 col) 1)         ((= depth col) 1)         (else (+ (pascal-value (- depth 1) (- col 1))                  (pascal-value (- depth 1) col)))))

We can define two more procedures to (primitively) print the triangle:

(define (make-new-row depth)   (define (loop depth col str)     (if (> col depth) str         (string-append str                        (number->string (pascal-value depth col))                        (loop depth (+ col 1) " "))))   (loop depth 0 ""))

(define (pascals-triangle depth)   (display (make-pascal-triangle 0 depth "")))

However, I’m not satisfied with this recursive solution. It is clear to me that, instead of tree-recursively generating every value in the tree individually, we can generate the next row of the tree given the bottom row in the current one. We can do this by storing the tree as a list of lists (where new rows are added to the front of the list), and making new rows of the tree by making a list of all the pairs of values in the last row and mapping + over them.

Of course, I could’ve also calculated values using binomial coefficients by row, but I’m more interested in treating this like a data structure juggling problem. Constructing and extending lists of lists can be tricky (especially since we don’t have mutation yet), and it happens that this is a good problem for exploring one way to do this.

It is crucial to the simplicity of implementation that the lists of lists be constructed by prepending – making a new list by consing the new inner list with the old list itself. I haven’t bothered to reverse the rows of the entire tree, so it appears upside-down – but luckily for us, every row is the same forwards and backwards, so this construction has no effect on the tree itself.

I much prefer having a data structure holding an instance of Pascal’s triangle collected and returned. It seems to me that writing procedures consuming this structure can be more general than those that need to directly generate values in the triangle themselves, as seen above.

There is a trick in make-pairs: I add a new pair ’(0 1) to the front and back of the pairs list. This is done to automatically generate the 1s on the outside of the triangle without special cases. Also, make-pairs will generate no pairs other than these padding ones for the row at depth 0, ’(1), because (cdr ’(1)) is null.

Unlike the exercise directs, this procedure also generates an iterative process.

(define (empty? l)   (eq? nil l))

(define (pascal-triangle depth)   (define (make-pairs l)     (define (loop l pairs)       (if (null? (cdr l)) (cons '(0 1) pairs)           (loop (cdr l)                 (cons (list (car l) (cadr l)) pairs))))     (loop l '((0 1))))   (define (compute-next-row row)     (if (empty? row) '(1)         (map          (lambda (p) (+ (car p) (cadr p)))          (make-pairs row))))   (define (triangle-loop current-depth current-triangle)     (if (> current-depth depth) current-triangle         (triangle-loop (+ current-depth 1)                        (cons (compute-next-row (car current-triangle))                              current-triangle))))   (triangle-loop 1 '((1))))