Why doesn't Haskell provide folds for one-dimensional Arrays?

Question

Data.Array doesn't provide folds for the Array type.

In Real World Haskell (ch. 12), the reason is said to be that Arrays could be folded in different ways based on the programmer's needs:

First of all, there are several kinds of folds that make sense. We might still want to fold over single elements, but we now have the possibility of folding over rows or columns, too. On top of this, for element-at-a-time folding, there are no longer just two sequences for traversal.

Isn't this exactly true of Lists? It's very common to represent e.g. a matrix with a multidimensional List, but there are still folds defined for one-dimensional Lists.

What's the subtlety I'm missing? Is it that a multidimensional Array is sufficiently different from an Array of Arrays?

Edit: Hm, even multidimensional arrays do have folds defined, in the form of instances of Data.Foldable.[0] So how does that fit in with the Real World Haskell quote?

[0] http://hackage.haskell.org/packages/archive/base/4.6.0.0/doc/html/Data-Foldable.html

Answer 1

Since you mention the difference between a "multidimensional" Array and an Array of Arrays, that will illustrate the point nicely, alongside a comparison with lists.

A fold (in the Foldable class sense) is an inherently linear operation, just as lists are an inherently linear structure; a right fold fully characterizes a list by matching its constructors one-for-one with the arguments to foldr. While you can define functions like foldl as well, there's a clear choice of a standard, canonical fold.

Array has no such transparent structure that can be matched one-for-one in a fold. It's an abstract type, with access to individual elements provided by index values, which can be of any type that has an Ix instance. So not only is there no single obvious choice for implementing a fold, there also is no intrinsic linear structure. It does so happen that Ix lets you enumerate a range of indices, but this is more an implementation detail than anything else.

What about multidimensional Arrays? They don't really exist, as such. Ix defines instances for tuples of types that are also instances, and if you want to think of such tuples as an index type for a "multidimensional" Array, go ahead! But they're still just tuples. Obviously, Ix puts some linear order on those tuples, but what is it? Can you find anything in the documentation that tells you?

So, I think we can safely say that folding a multidimensional Array using the order defined by Ix is unwise unless you don't really care what order you get the elements in.

For an Array of Arrays, on the other hand, there's only one sensible way to combine them, much like nested lists: fold each inner Array separately according to their own order of elements, then fold the result of each according to the outer Array's order of elements.

---

Now, you might reasonably object that since there's no type distinction between one-dimensional and multidimensional Arrays, and the former can be assumed to have a sensible fold ordering based on the Ix instance, why not just use that ordering by default? There's already a function that returns the elements of an Array in a list, after all.

As it turns out, the library itself would agree with you, because that's exactly what the Foldable instance does.

Answer 2

There is one natural way to fold lists, which is foldr. Note the types of the list constructors:

(:) :: a -> [a] -> [a]
[]  :: [a]

Replacing the occurrences of [a] with b, we get these types:

f :: a -> b -> b
z :: b

And now, of course, the type of foldr is based on this principle:

foldr :: (a -> b -> b) -> b -> [a] -> b

So given the construction/observation semantics of lists, foldr is the one that's most natural. You can read the type as "tell me what to do with a (:) and what to do with a [], and I'll get rid of a list for you."

Array doesn't have this property; you build an array from an association list (Ix i => [(i,a)]), and the type doesn't really expose any recursive structure: one array is not built from other arrays through a recursive constructor as a list or tree would be.