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

On Jan 18, 2007, at 2:40 PM, Corey Sweeney wrote:

> Like most people, I've built up a small library of functions that i  
> seem to use over and over again, and are not specific to any  
> individual application that I write..  I was considering makeing a  
> planet package out of them, but before I do, If anyone has comments  
> on them, I'd love to hear them.  I'm guessing i'm not the first  
> person to have written some of these functions.
>
> Here are the first few that I'm considering of posting:  {examples  
> on how to use them follows most of the non-obvious functions}
>
...


> ;;maprec maps func to all elements of a tree, but only the elements  
> (no lists)
> (define (maprec func tree)
>   (if (not (list? tree))
>       (func tree)
>       (map (lambda (x) (maprec func x)) tree)))

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.

>
>
> (define (unique list-in)
>   (cond ((null? list-in)
>          list-in)
>         (#t
>          (cons (first list-in)
>                (unique (filter (lambda (x) (not (equal? x (first  
> list-in))))
>                                (rest list-in)))))))

This is always n^2.  It's quicker just to sort the list and then make  
one pass to remove duplicates.

>
>
> (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.

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)]))



Hope this helps,

John Clements

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2484 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20070119/054e418b/attachment.p7s>