[plt-scheme] build-vector avoids sharing problem + tensor algebras

Lo, on Wednesday, February 5, Bill Richter did write:

>    From: "Richard C. Cobbe" <cobbe at ccs.neu.edu>
>    
>    However, you may not necessarily need to use side effects to
>    initialize your arrays.  If you can write an expression that
>    computes the value for location (i,j) from i and j, why not simply
>    use this in a nested build-vector?  Something like the following:
>    
>    (build-vector 50 
>                  (lambda (i) 
>                    (build-vector 50
>                                  (lambda (j)
>                                    (compute-element i j)))))
>    
>    Here, compute-element may be your B(i,j); I didn't find the description
>    above very clear on this point.
>    
> My B(i,j) will be the value of your (compute-element i j).
> 
> The problem is that (compute-element i j) needs to reference all
> earlier elements of the 2-d array.  

Ah.  In that case, it sounds a bit like dynamic programming to me.  Any
reasonably thorough algorithms text should have more details; I know
Cormen, Leiserson, and Rivest has it.

One typical implementation of dynamic programming (the one in CLR) uses,
wait for it, an N-dimensional array with side effects to initialize
everything.  I can think of a couple of different strategies that use
different data structures and no side effects, but they require rather
more code.  Another possible alternative which is only slightly more
inconvenient than side effects involves the use of promises.

Richard