|
module Array ( module Ix, -- экспортирует весь Ix в целях удобства Array, array, listArray, (!), bounds, indices, elems, assocs, accumArray, (//), accum, ixmap ) where import Ix infixl 9 !, // data (Ix a) => Array a b = ... -- Абстрактный array :: (Ix a) => (a,a) -> [(a,b)] -> Array a b listArray :: (Ix a) => (a,a) -> [b] -> Array a b (!) :: (Ix a) => Array a b -> a -> b bounds :: (Ix a) => Array a b -> (a,a) indices :: (Ix a) => Array a b -> [a] elems :: (Ix a) => Array a b -> [b] assocs :: (Ix a) => Array a b -> [(a,b)] accumArray :: (Ix a) => (b -> c -> b) -> b -> (a,a) -> [(a,c)] -> Array a b (//) :: (Ix a) => Array a b -> [(a,b)] -> Array a b accum :: (Ix a) => (b -> c -> b) -> Array a b -> [(a,c)] -> Array a b ixmap :: (Ix a, Ix b) => (a,a) -> (a -> b) -> Array b c -> Array a c instance Functor (Array a) where ... instance (Ix a, Eq b) => Eq (Array a b) where ... instance (Ix a, Ord b) => Ord (Array a b) where ... instance (Ix a, Show a, Show b) => Show (Array a b) where ... instance (Ix a, Read a, Read b) => Read (Array a b) where ... |
Haskell обеспечивает индексируемые массивы, которые можно рассматривать как функции, чьи области определения изоморфны соприкасающимся подмножествам целых чисел. Функции, ограниченные таким образом, можно эффективно реализовать; в частности, программист может ожидать разумно быстрого доступа к компонентам. Чтобы гарантировать возможность такой реализации, массивы обрабатываются как данные, а не как обычные функции.
Так как большинство функций массива затрагивают класс Ix, этот модуль экспортируется из Array, чтобы не было необходимости модулям импортировать и Array, и Ix.
Вторым аргументом array является список ассоциаций
вида (индекс, значение). Обычно этот список
выражен в виде описания элементов. Ассоциация (i, x) определяет, что
значением массива по индексу i является x. Массив не определен (т.е. _|_), если
какой-нибудь индекс в списке находится вне границ. Если какие-нибудь две ассоциации в
списке имеют один и тот же индекс, значение по этому индексу не определено (т.е. _|_).
Так как индексы должны быть проверены на наличие этих ошибок, array
является строгим по аргументу границ и по индексам списка ассоциаций,
но не является строгим по значениям. Таким образом, возможны такие рекуррентные отношения:
a = array (1,100) ((1,1) : [(i, i * a!(i-1)) | i <- [2..100]])
Не каждый индекс в пределах границ массива обязан
появиться в списке ассоциаций, но значения, связанные с индексами,
которых нет в списке, будут не определены (т.е. _|_).
На рис. 16.1 изображены некоторые примеры, которые используют
конструктор array.
Оператор (!) обозначает доступ к элементам массива по индексу (операция индексации массива). Функция bounds, будучи примененной к массиву, возвращает его границы. Функции indices, elems и assocs, будучи примененными к массиву, возвращают соответственно списки индексов, элементов или ассоциаций в порядке возрастания их индексов. Массив можно создать из пары границ и списка значений в порядке возрастания их индексов, используя функцию listArray.
Если в каком-либо измерении нижняя граница больше чем верхняя граница, то такой массив допустим, но он пуст. Индексация пустого массива всегда приводит к ошибке выхода за границы массива, но bounds по-прежнему сообщает границы, с которыми массив был создан.
Другая функция создания массива, accumArray,
ослабляет ограничение, при котором данный индекс может появляться не более одного раза
в списке ассоциаций, используя функцию накопления, которая
объединяет значения ассоциаций с одним и тем же индексом.
Первым аргументом accumArray является функция накопления;
вторым --- начальное значение; оставшиеся два аргумента являются соответственно парой границ
и списком ассоциаций, как и для функции 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]
Если функция накопления является строгой, то accumArray
является строгой в отношении значений, также как и в отношении индексов, в
списке ассоциаций. Таким образом, в отличие от обычных массивов,
накопленные массивы не должны быть в общем случае рекурсивными.
Оператор (//) принимает в качестве аргументов массив и список пар и возвращает массив, идентичный левому аргументу, за исключением того, что он обновлен ассоциациями из правого аргумента. (Как и с функцией array, индексы в списке ассоциаций должна быть уникальны по отношению к обновляемым элементам, которые определены.) Например, если m --- матрица n на n с началом в 1, то m//[((i,i), 0) | i <- [1..n]] --- та же самая матрица, у которой диагональ заполнена нулями.
accum f принимает в качестве аргументов массив
и список ассоциаций и накапливает пары из списка в
массив с помощью функции накопления f. Таким образом, accumArray
можно определить через accum:
accumArray f z b = accum f (array b [(i, z) | i <- range b])
Функции fmap и ixmap получают новые массивы из существующих; их можно рассматривать как обеспечение композиции функций слева и справа соответственно, с отображением, которое реализует исходный массив. Функция fmap преобразовывает значения массива, в то время как ixmap позволяет выполнять преобразования на индексах массива. На рис. 16.2 изображены некоторые примеры.
Примеры производных массивов |