Data.Array

Copyright	(c) The University of Glasgow 2001
License	BSD-style (see the file libraries/base/LICENSE)
Maintainer	libraries@haskell.org
Stability	provisional
Portability	portable
Safe Haskell	Trustworthy
Language	Haskell2010

Неизменяемые нестрогие массивы

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

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

module Data.Ix

data Array i e :: * -> * -> * Source

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

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

array Source

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

Массив не определен (т.е. равен bottom), если какой-либо индекс в списке выходит за границы. В отчете Haskell 2010 дополнительно указывается, что если какие-либо две ассоциации в списке имеют одинаковый индекс, значение по этому индексу не определено (т.е. равно bottom). Однако в реализации 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 :: Ix i => Array i e -> (i, i) Source

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

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

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

elems :: Ix i => 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 является матрицей с нулевым началом, 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])

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

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

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

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