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.

## 2 comments:

how would you do the following?

(define filter

(lambda (predicate sequence)

(accumulate null sequence)))

sorry, it seems to have deleted the space with the question marks

(define filter

(lambda (predicate sequence)

(accumulate (something here) null sequence)))

Post a Comment