[plt-scheme] build-vector avoids sharing problem

From: Bill Richter (richter at math.northwestern.edu)
Date: Mon Feb 10 00:51:36 EST 2003

Thanks to John Clements <clements at brinckerhoff.org>, who explained my
error in my discussion of HtDP's discussion of the accumulator-style
version of factorial.  I wrote:

   BUT: what if we wanted all of the earlier factorials too:
			1! 2! 3! ... (n-1)! n!
   Then clearly accumulator-style is better, because we calculate all
   the earlier factorials along the way to n!

As John pointed out, I'm making 2 errors: 

1) the accumulator-style factorial doesn't calculate the prior
   factorials.

2) Plain recursion gives a perfectly good function calculating all the
   prior factorials.

I'll do (2) first, as it's more important.  Here's John's code:

(define (all-prior-factorials n)
  (if (= n 1)
      (list 1)
      (let ([remaining (all-prior-factorials (- n 1))])
        (cons (* n (first remaining))
              remaining))))

We get this from the simplest considerations of recursion.  I found
John's code really surprising, because I was trying to modify existing
factorial code.  From simple recursion 101:

We want a function F with F(n) = (n! ... 1!).  

The obvious recursion relation is 

F(1) = (1)
F(n) = G( F(n-1), n)

where G(l_1 ... l_k), n) = (n*1_1, l_1, ..., l_k) 

or in Scheme lingo, 

(G lofax n) = (cons (* n (first lofax)) lofax) 

That's the simplest kind of recursive function to build, and there are
many examples like this in TLS, and I just bothered to code it up
myself, and I got exactly John's function!

(define (F n)
  (if (= n 1)
      (list 1)
      (let 
          ([lofax (F (sub1 n))])
        (cons (* n (first lofax)) lofax))))

(F 6)     ;=> (720 120 24 6 2 1)


(1) was plain wrong too.  I didn't bother to look before posting, but
here's HtDP's accumulator-style factorial, from section 31.3
Transforming Functions into Accumulator-Style:

;; ! : N  ->  N
;; to compute n  ·  (n - 1)  ·  ...  ·  2  ·  1
(define (! n0)
  (local (;; accumulator is the product of all natural numbers in [n0, n)
          (define (!-a n accumulator)
            (cond
              [(zero? n) accumulator]
              [else (!-a (sub1 n) (* n accumulator))])))
    (!-a n0 1)))

See, I thought it would iteratively construct the numbers in sequence

1, 2!, 3! .... n!

But it doesn't.  It construct the number sequence

n, n(n-1), n(n-1)(n-2), ....  n!

I was thinking instead of the thinly disguised iteration:

(define (list-prior-factorials n)
  (list-prior-factorials-accum n 1 (list 1)))

(define (list-prior-factorials-accum n multiplier lofax)
  (if (= n 0)
      lofax
      (list-prior-factorials-accum 
       (sub1 n)
       (add1 multiplier)
       (cons (* multiplier (first lofax))
             lofax))))

(list-prior-factorials 6)  ; => (720 120 24 6 2 1 1)

And this is my real interest here: I think that's a real kludge.  I do
this sorta Scheme coding plenty, and I don't like it.  I want to be
more elegant, and John gave me a good tip!

BTW I complained earlier about the colorizing of Check Syntax.  But
now I like it a lot!  Here's the point:

Advanced Scheme won't let you load files with
(load "filename.scm")
and I think I know why now:  Hot Pink!

Function names defined in filename.scm will be colored Hot Pink
because they're treated as unbound variables.

And I thought that was garish.  But reading HtDP I noticed no Hot
Pink, and so I looked in Preferences...

Well, now I like Hot Pink!  I think it looks fine for the function
names in my earlier files, since they're distinctive names, I know
they're not unbound variables.

And I do think that colorization adds greatly to readability.  I was
skipping a lot of lines in order to "see" my file.  With colors, I can
get rid of the newlines, and that makes for a different kind of
readability.  If a function definition goes on for 6 screenfuls...

I finished my matrix code (homology of the Lambda algebra), at 800+
lines, and it's not pretty, or blindingly fast, but I'm bubbly :)


Posted on the users mailing list.