Well, in C/C++, and most any other imperative languages (as you probably know) is O(1) for both reading and updating arrays. Until Haskell can do this, I don't think Haskell is a viable option for operating system design, computer graphics, or embedded applications. Thats a shame because Haskell can do pretty much anything else, and much better/safer than imperative languages -- at least until we get CPU's specially designed to run Haskell code at the machine-level. I was hoping that Haskell-prime would address this. I could be wrong but it really comes down to whether or not the Haskell code be optimized to use arrays in the same way that a C program would. And this optimization could be explicitly declared by the programmer if the language allowed for it, right? Don Stewart wrote:

lennart:

...

As for array updating, there are many ways to improve the O(n) update. You can use a tree representation and get O(log n) for all operations. You can use the array single threaded in the ST monad and get all the usual array operation complexities.

Or use a history/transaction list to average out the copy cost, or use fusion to minimise the updates required.

Making pure arrays efficient is a lot of fun, but it's a library issue, not a language one, necessarily.

-- Don

Ramin wrote:

Well, in C/C++, and most any other imperative languages (as you probably know) is O(1) for both reading and updating arrays. Until Haskell can do this, I don't think Haskell is a viable option for operating system design, computer graphics, or embedded applications.

There are two issues here, which I think were unnecessarily tangled together in your original post. First: you proposed arrays whose size is known and accesses checked at compile-time. Second: you proposed making arrays mutable so as to recover the expected time bounds for operations. The first is possible, but considerably more complex that your original post made it sound. The second, though, is already there in Haskell as it stands. Just use STArray, for example. The big difference is that with STArray, the side effects of your code, and the fact that the original copy of the array is destroyed, are acknowledged by the type system. You tried to give changeArrayFunc a type of a^10 -> a^10: a type that implies it computes a new value, but leaves the original array alone. Unless it does some analysis, that could be arbitrarily complex in general, to prove I never use the original array again, the compiler can *not* generate destructive code in this case. The ST monad *is* the general answer to this problem, so you should just use STArray, and you get what you want. -- Chris Smith