0

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)

Óscar López
  • 232,561
  • 37
  • 312
  • 386
user3435279
  • 85
  • 1
  • 8
  • 1
    [you have the power](http://stackoverflow.com/help/privileges/vote-up) to [up-vote](http://stackoverflow.com/help/why-vote) now. :) – Will Ness Jul 09 '14 at 22:24

3 Answers3

2

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.

Óscar López
  • 232,561
  • 37
  • 312
  • 386
1

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).

Community
  • 1
  • 1
Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • cheers. as i said to the dude above, the penny hasn't properly dropped yet (but i'm keeping at it so hopefully it will do eventually) – user3435279 Jul 07 '14 at 19:48
  • @user3435279 was my answer helpful at all? I thought the equational definitions should be clear enough. If *recursion* is your difficulty, try http://stackoverflow.com/a/19951540/849891 or http://stackoverflow.com/a/11666815/849891. It might seem mysterious at first, the ability to call itself, but the key is that it's not "self" that gets called - but rather a ***copy*** of self. – Will Ness Jul 08 '14 at 09:28
  • no it is dude, v helpful. at least today. yesterday brain wasn't so receptive but this recursion thing & SICP are hard (probably hardest thing i've ever studied & i've studied lots of stuff) – user3435279 Jul 08 '14 at 12:51
  • @user3435279 you know this joke, about how to boil some eggs? you need a pot, a stove, a water faucet and matches, and then you have a procedure how to boil yourself some eggs in a pot full of water by placing it on a stove and lighting it with a match, right? And what if you're already given a pot full of water with eggs in it, and a stove is already lit? How do you boil eggs then, in the spirit of *code reuse* / *structural recursion* ? – Will Ness Jul 08 '14 at 14:49
  • @user3435279 OK, here it is: you take the eggs out, pour out the water, turn off the stove, and are left with the situation you already know how to handle! :) IOW, don't try to see the big picture; work in-the-small. Which is the attitude of structural recursion: `(define (boil-some-eggs situation) (cond ((basic-situation? situation) (pour-water-in-put-eggs-in-turn-the-stove-on! situation)) (else (let ((basic-situation (analyze-into-constituent-parts situation))) (boil-some-eggs basic-situation)))))`. – Will Ness Jul 09 '14 at 11:23
  • consider the terseness of this question, its amazing (a) how different your & mr lopez's explanations of the answers are, & (b) how much study time i've been able to sink into it (~ 3 days) without properly feeling like i've cracked it. [ i think i'm about 85% there currently ] – user3435279 Jul 10 '14 at 18:45
  • @user3435279 what is still unclear? I don't see much difference BTW. :) He mentions `foldr` too (cf. my reference to "folding"). Did you like the joke at least? – Will Ness Jul 10 '14 at 18:58
  • lol. lots. not so much the joke itself but at your question of whether i like it. i mean, maybe when i've finished SICP & thinking recursively comes as easily as blowing bubbles... perhaps then i'll be able to process it as-a-joke. for now, like 99.9999% of people, its an exam question – user3435279 Jul 11 '14 at 13:37
  • Ah, the joke should've been: given eggs in a water in a pot and a burning stove, we'd just place the pot on the fire. ***But what would a programmer do?*** -- he'd take everything out because "that's the ***basic case*** we already know how to deal with". Funny. But actually this near-sighted attitude guarantees to him that he deals with the situation correctly (makes no errors trying to be smart about it). -- The counter-joke is about a centipede who gets asked, "how exactly *do* you walk with your 100 legs?" after which he becomes motionless, thinking which leg to move first. – Will Ness Jul 11 '14 at 14:05
  • @user3435279 (see also: http://stackoverflow.com/a/19951540/849891, near the end of that post). – Will Ness Jul 11 '14 at 14:09
0

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)))))
DanEEStar
  • 6,140
  • 6
  • 37
  • 52