A simple doubt about // operator ....

[Hal Daume III]

Hi,

>      The GHC documentation says about // (update array operator):
> 
> "For MOST array types, this operation is O(n) where n is the size of the
> array. However, the DiffArray type provides this operation with complexity
> linear in the number of updates".
> 
>   The word "MOST" sugggests that there are other array variants for which //
> is linear on the number of updates. For unboxed arrays, // is linear on the
> array size or number of updates ?

(//) is always* linear in the array size
  * except for DiffArrays

this is because it copies the array, which takes linear time in the size
of the array.

In general, I think the name "array" for these data structures is a bit
misleading, since nearly everyone expects an array to have constant time
read and update, while these only have constant time read.

 - Hal