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