Problem with array manipulation functions

[Martin Wierich]

Hi Pablo,

You wrote:

> Hi!
> I'm having some problems when trying to handle the array belonging
> to this data structure:
>
> :: VEBTree a = ManyVEB a a a .{VEBTree a} (VEBTree a)
>
> I'd like (for sake of efficiency) to be able to write an insertion function
> similar to this one:
>
> insert :: *(VEBTree a) a -> *(VEBTree a)
> insert (ManyVEB ru f l det res) i =
>   let!
>     a = i / ru
>     b = i mod ru
>     (w,det1) = uselect det (toInt a)
>     w1 = insert w b
>     det2 = update det1 (toInt a) w1
>  in ManyVEB ru f l det2 res
>

...

> The uselect function seems to nuke the
> uniqueness of the array elements (Is this right?), and I need'em to be unique
> for the recursive step of the insertion! .

That's the point. You have an array with unique elements. The uselect function
returns both an element of an array ("w") and the array itself ("det1"). This
means that there are two references to that element: "w" is of course a reference
and "det1" is also a reference, because this array still contains the element.
That's why the element that's returned by uselect is non unique.

To access an array element in a unique way you have to use the "replace"
function:

  replace :: !*(a .e) !Int .e -> (.e, !*(a .e))   | (???)

This function takes an array a, an index i and a possibly unique element e. It
returns the desired (possibly unique) element a.[i] and an array { a & [i]=e }.
The returned element can be unique because the returned array has no reference to
the element anymore (if the array elements are unique): the reference has been
overwritten. Try the following:

:: *VEBTree a = ManyVEB a a a *{*VEBTree a} (VEBTree a)
              | Empty

insert_ (ManyVEB ru f l det res) i =
  let!
    a = i / ru
    b = i mod ru
    (w,det1) = replace det (toInt a) Empty
    w1 = insert_ w b
    det2 = update det1 (toInt a) w1
 in ManyVEB ru f l det2 res

BTW: check out strict and unboxed arrays. They might be faster.

greetings
  Martin Wierich