SICP Exercise 2.33 issue

0
votes

having a bit of a problem with this exercise. specifically, 'seeing' how the lambda expression works

the exercise itself says this..

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

has to turn into this...

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

but i don't understand. i mean, i see that the 'accumulate' procedure follows the (define (accumulate op initial sequence)... form

so, does this mean (lambda (x y) (cons (p x) y)) is the 'op' part? & if so, what are x & y & how are they passed into the equation?

(decent explanation much appreciated)

3
lambdaschemelispsicp
you have the power to up-vote now. :) – Will Ness

3 Answers

2
votes

First, let's take a look at accumulate as defined in the book:

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

Basically, it's an ad-hoc implementation of foldr (a.k.a. fold-right), a higher-order procedure that processes an input list, applying a certain operation on each element and accumulating the result.

Notice that the op parameter is a procedure that looks like this (let's rename x and y to something more meaningful):

(lambda (element accumulator) <body>)

In the above, element represents the current element in the input list, each one of the elements is processed in turn in left-to-right order, and accumulator is the accumulated value of the output, which is being built recursively as we traverse the list. The <body> part takes care of updating the accumulated value, by doing something with the current element and the accumulated value. Now, let's take a look at how we usually write map:

(define (map p sequence)
  (if (null? sequence)
      null
      (cons (p (car sequence))
            (map p (cdr sequence)))))

Do you notice the pattern? map is very, very similar to accumulate, we just have to:

  1. Pass an appropriate initial value: null will be perfect
  2. Provide an op procedure that applies p to the current element in the list and conses it to the result of the recursive call

And that's exactly what we do, when we call accumulate with just the right parameters:

(define (map p sequence)
  (accumulate (lambda (element accumulator)
                (cons (p element) accumulator))
              null
              sequence))

The key insight to notice is that this line in the lambda body:

(cons (p element) accumulator)

Is doing exactly the same as this other line in the original map:

(cons             (p (car sequence))            (map p (cdr sequence)))
 ^^^^             ^^^^^^^^^^^^^^^^^^            ^^^^^^^^^^^^^^^^^^^^^^
 cons both parts  apply `p` on current element  all this is the accumulated value

To see why, use the substitution model and replace op, initial and sequence (the parameters in accumulate) with the actual values that we passed as arguments.

1
votes

so, does this mean (lambda (x y) (cons (p x) y)) is the 'op' part?

yes.

& if so, what are x & y & how are they passed into the equation?

x is "the current element" and y is "the result of recursively calling (accumulate ...) on the rest of the list".

Here's what this means. Each given list is seen as a cons pair - a pair of its car and its cdr. The value of a list's car goes into x, and of cdr - to the recursive call whose result goes into y. Or in equational style,

accumulate( op, z, CONS(e,es) ) = op( e, accumulate(op, z, es) )

where CONS(e,es) is not a function call, but a data representation (using the upper case to signify this) - a cons cell with e in its car and es (read: eez, like in e, plural) in its cdr. So when op(x,y) = ... is called, x = e and y = accumulate(op, z, es) are passed into it.

The above equation defines the function accumulate. One more equation is needed, for the NIL case:

accumulate( op, z, NIL ) = z

Thus it is assumed that op is a binary operation (i.e. receiving two arguments), able to deal with results of accumulate as its second argument. This pattern of list processing is known as "folding", or "catamorphism" - i.e. processing the data down, analyzing the data into its constituent parts, and recombining them in a certain fashion, arranging for a certain "call protocol" for the binary operation.

There are other patterns as well, e.g. a so-called "paramorphism",

accumulate2( op, z, NIL ) = z
accumulate2( op, z, CONS(e,es) ) = op( e, es, accumulate2(op, z, es) )

Here the operation is assumed to be ternary (i.e. receiving three arguments), receiving the current element, the rest of input list, and the result of recursive processing of the rest of the input list. It is useful in implementing patterns of data processing which need to have access to input as well as output (what's sometimes referred to, cryptically, as "having your cake and eating it too").

To be more useful these definitions need to be encoded lazily, so op has a choice of whether to force the recursive result or not, to be able to abort early (see e.g. this).

0
votes

What helped me a lot in some of the exercises in this section of SICP was to introduce some print statements for seeing what is happening in the calls of accumulate or other functions which are called recursively.

Like that: (I am using Racket so I am not sure if the printf is also defined in other Schemes)

(define (accumulate op initial seq)
  (printf "op: ~a, initial: ~a, seq: ~a\n" op initial seq)
  (if (null? seq)
      initial
      (op (car seq)
          (accumulate op initial (cdr seq)))))