[plt-scheme] build-vector avoids sharing problem
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 :)