Array sparsi in Haskell?

Question

Esiste un modo standard o "il solito" per rappresentare array sparsi multidimensionali in Haskell (senza sacrificare troppo le prestazioni)?

Qualcosa come la mappa < int, mappa < int, MyClass>> in C++, ad esempio. Ho cercato su Google e ho trovato solo alcuni vecchi documenti accademici e altre persone che chiedono questo.

Grazie!

Answer 1

Data.Map (Int,Int) MyClass è un eccellente suggerimento; provalo prima

Se si riscontrano problemi di spazio, provare . IntMap s (nel modulo Data.IntMap) sono Map s con Int s come chiavi; essendo specializzati sono più efficienti delle mappe generiche. Potrebbe o potrebbe non fare una differenza significativa.

C'è anche il progetto Scalable, adaptive persistent container types che potrebbe essere utile. Questi contenitori (incluse le mappe) usano molto meno spazio rispetto alle mappe normali, ma sono leggermente più complicati (anche se ancora ragionevolmente facili da usare).

Answer 2

Nulla posso vedere che è gratuito, ma c'è questo:

Sparse matrix representations in a functional language

e questo:

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

Answer 3

Come su un Data.Map (Int,Int) MyClass?

Answer 4

C'è HsJudy, che sembra essere ben adattato per set di chiavi sparse.

attacchi Judy (una libreria C che implementa veloci matrici dinamiche sparse) per Haskell presentano API conformi il più possibile alle esistenti interfacce libreria Haskell, come Data.Map e Data.Array.MArray. Questo binding per la libreria Judy include tutti i suoi quattro tipi: mapping da parole a bit (Judy1), da parole a valori (JudyL), da stringhe a valori (JudyHS) e da array-of-byte a valori (JudyHS).

Ma probabilmente andrei con un Data.Map.Map (Int, Int) MyClass fino a quando si esegue in scalabilità o problemi di usabilità.

Answer 5

ho trovato this short gist che mostra una riga di archiviazione compressa per Haskell e l'associato moltiplicazione matrice-vettore:

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