I've used this a fair amount: e.g. 2D grids going from (-n,-n) to (n,n).  This is one of the things I liked about Haskell arrays, in that you _weren't_ limited to the [0,n-1] bounds found in C-based languages (and that annoyed me to no end when I was using them).  Even

And to be honest, it's fairly easy to wrap the array functions to specialize them for (0..n-1). It just took me a while to figure out that I would have to make my own array module to stop getting those off-by-one errors.

...

 Meanwhile, they lack basic features like concatenation.

I obviously don't know what you're doing with arrays, but this sounds a bit like using the wrong datatype for the job: if you're concatenating arrays, wouldn't you have to explicitly create or extend one of those arrays to get the contiguous memory (unless you're using a DiffArray)?

Yes, that's also the case for vector, or bytestring, or any of the other array libraries. Concatenating arrays is not a crazy thing to do if it's uncommon and the arrays are not large. You have to copy them in imperative languages too, so it's hardly unique to haskell. Admittedly, I could have used an IntMap but it's a small dense array that's very infrequently changed, and I do mostly iterating forwards and backwards and a plain array seemed simpler than an IntMap with the condition that the keys should be consecutive.

To an extent, I wonder how much of this has been that arrays were considered to be bad in Haskell, so no-one used them and no-one bothered to try and improve the API much (and instead went and created Vector, etc.).

Right, so we have arrays with nicer APIs, it's just that IArray has been kind of left behind. I don't think arrays are bad in haskell, if that were true all those array libraries wouldn't be so popular! They might not be quite the go-to type as in other languages, but they still have their uses.

Any particular reason you used Data.Graph rather than fgl, etc.?

Well... it's built-in... I needed something simple... so I just hit the ghc stdlib doc and searched for "graph". Is this another "left behind" module? And if so... well, maybe it's in the same situation as IArray.

I see there are two possible sources of your "problems" here:

1. The underlying data structure (index types and bounds, etc.) 2. The API

You mainly seem to have an issue with the API itself.  My guess is that the API for array hasn't changed much because it was already there and a boot library (so incremental changes, etc.) whereas when vector, etc. was being written the opportunity was being taken to create an API better suited for the task, taking into account people's usage of array.

Right, it's hard to dislike the underlying data structure, arrays are about as simple as you can get :) My guess was the same as yours, i.e. that it's been sort of neglected but it's a bootlib and H98 so nothing can happen to it quickly. I can't realistically suggest a course of action here, other than "gosh someone should update these modules" to which everyone is likely to say "yes, it would be nice if you did that" :) Or maybe in 10 years vector will be mature and standard and the old Array stuff can be deprecated and removed. So that's why this was more of a little rant than actual constructive comment. Maybe at the least I could submit a patch to the IArray haddock saying "there are other array interfaces out there on hackage if you're looking for the 'default array' and this one isn't doing it for you". Maybe the same with Data.Graph and fgl, if that's so much nicer. But then, you know, it feels strange for a stdlib to come with such disclaimers :)

On 03/09/2011, at 03:04, Ivan Lazar Miljenovic wrote:

On 3 September 2011 11:38, Evan Laforge wrote:

...

The result is that my first contact with haskell arrays left me with the impression that they were complicated, hard to use, and designed for someone with different priorities than me. Of course, Data.Vector didn't exist back then, but if someone were new to haskell now I would recommend they skip Data.IArray and head straight for vector.

To an extent, I wonder how much of this has been that arrays were considered to be bad in Haskell, so no-one used them and no-one bothered to try and improve the API much (and instead went and created Vector, etc.).

It's rather that some considered the IArray API to be inadequate most of the time. Really, H98 arrays aren't very good at anything they do. For collective operations, you are supposed to convert the array to a list, work on the list and then convert it back to an array which just seems wrong. Multidimensional arrays can't be sliced and diced in the style of Repa or NumPy. In general, H98 arrays seem to have been designed with the goal of providing a container with O(1) indexing. They do that, I suppose, although they aren't very well integrated with the rest of the language and they have conceptual problems (such as requiring two bounds checks for one array access). But requirements have shifted quite a bit since then. Now, people want to write real array programs and they want those to be fast. Personally, I don't know how to improve the H98 array API to provide this. You basically need to create a completely new API based on different principles. Roman

Jon Fairbairn wrote:

Roman Leshchinskiy writes:

No, arrays were not considered to be bad, they were designed with parallelism in mind.

I'm not sure how this can be the case if, as discussed below, most array operations have to go through lists, an inherently sequential data structure.

...

It's rather that some considered the IArray API to be inadequate most of the time. Really, H98 arrays aren't very good at anything they do. For collective operations, you are supposed to convert the array to a list, work on the list and then convert it back to an array which just seems wrong.

