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

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!