SICP 2.33: List-manipulation operations as accumulations

From SICP section 2.2.3 Sequences as Conventional Interfaces

Section 2.2.3 of SICP introduces the accumulate procedure, which combines elements of a list given an initial value and an operation to combine them with.

(define (accumulate op initial sequence)
   (if (null? sequence)
       initial
       (op (car sequence)
           (accumulate op initial (cdr sequence)))))

> (accumulate + 0 (list 1 2 3 4 5))
15
> (accumulate * 1 (list 1 2 3 4 5))
120

Exercise 2.33 asks us to fill in the missing expressions in the following procedure definitions to implement some basic list-manipulation operations as accumulations.

map

(define (map p sequence)
   (accumulate (lambda (x y) <??>) nil sequence))

The map procedure should accept a procedure and a list as arguments, and it should apply the procedure to each element of that list. We can finish the lambda above by making it apply the procedure p to x, then cons that result to the accumulated sequence.

(define (map p sequence)
   (accumulate (lambda (x y) (cons (p x) y)) null sequence))

Let's also define a couple of simple procedures to test with.

(define (double x)
   (* 2 x))
(define (square x)
   (* x x))

> (map double (list 1 2 3 4 5))
(2 4 6 8 10)
> (map square (list 1 2 3 4 5))
(1 4 9 16 25)

append

(define (append seq1 seq2)
   (accumulate cons <??> <??>))

The append procedure accepts two lists as its parameters and simply appends the second list to the end of the first. My first attempt at this solution was to simply pass the two sequences to accumulate in their original order, but this gives us the wrong output.

(define (append seq1 seq2)
   (accumulate cons seq1 seq2))

> (append (list 1 2 3) (list 4 5 6))
(4 5 6 1 2 3)

This is because of the way the accumulate procedure works. Each element of seq2 is being recursively appended to the front of seq1. All we need to do to fix this problem is reverse the order in which the lists are passed to accumulate.

(define (append seq1 seq2)
   (accumulate cons seq2 seq1))

> (append (list 1 2 3) (list 4 5 6))
(1 2 3 4 5 6)

length

(define (length sequence)
   (accumulate <??> 0 sequence))

This seems like it should be the easiest one of the bunch. The length procedure should simply return the length of the initial sequence. But accumulate combines each element of a sequence using the operation we pass to it. How do we get it to just return the length of the sequence? We can do that by simply giving it an operation that will ignore each element of the sequence, and just increment the accumulated value.

(define (length sequence)
   (accumulate (lambda (x y) (+ 1 y)) 0 sequence))

> (length (list 2 4 6))
3
> (length (list 9 8 7 6 5))
5

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.