Sparse arrays in Haskell?

Question

Is there any standard or "most usual" way to represent multidimensional sparse arrays in Haskell (without sacrificing performance too much)?

Something like map< int, map< int, MyClass> > in C++, for example. I've Googled and found just some old academic papers and other people asking for this too.

Thanks!

Answer 1

Nothing I can see that's free, but there is this:

Sparse matrix representations in a functional language

and this:

A study of sparse matrix representations for solving linear systems in a functional language

Answer 2

How about a Data.Map (Int,Int) MyClass?

Answer 3

There's HsJudy, which seems to be well-tailored for sparse key sets.

Judy bindings (a C library that implements fast sparse dynamic arrays) for Haskell presenting APIs conforming as much as possible to the existent Haskell library interfaces, like Data.Map and Data.Array.MArray. This binding for the Judy library includes all its four types: mapping from words to bits (Judy1), from words to values (JudyL), from strings to values (JudyHS) and from array-of-bytes to values (JudyHS).

But I'd probably go with a Data.Map.Map (Int, Int) MyClass until running into scalability or usability issues.

Answer 4

Data.Map (Int,Int) MyClass is an excellent suggestion; try that first.

If you run into space problems with that, try IntMap (IntMap MyClass). IntMaps (in module Data.IntMap) are Maps with Ints as keys; being specialised they are more efficient than generic maps. It might or might not make a significant difference.

There is also the Scalable, adaptive persistent container types project which might be of use to you. Those containers (including maps) use significantly less space than normal maps but they are slightly more complicated (although still reasonably easy in use).