[plt-scheme] Re: scribblings on PLT Scheme 4.0

From: Kyle Smith (airfoil at bellsouth.net)
Date: Tue May 29 02:38:25 EDT 2007

Matthew Flatt <mflatt at ...> writes:

> Well, I think it was an interesting comparison. The example shows how
> replacing `append!' with `append' can lead to touching more than twice
> as much memory (and therefore suffer more than a 2x hit) without
> affecting asymptotic complexity.
> Still, at this point, I'm interested in hearing about the overall
> effect on realistic programs (instead of just microbenchmarks) if
> anyone has an example to measure it.
> Matthew


I gave you a version that I was playing with that has two appends.
You can get slightly better times with this one.


(define (fringe! x:xs)
    [(null? x:xs) ()]
     (let ([x (car x:xs)][xs (cdr x:xs)])
         [(null? x) (fringe! xs)]
         [(atom? x) (cons x (fringe! xs))]
          ((lambda (t)
               [(not (null? t)) (append! t (fringe! xs))]
               [else (fringe! xs)]))
           (fringe! x))]))]))


The ratio's between the append and append! version is the
same either way, but for completeness sake, this is the better


airfoil at bellsouth dot net

Posted on the users mailing list.