Haskell中的稀疏数组？

Question

有没有标准或“最常见”的方法在Haskell中表示多维稀疏数组（不会牺牲太多性能）？例如，在C++中的map< int，map< int，MyClass>>之类的东西。我已经搜索过谷歌，只找到一些老的学术论文和其他人也在寻找这个问题的答案。谢谢！

- Jay

Answer 1

Data.Map (Int,Int) MyClass 是一个很好的建议；首先尝试使用它。

如果你在使用上遇到空间问题，可以尝试使用 IntMap (IntMap MyClass)。其中的IntMap（在模块 Data.IntMap 中）是以Int作为键的Map，由于是专门针对Int类型进行优化，因此比通用的maps更高效。这可能会或可能不会有显著的差异。

还有一个可扩展的、自适应的持久化容器类型项目，可能对你有用。这些容器（包括maps）使用的空间显著少于普通maps，但它们稍微复杂一些（虽然仍然相对容易使用）。

- Martijn

---

谢谢！这对我来说非常有用（我正在处理一些大型但稀疏数组上的数值算法）。 - Jay

Answer 2

那么一个 Data.Map (Int,Int) MyClass 怎么样？

- newacct

Answer 3

有一个叫做HsJudy的工具，似乎非常适合稀疏键集。

这是一个Judy绑定的工具（一种实现快速稀疏动态数组的C库），它提供了尽可能符合现有Haskell库接口的API，例如Data.Map和Data.Array.MArray。这个Judy库的绑定包括其四种类型：从单词到位（Judy1），从单词到值（JudyL），从字符串到值（JudyHS）以及从字节数组到值（JudyHS）。

但在遇到可扩展性或可用性问题之前，我可能会使用Data.Map.Map (Int, Int) MyClass。

- ephemient

---

非常感谢你和另一个建议使用Data.Map的人。我猜我可能会遇到可扩展性问题，但我还是会尝试的 :-) - Jay

Answer 4

我找不到免费的资源，但是有以下两个：

函数式语言中的稀疏矩阵表示

以及这个：

函数式语言中用于解决线性系统的稀疏矩阵表示研究

- Robert Harvey

Answer 5

我找到了一个简短的代码片段，展示了Haskell中的压缩行存储和相关的矩阵-向量乘法：

我找到了这个简短的代码片段，展示了Haskell中的压缩行存储和相关的矩阵-向量乘法：

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

- JKnight