[plt-scheme] HTDP 21.1.2

From: Richard Cobbe (cobbe at ccs.neu.edu)
Date: Mon Jul 10 12:20:34 EDT 2006

On Mon, Jul 10, 2006 at 05:05:43PM +0100, wooks . wrote:
> 
> http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-27.html#node_sec_21.1
> 
> OK I'm flummoxed on the bit that asks you to use map to define fold.
                                                   ~~~~~~~~~~~~~~~~~~
Based on the rest of your question, it looks like you understand this,
but just to be sure we're all on the same page, 21.1.2 asks you to use
fold to define map, not the other way around.

> (define (fold baseCase op alon)
>  (cond
>    [(empty? alon) baseCase]
>    [else (op (first alon)
> 	     (fold baseCase op (rest alon)))]))
> 
> (define (sum alon)
>  (fold 0 + alon))
> (define (prod alon)
>  (fold 1 * alon))

That's correct.  (BTW, it's conventional to define fold with op as the
first argument rather than base-case, but that's a minor issue.)

> All good .... the append using fold was pretty straightforward but if I 
> want to map square on to a list
> 
> (define (square n) (* n n))
> 
> (myMap square (list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16))
> 
> I don't see how this can be done with fold.... is this a trick part of the 
> question...(I suspect not).

No, it's not a trick, though it is more challenging than using fold to
define sum or product.  One can certainly define map in terms of fold.

Here's a suggestion: write down the original definition of sum on paper
(or print it out).  Circle the parts of the definition that you turned
into additional parameters when you abstracted sum and product into
fold.

Now, think about editing the definition of sum to change it into the
definition of map.  What changes do you need to make?  If your
definition of fold is correct (that is, if it's sufficiently general),
then all of those changes should be inside the circles that you drew in
the previous paragraph.  Once you've made those changes, that should
give you a clue.

Richard


Posted on the users mailing list.