Редкие массивы в Хаскелле?

Существует ли какой-либо стандартный или "самый обычный" способ представления многомерных разреженных массивов в Haskell (не жертвуя слишком высокой производительностью)?

Что-то вроде map < int, map < int, MyClass → в С++, например. Я googled и нашел только некоторые старые научные статьи и другие люди, просящие это тоже.

Спасибо!

Ответ 1

Data.Map (Int,Int) MyClass - отличное предложение; попробуйте это сначала.

Если вы столкнетесь с проблемами пространства с этим, попробуйте IntMap (IntMap MyClass). IntMap (в модуле Data.IntMap) являются Map с Int в качестве ключей; будучи специализированными, они более эффективны, чем общие карты. Это может или не может иметь существенного отличия.

Существует также проект Масштабируемый, адаптивный постоянный тип контейнеров, который может вам пригодиться. Эти контейнеры (включая карты) используют значительно меньше места, чем обычные карты, но они немного сложнее (хотя они все еще достаточно легки в использовании).

Ответ 2

Как насчет Data.Map (Int,Int) MyClass?

Ответ 3

Здесь HsJudy, который, кажется, хорошо адаптирован для разреженных наборов ключей.

Связывание Judy (библиотека C, которая реализует быстрые разреженные динамические массивы) для Haskell, представляющего API, максимально совместимые с существующими интерфейсами библиотеки Haskell, такими как Data.Map и Data.Array.MArray. Эта привязка для библиотеки Judy включает в себя все четыре ее типа: отображение слов в биты (Judy1), от слов до значений (JudyL), от строк до значений (JudyHS) и от массива байтов до значений (JudyHS).

Но я бы, вероятно, пошел с Data.Map.Map (Int, Int) MyClass, пока не столкнулся с проблемами масштабируемости или удобства использования.

Ответ 4

Ничего не вижу, что бесплатно, но есть это:

Разреженные представления матриц на функциональном языке

и это:

Исследование разреженных матричных представлений для решения линейных систем на функциональном языке

Ответ 5

Я нашел этот короткий текст, который показывает сжатое хранилище строк для 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