SICP exercise 2.33
From Drewiki
Problem
Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as accumulations:
(define (map p sequence) (accumulate (lambda (x y) <??>) nil sequence)) (define (append seq1 seq2) (accumulate cons <??> <??>)) (define (length sequence) (accumulate <??> 0 sequence))
Solution
Here's the definition of accumulate as given in the text:
(define nil (quote ())) (define (accumulate op initial sequence) (if (null? sequence) initial (op (car sequence) (accumulate op initial (cdr sequence)))))
Here's an implementation of map which uses accumulate:
(define (map p sequence) (accumulate (lambda (x y) (cons (p x) y)) nil sequence))
Test:
(define (square x) (* x x)) (map square (list 2 3 5 7 8))
Output:
(4 9 25 49 64)
An implementation of append:
(define (append seq1 seq2) (accumulate cons seq2 seq1))
Test:
(append (list 1 2 3 4) (list 5 6 7 8))
Output:
(1 2 3 4 5 6 7 8)
And finally, length:
(define (length sequence) (accumulate (lambda (x y) (+ 1 y)) 0 sequence))
Test:
(length (list 1 2 3 4))
Output:
4
(length (list))
Output:
0
(length (list 4 3 11 1 3 4))
Output:
6
