[plt-scheme] HtDP

From: David Yrueta (dyrueta at gmail.com)
Date: Wed Jul 9 10:36:44 EDT 2008

Hi Todd & Marco --

Thank you both for responding.

Perhaps my problem lies with my understanding of contracts?  Here's what I
have so far....

;contract for fold
;(X X > X) X (listof X) > X

;contract for abstract-from-sum and abstract-from-product
;(number number > number) number (listof numbers) > number

;contract for append
;lst lst > lst

;contract for append-from-fold
;(lst lst > lst) lst lst > lst

;contract for map
;(X > Y) (listof X) > (listof Y)

I feel my understanding is running aground on two counts.  First, it appears
to me that my contract for append--

;contract for 'append
;(lst lst > lst) lst lst > lst

--does not "map" onto my contract for 'fold --

;contract for 'fold
;(X X > X) X (listof X) > X

After substituting 'append's 'lst parameter for all instances of X in 'fold,
'fold's third parameter becomes (listof lst).  That can't be right?  Is this
where I'm floundering?

Second, I'm not sure how to resolve the discrepancy between the argument
requirements for the function parameters in 'fold and 'map.  'Fold's
function parameter requires two like arguments, and converts them into a
like value (X X > X); 'map's function parameter requires only one argument,
and coverts it into a different type of value (X > Y).  So it would seem
that the designer of map-from-fold is constrained by the structure of 'fold
to make 'cons the argument for the function parameter, since it the only
function that accepts two arguments and outputs a list. The final value of
any list must be an empty list, so it seem that limits 'threshold's value to
'empty.  The only parameter left is the list argument, and I suppose that's
where the list from map goes. So the result is this....

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

... which simply outputs 'map's list parameter, returning me to square 1,
and leaving 'f unused.

The only other thing I can think of is to take up Todd's suggestion, and
start off 'map by applying 'f directly to (first lox) --

(define(map f lox)
   (f((first lox).....

--'cons-ing that onto the front of a list

(define(map f lox)
   (cons(f((first lox)....

-- and then introducing 'fold in the manner above, with one change: making
'(map f (rest lox)) the argument for 'fold's third parameter, since we know
'map, according to its' contract, is supposed to produce a list.

Hmm, that seems to work as long as the first conditional clause answers to

(define(mapp2 f lox)
    [(empty? lox)empty]
    [else(cons(f(first lox))
              (fold cons empty (mapp2 f (rest lox))))]))

(Sorry about the discursive prose. Writing this stuff out helps me work thru
the problem-solving process....)

Could this be the solution sought after by HtDP?  If so, it seems to me like
a *much* more complicated version of the original 'map, or an instance of
spending dollars to save pennies......

At any rate, your thoughts and suggestions are very much appreciated,
especially since I'm trying to work thru HtDP on my own with assistance only
from the members of plt-scheme.

Many thanks,
Dave Yrueta

On Mon, Jul 7, 2008 at 4:04 PM, Marco Morazan <morazanm at gmail.com> wrote:

> On Mon, Jul 7, 2008 at 6:11 PM, dave yrueta <dyrueta at gmail.com> wrote:
> >
> > (define(fold f th lox)
> >  (cond
> >    [(empty? lox)th]
> >    [else
> >     (f (first lox)
> >        (fold f th (rest lox)))]))
> >
> What is the contract for fold?
> >
> > (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?
> >
> Here's where a contract is going to be useful for you. What does fold
> expect as arguments? Certainly, (cons f) is not something fold is
> expecting as its first argument.
> Cheers,
> Marco
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20080709/b6835d5d/attachment.html>

Posted on the users mailing list.