[plt-scheme] build-vector avoids sharing problem

From: Bill Richter (richter at math.northwestern.edu)
Date: Tue Feb 4 01:18:09 EST 2003

Advanced Student's function `build-vector' solves a sharing problem
that's puzzled me: How to define 2-d vector array where the "rows"
aren't all shared?  Below I get unwanted sharing with my first 2 tries
(using R5RS functions), and only the 3rd (with build-vector) works:

Welcome to DrScheme, version 203.
Language: Pretty Big (includes MrEd and Advanced) custom.
"#(0 0 0)"
#3(#0=#3(6 53 zzz))
"(make-vector 3)"
#3(#0=#3(6 53 zzz))
#3(#3(6 0) #3(0 53 0) #3(0 0 zzz))

Here's the code:

(define no-sharing (make-vector 3 #(0 0 0)))
(vector-set! (vector-ref no-sharing 0) 0 6)
(vector-set! (vector-ref no-sharing 1) 1 53)
(vector-set! (vector-ref no-sharing 1) 2 'zzz)
(print "#(0 0 0)")

(define no-sharing (make-vector 3 (make-vector 3)))
(vector-set! (vector-ref no-sharing 0) 0 6)
(vector-set! (vector-ref no-sharing 1) 1 53)
(vector-set! (vector-ref no-sharing 2) 2 'zzz)
(print "(make-vector 3)")

(define no-sharing (build-vector 3 (lambda (n) (make-vector 3))))
(vector-set! (vector-ref no-sharing 0) 0 6)
(vector-set! (vector-ref no-sharing 1) 1 53)
(vector-set! (vector-ref no-sharing 2) 2 'zzz)
(print "build-vector")

I'm writing some code to do some machine-intensive `tensor algebra'
calculations that have been done in the past in C, but Scheme seems
the right language, because there's so much recursion here.

I need a 2 parameter family of lists B(s,t), where 0 <= s, t < 50.

The list B(s,t) is computed from the earlier B(i, j) where either 
j < t, or i < s and j = t.

Only solution that pops into my head is to make a 2-d vector by 

(define solution (build-vector 50 (lambda (n) (make-vector 50))))

and then, having computed the list B(s,t), stick it into solution by 

(vector-set! (vector-ref solution s) t ****)

and then I can use it later by 

(vector-ref (vector-ref solution s) t ****)

Doesn't strike me as a real elegant solution, I hate to use mutation
when I don't "need" it, but it'll do I guess.

Shriram recommended I use Advanced Student, so I read more of HtDP,
and I think `define-struct' is pretty useful.  I'd essentially defined
some structs by hand, but without of course without the predicates.  I
think it organizes the thinking pretty well.  

See, in a tensor algebra (over the field Z/2 in my case), we have:

the variables lambda_0, lambda_1, lambda_2, lambda_3, ....

monomials = products of the variables

polynomials = sums of the monomials.

Naturally, that's 3 structs, Variable, Mono & Poly, and we have
functions between these structs, like 

Poly-first-element : Poly -> Mono

OK, the variables don't commute in the tensor algebra, but then we
"mod out" by some relations, and now we can move the polynomials
around by using the relations over & over.  And there's a
differential, so we can take the homology...  Funny thing, the tensor
algebra modulo these relations is called the "Lambda algebra".

Posted on the users mailing list.