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.

SICP 2.32: Generating Power Sets

From SICP section 2.2.2 Hierarchical Structures

Exercise 2.32 introduces the concept of the "set of all subsets" of a given set, which you may recognize from mathematics as the power set. If we have the set S = {x, y, z}, then the power set of S is:

P(S) = { {}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z} }

There are a couple of details to note:

1. The empty set {} is a member of every power set.
2. The original set {x, y, z} is also a member of its own power set.

In Scheme we can represent a set as a list of distinct elements, and the power set as a list of sets. In this exercise, we're given the following definition of a procedure that generates the power set of a set, and asked to complete it:

(define (subsets s)
   (if (null? s)
       (list nil)
       (let ((rest (subsets (cdr s))))
          (append rest (map <??> rest)))))

If we're given the set (1 2 3), then the finished procedure should return:

(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

If you read the Wikipedia Power set article that I linked to earlier, you'll see that there's a recursive algorithm for calculating power sets (which I'll now quote liberally).

The first step is to define the following operation:


This function takes an element e and a set T, and returns a set with the element e added to each set X in T.

The procedure for generating the power set follows:

If S = {}, the P(S) = {{}} (the set contaning only the empty set) is returned.

Otherwise:

• Let e be any single element of S.
• Let T be the relative complement of {e} in S.
• 

In other words, the power set of the empty set is the set containing the empty set and the power set of any other set is all the subsets of the set containing some specific element and all the subsets of the set not containing that specific element.

This is exactly the same procedure defined in the text. The only part we have to do is finish the initial operation:


The append and map procedures are already doing much of the work for us. We just need to define a function that will add an element e to the set X. The map procedure will apply whatever function we give it to each set in rest (T in the mathematical definition above). We can define that using lambda as follows.

(define (subsets s)
   (if (null? s)
       (list null)
       (let ((rest (subsets (cdr s))))
          (append rest (map (lambda (x) (cons (car s) x))
                            rest)))))

Here we're recursively calling subsets with (cdr s), which will append to that the car of s (which represents e from the mathematical definition) to each subset of (cdr s). The recursion stops when we run out of elements and the empty set is returned.

We can test it out with the example given.

> (subsets (list 1 2 3))
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

Related:

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