Data.Array.IArray

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

Классы массивов

class IArray a e where Source

Класс неизменяемых типов массивов.

Тип массива имеет вид (a i e), где a — это конструктор типа массива (kind * -> * -> *), i — это тип индекса (элемент класса Ix), и e — это тип элемента. Класс IArray параметризован как по a, так и по e, так что можно определять экземпляры, специализированные для определенных типов элементов.

module Data.Ix

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

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

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

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

array Source

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

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

Ассоциация имеет вид пары (i,x), которая определяет значение массива с индексом i равным x. Массив не определен, если какой-либо индекс в списке выходит за границы. Если какие-либо две ассоциации в списке имеют одинаковый индекс, значение по этому индексу зависит от реализации. (В GHC используется последнее указанное значение для этого индекса. Другие реализации также будут делать это для распакованных массивов, но Haskell 98 требует, чтобы для Array значение по таким индексам было bottom.)

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

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

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

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

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

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

accumArray Source

Создаёт неизменяемый массив из списка ассоциаций. В отличие от array, в списке ассоциаций допускается многократное указание одного и того же индекса; для объединения значений элементов с одинаковым индексом используется функция накопления.

Например, задан список значений некоторого типа индексов; 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]

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

(!) :: (IArray a e, Ix i) => a i e -> i -> e Source

Возвращает элемент неизменяемого массива по указанному индексу.

indices :: (IArray a e, Ix i) => a i e -> [i] Source

Возвращает список всех допустимых индексов в массиве.

elems :: (IArray a e, Ix i) => a i e -> [e] Source

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

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

Возвращает содержимое массива в виде списка ассоциаций.

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

(//) :: (IArray a e, Ix i) => a i e -> [(i, e)] -> a i e Source

Принимает массив и список пар и возвращает массив, идентичный левому аргументу, за исключением того, что он был обновлён ассоциациями правого аргумента. Например, если m — матрица 1-го начала, n×n, то m//[((i,i), 0) | i <- [1..n]] — та же матрица, за исключением того, что диагональ обнулена.

Как и в случае с функцией array, если любые две ассоциации в списке имеют одинаковый индекс, значение в этом индексе зависит от реализации. (В GHC используется последнее указанное значение для этого индекса. Другие реализации также делают это для массивов без упаковки, но Haskell 98 требует, чтобы для Array значение в таких индексах было неопределённым.)

Для большинства типов массивов эта операция имеет сложность O(n), где n — размер массива. Однако пакет diffarray предоставляет тип массива, для которого эта операция имеет сложность, линейную относительно числа обновлений.

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

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

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

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

amap :: (IArray a e', IArray a e, Ix i) => (e' -> e) -> a i e' -> a i e Source

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

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

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