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 _______________________________________________ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
