Data.Array

Авторские права	(c) Университет Глазго 2001
Лицензия	BSD-стиля (см. файл libraries/base/LICENSE)
Поддержка	libraries@haskell.org
Стабильность	предварительная
Переносимость	переносимый
Безопасный Haskell	Надежный
Язык	Haskell2010

Неизменяемые ленивые массивы

Haskell предоставляет индексируемые массивы, которые можно рассматривать как функции, области которых изоморфны непрерывным подмножествам целых чисел. Функции, ограниченные таким образом, могут быть реализованы эффективно; в частности, программист может разумно ожидать быстрого доступа к компонентам. Для обеспечения возможности такой реализации массивы рассматриваются как данные, а не как общие функции.

Поскольку большинство функций массивов включают класс Ix, этот модуль экспортируется из Data.Array, чтобы модули не должны были импортировать как Data.Array, так и Data.Ix.

module Data.Ix

data Array i e Источник

Тип неизменяемых ленивых (упакованных) массивов с индексами в i и элементами в e.

Создание массива

array Исходный код

Создает массив с заданными границами, содержащий значения для заданных индексов в этих пределах.

Массив неопределен (т.е. ложь), если какой-либо индекс в списке выходит за границы. Отчёт о языке Haskell 2010 дополнительно указывает, что если какие-либо две ассоциации в списке имеют одинаковый индекс, значение в этом индексе неопределено (т.е. ложь). Однако в реализации GHC значение в таком индексе — это часть последней ассоциации с этим индексом в списке.

Поскольку индексы должны проверяться на наличие этих ошибок, array строго проверяет аргумент границ и индексы списка ассоциаций, но не строго проверяет значения. Таким образом, возможны рекурсии, такие как следующие:

a = array (1,100) ((1,1) : [(i, i * a!(i-1)) | i <- [2..100]])

Не каждый индекс в пределах границ массива должен появляться в списке ассоциаций, но значения, связанные с индексами, которые не появляются, будут неопределенными (т. е. bottom).

Если в любом измерении нижняя граница больше верхней границы, то массив является допустимым, но пустым. Индексирование пустого массива всегда приводит к ошибке границ массива, но bounds по-прежнему возвращает границы, с которыми был создан массив.

listArray :: Ix i => (i, i) -> [e] -> Array i e Source

Создает массив из пары границ и списка значений в порядке индексов.

accumArray Source

Функция accumArray обрабатывает повторяющиеся индексы в списке ассоциаций, используя функцию накопления, которая объединяет значения ассоциаций с одинаковым индексом.

Например, задан список значений некоторого типа индексов, hist создает гистограмму числа появлений каждого индекса в заданном диапазоне:

hist :: (Ix a, Num b) => (a,a) -> [a] -> Array a b
hist bnds is = accumArray (+) 0 bnds [(i, 1) | i<-is, inRange bnds i]

accumArray строго в каждом результате применения функции накопления, хотя она ленива относительно начального значения. Таким образом, в отличие от массивов, построенных с помощью array, накопленные массивы, как правило, не должны быть рекурсивными.

Доступ к массивам

(!) :: Ix i => Array i e -> i -> e infixl 9 Source

Значение по заданному индексу в массиве.

bounds :: Array i e -> (i, i) Source

Границы, с которыми был создан массив.

indices :: Ix i => Array i e -> [i] Source

Список индексов массива в порядке возрастания.

elems :: Array i e -> [e] Source

Список элементов массива в порядке индексов.

assocs :: Ix i => Array i e -> [(i, e)] Source

Список ассоциаций массива в порядке индексов.

Инкрементные обновления массивов

(//) :: Ix i => Array i e -> [(i, e)] -> Array i e infixl 9 Source

Создает массив, идентичный первому аргументу, за исключением того, что он был обновлен ассоциациями во втором аргументе. Например, если m - это массив 1-го начала, n по n матрице, то

m//[((i,i), 0) | i <- [1..n]]

это та же матрица, за исключением того, что диагональ обнулена.

Повторяющиеся индексы в списке ассоциаций обрабатываются так же, как и в array: Haskell 2010 указывает, что полученный массив неопределен (т. е. bottom), но реализация GHC использует последнюю ассоциацию для каждого индекса.

accum :: Ix i => (e -> a -> e) -> Array i e -> [(i, a)] -> Array i e Source

accum f принимает массив и список ассоциаций и накапливает пары из списка в массив с функцией накопления f. Таким образом, accumArray можно определить с использованием accum:

accumArray f z b = accum f (array b [(i, z) | i <- range b])

accum строго относительно всех результатов применения накопления. Однако, он ленив относительно начальных значений массива.

Производные массивы

ixmap :: (Ix i, Ix j) => (i, i) -> (i -> j) -> Array j e -> Array i e Source

ixmap позволяет выполнять преобразования над индексами массива. Его можно рассматривать как обеспечение композиции функций справа с отображением, которое воплощает исходный массив.

Аналогичное преобразование значений массива можно получить с помощью fmap из Array экземпляра класса Functor.