[clean-list] help, update in place, two dimensional array.

[John van Groningen]

Carlos Aya wrote:
>I'm trying a two-dimensional array update in-place... and got lost.
>
>I have this utility function I did a while ago for update in place for one-dimensional arrays...
>
>// updates first parameter (array) in place with values from a function that takes as parameters the value at
>// index p and p itself
>updateInPlace :: *(a e) (e Int -> e) Int -> *(a e) | Array a e
>updateInPlace arr1 f maxPos = updateLoop_ arr1 f 0 maxPos
>where
>    updateLoop_ :: *(a e) (e Int -> e) Int Int -> *(a e) | Array a e
>    updateLoop_ arr1 f pos maxPos
>    | pos == maxPos  = arr1
>    # (v, arr1) = arr1![pos]
>    = {(updateLoop_ arr1 f (pos+1) maxPos) & [pos] = f v pos}
>
>If not the best implementation, at least worked for me.
>
>I'm now trying to port the following element-wise matrix multiplication (for the sake of a simple example)
>
>times :: {{#Int}} {{#Int}} -> {{#Int}}
>times m1 m2 = {{m1.[i,j] * m2.[i,j] \\ j <- [0..MAX_INDEX]} \\ i <- [0..MAX_INDEX]}
>
>into an efficient update in place in the first parameter... but this throws a compilation error
>
>times :: *{{#Int}} {{#Int}} -> *{{#Int}}
>times m1 m2 = updateInPlace m1 rowUpdate SIZE
>where
>    rowUpdate :: *{#Int} Int -> *{#Int}
>    rowUpdate row i = updateInPlace row (\v j = v * m2.[i,j]) SIZE
>
>And the error refers to rowUpdate, I believe, but refers to it curried, [i.e. like A -> (B -> C) instead of A B -> C]... and says that (B -> C) must be unique, I'm lost.
>
>Am I missing something?

If you use type *{{#Int}}, only the outer array is unique, but the
inner arrays are not. To make all arrays unique, use type *{*{#Int}}.
For better efficiency use *{#*{#Int}}.

The updateInPlace function can only update arrays of elements that are
not unique. If you want to use this function for a 2 dimensional array
of type *{#*{#Int}}, you need an update function that can also update
arrays with unique elements.

However, a unique element cannot be selected from an array using a![i],
because after the selection there would be 2 references to the element,
because the array still contains this element as well.
Therefore, the selection should be done using replace, which selects
the element from the array, and also stores a new value in the array.

For example:

updateUInPlace :: *(a .e) (.e -> .(Int -> .e)) Int .e -> *(a .e) | Array a e
updateUInPlace arr1 f maxPos d = updateLoop_ arr1 f 0 maxPos d
where
    updateLoop_ :: !*(a .e) (.e -> .(Int -> .e)) !Int !Int !.e -> *(a .e) | Array a e
    updateLoop_ arr1 f pos maxPos d
    | pos == maxPos  = arr1
    # (v,arr1) = replace arr1 pos d
    # (d,arr1) = replace arr1 pos (f v pos)
    = updateLoop_ arr1 f (pos+1) maxPos d

times :: *{#*{#Int}} {#{#Int}} -> *{#*{#Int}}
times m1 m2 = updateUInPlace m1 rowUpdate SIZE {}
where
    rowUpdate :: *{#Int} Int -> *{#Int}
    rowUpdate row i = updateInPlace row (\v j = v * m2.[i,j]) SIZE

For the current development version of the compiler the updateUInPlace
can be written without using replace, because the compiler recognizes
selections and updates of the same array element without using the
array in between. In such cases a unique element may be selected and
updated.

Kind regards.

John van Groningen