[plt-scheme] Request for comments on possible planet functions

Thanks to everyone for the comments.  I've been slowly integrating
peoples comments in, and hope to relase something soon.



On 1/19/07, Eli Barzilay <eli at barzilay.org> wrote:
> On Jan 19, John Clements wrote:
> > Don't use "list?".  It forces a traversal of the full list.  It turns
> > a linear operation into an n^2 one.  Since the cdr of a list is a
> > list, you can easily fix this, like this:
> >
> > (define (maprec f tree)
> >    (cond [(pair? tree) (cons (maprec f (car tree))
> >                              (maprec f (cdr tree)))]
> >          [(null? tree) null]
> >          [else (f tree)]))
> >
> > Also, this (and any-rec) could probably be made special cases of
> > some kind of pair-fold.
>
> What do you mean "probably"??  All you need is to distinguish the
> tree-traversal parts from the answer construction parts, then abstract
> the latter parts.
>
>   (define (tree-fold f-pair init f-item tree)
>      (cond [(pair? tree) (f-pair (tree-fold f-pair init f-item (car tree))
>                                  (tree-fold f-pair init f-item (cdr tree)))]
>            [(null? tree) init]
>            [else (f-item tree)]))
>
> Should be an almost-mechanical transformation, but...
>
>
> > > (define (flatten tree)
> > >   (fold (lambda (item list-so-far)
> > >           (if (not (list? item))
> > >               (append list-so-far (list item))
> > >               (append list-so-far (flatten item))))
> > >         `()
> > >         tree))
> >
> > Your running time here is going to be very very high; each time you
> > add an item to the list, you're doing (append list-so-far (list
> > item)) which will require re-consing up the whole list.  You get a
> > big win just by switching to 'foldr' (or fold-right, as the case may
> > be).  Also, stay away from list?, as before.
>
> Using the above:
>   (define (flatten tree) (tree-fold append null list tree))
>
>
> > In fact, you can also avoid the append completely by using an
> > accumulator.  This seems to work, and it should be linear in the size
> > of the tree:
> >
> > (define (flatten tree so-far)
> >    (cond [(pair? tree) (flatten (car tree) (flatten (cdr tree) so-far))]
> >          [(null? tree) so-far]
> >          [else (cons tree so-far)]))
>
> (And this version is still better than the one that uses tree-fold,
> which shows why creating a fold-er function is not completely
> mechanical, since you need to choose which kind of fold you want...)
>
> --
>           ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
>                   http://www.barzilay.org/                 Maze is Life!
>


-- 
((lambda (y) (y y)) (lambda (y) (y y)))