I am unconvinded that this is any more wrong than using a for loop in an imperative language.

Oh, definitely. In fact, I consider using a for loop even more wrong, you really want to use collective operations instead whenever possible. But I don't think for loops are the right benchmark for ease of use.

Remember that the lists are lazy, so it’s misleading to say “convert the array to a list” since what happens most of the time is that elements are taken out of the array and passed to the processing function and then thrown away before the next element is processed.

Efficiency isn't even the biggest problem here. Whenever you want to perform a collective operation on an array, you have to do the actual work on an entirely different data structure. So I, as a programmer, have to say: "Convert this array to a list, then do something with the list and then convert the resulting list back to an array". To me, at least, this is very inconvenient and requires a context switch. No other widely used container type requires you to do that.

...

Multidimensional arrays can't be sliced and diced in the style of Repa or NumPy.

I’m not familiar with Repa or NumPy, but what can they do that cannot be done with judicious use of ixmap, which is a very powerful mechanism.

Yes, it is quite powerful but not very convenient. Just as an example, if A is a matrix, then A[3,:] gives you the 4th row and A[:,3] the 4th column in NumPy. You can do that with ixmap but it's far more involved. It also isn't powerful enough since it doesn't support certain highly useful uses of shape polymorphism (an example is a generic concat which decreases the dimensionality of any array by 1). This is discussed in detail in http://www.cse.unsw.edu.au/~chak/papers/repa.pdf.

...

In general, H98 arrays seem to have been designed with the goal of providing a container with O(1) indexing. They do that, I suppose, although they aren't very well integrated with the rest of the language

Can you give examples?

My favourite is the interaction between arrays and Enum. If I want to implement a generic enumFromTo m n that produces an array, I have to create the list [m .. n], take its length (which forces the entire list into memory) and then create an array of that length and fill it from the list. There doesn't seem to be any other way of doing it. This is a deficiency of Enum, really, but that's what I mean by not being well integrated. There are other examples like this.

...

and they have conceptual problems (such as requiring two bounds checks for one array access).

Assuming that you mean that for safe array access where nothing is known about the index at compile time, since any sort of array has at least a beginning and an end, they all require two bounds checks. Once you do know something about the index, it’s a question of implementation.

That's not what I meant. You really need to do two full bounds checks, one against inRange and one against the actual length of the array. Here is the relevant comment from the GHC libraries: Note [Double bounds-checking of index values] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ When you index an array, a!x, there are two possible bounds checks we might make: (A) Check that (inRange (bounds a) x) holds. (A) is checked in the method for 'index' (B) Check that (index (bounds a) x) lies in the range 0..n, where n is the size of the underlying array (B) is checked in the top-level function (!), in safeIndex. Of course it *should* be the case that (A) holds iff (B) holds, but that is a property of the particular instances of index, bounds, and inRange, so GHC cannot guarantee it. * If you do (A) and not (B), then you might get a seg-fault, by indexing at some bizarre location. Trac #1610 * If you do (B) but not (A), you may get no complaint when you index an array out of its semantic bounds. Trac #2120 At various times we have had (A) and not (B), or (B) and not (A); both led to complaints. So now we implement *both* checks (Trac #2669). Roman

On Tue, Sep 6, 2011 at 13:40, Andrew Coppin wrote:

But then, lists are in the standard Prelude, and hard-wired into the language syntax. Streams aren't exposed by any moderately standard library. Even the stream-fusion library treats streams as a sort of "under the covers" thing to deforest lists.

These two statements taken together are slightly ironic: stream-fusion's goal is to make streams wired-in syntax by borrowing the syntax from lists. -- brandon s allbery allbery.b@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms

I am unconvinded that this is any more wrong than using a for loop in an imperative language. Remember that the lists are lazy, so it’s misleading to say “convert the array to a list” since what happens most of the time is that elements are taken out of the array and passed to the processing function and then thrown away before the next element is processed.

I don't think it's misleading to say "convert to a list". Without the presence of some fusion-esque optimization, the entire list is created and destroyed. It's nice if it can be done incrementally, but that's still a lot of garbage. And for a concrete example, consider concatenating a bunch of arrays. Unless it gets deforested, you have to copy each element a couple of times, since there is intermediate list concatenation. And then this kind of API is incompatible with unboxing... if you later decide to unbox the data type then I don't think you could ever get the intermediate list approach to work, since it's boxed by nature.

I’m not familiar with Repa or NumPy, but what can they do that cannot be done with judicious use of ixmap, which is a very powerful mechanism.

I spent hours messing with ixmap before getting something that seemed to work right. Maybe I just have more trouble than most with it, but though it may be powerful it's certainly not easy to use! After spending too much time on it I learned to just convert to a list and back.