[plt-scheme] HtDP

From: dave yrueta (dyrueta at gmail.com)
Date: Mon Jul 7 18:11:24 EDT 2008

Hi All –
Am having problems with the last part of Exercise 21.1.2, which
requires defining function ‘map in terms of function ‘fold.

‘Fold is an abstraction of two similar example functions, ‘sum and
‘product, reproduced below:

(define(sum a-list-of-numbers)
  (cond
    [(empty? a-list-of-numbers)0]
    [else
     (+(first a-list-of-numbers)
       (sum(rest a-list-of-numbers)))]))

(define(product a-list-of-numbers)
  (cond
    [(empty? a-list-of-numbers)1]
    [else
     (*(first a-list-of-numbers)
       (product(rest a-list-of-numbers)))]))

The design recipe for abstracting functions instructs us to compare,
abstract and then test.  After comparing the two functions, I
abstracted two common values: the answer to the first conditional
clause, and the function applied to the first item on the list
parameter. I named the first abstracted value ‘th for threshold, and
the second ‘f for function.   The resulting function named ‘fold
looked like this:

(define(fold f th lox)
  (cond
    [(empty? lox)th]
    [else
     (f (first lox)
        (fold f th (rest lox)))]))

Next, I tested ‘fold by defining functions which made the abstracted
values of the original functions arguments in ‘fold:

(define(abstract-from-sum lox)
  (fold + 0 lox))

(define(abstract-from-product lox)
  (fold * 1 lox))

(equal?(product(list 1 2 3))
       (abstract-from-product(list 1 2 3)))

(equal?(sum (list 2 3 4))
      (abstract-from-sum (list 2 3 4)))

The results were consistent.

I then defined a version of function ‘append in terms of ‘fold, which
seems to work when the list acting as the second parameter of ‘append
is made the threshold of ‘fold:

(define(apend loX1 loX2)
  (fold cons loX2 loX1))

However, I’m puzzled on how to approach defining ‘map in terms of
‘fold.  ‘Map creates a list of values by applying some function (f) to
each item on a list:

(define(mapp f lox)
  (cond
    [(empty? lox)empty]
    [else
     (cons(f(first lox))
            (map f (rest lox)))]))

(define(add10 x)
  (+ x 10))

(check-expect(mapp add10 (list 1 2 3))(list 11 12 13)) = "All tests
pass!"

So defining ‘map in the terms I’ve defined ‘fold requires double-duty
on the part of parameter ‘f: it must first introduce the primitive
‘cons which starts a list, and then it must apply a function ‘f to
each member of the list:

(define(mapp2 f lox)
  (fold (cons f) empty lox))

This won’t work, because (cons f) is not a legitimate expression.  I
started work on next problem in the meantime, and that seems even more
puzzling, so I feel like there is some basic concept about abstraction
that I’m not getting.  Any suggestions?

Thanks,
Dave Yrueta


Posted on the users mailing list.