Reputation: 9646

Sparse arrays in Haskell?

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!

Upvotes: 9

Answers (5)

JKnight

Reputation: 2006

I found this short gist that shows a Compressed Row Storage for Haskell and the associated Matrix-vector multiplication:

import Data.Vector.Unboxed as U

-- | A compressed row storage (CRS) sparse matrix.
data CRS a = CRS {
      crsValues :: Vector a
    , colIndices :: Vector Int
    , rowIndices :: Vector Int
    } deriving (Show)

multiplyMV :: CRS Double -> Vector Double -> Vector Double
multiplyMV CRS{..} x = generate (U.length x) outer
  where outer i = U.sum . U.map inner $ U.enumFromN start (end-start)
          where inner j = (crsValues ! j) * (x ! (colIndices ! j))
                start   = rowIndices ! i
                end     = rowIndices ! (i+1)
                (!) a b = unsafeIndex a b

Upvotes: 3

Martijn

Reputation: 6763

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).

Upvotes: 10

ephemient

Reputation: 204668

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.

Upvotes: 5