Главная » Haskell » Модуль Array позволяющих работать со строгими массивами

0

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

import Data.Array

Необходимо отметить, что в модуле IArray (описывается ниже, см. подраздел 8.1.3.) описываются программные сущности,  которые  позволяют работать с неизменяемыми массивами (к тому же в этом модуле предоставлены  более общие интерфейсы к  массивам). Все такие программные сущности имеют те же самые наименования. Если есть необходимость работы с более общим интерфейсом, необходимо подключить модуль IArray.

Рассматриваемый модуль импортирует, использует и реимпортирует модуль Ix (см. раздел 8.18.), который описывает типы, предназначенные для индексации массивов. Если подключён модуль Array, то дополнительно подключать модуль Ix не нужно.

Язык  Haskell предоставляет  в распоряжение программиста  неизменяемые строгие и нестрогие массивы, которые  можно  рассматривать в виде функций, чьи области определения изоморфны множествам последовательно расположенных целых чисел. Ограниченные таким образом функции можно достаточно эффективно реализовать (в отличие, например, от списков произвольной длины), и программист может рассчитывать на быстрый доступ к произвольному элементу массива. Для гарантирования возможности быстрого доступа массивы реализованы в виде алгебраического типа данных, а не в виде обобщённых функций. Тип: Array

Описание: тип неизменяемого нестрогого массива.

Определение:

data  Array  i e = …

Сам тип реализован в виде примитива. Компонент i является типом индексов массива, а компонент e является типом элементов массива. Тип Array  имеет экземпляры для следующих классов: Typeable2, IArray, Foldable,  Functor, FunctorM, Traversable, Data, Eq, NFData, Ord, Read и Show.

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

Функция: array

Описание:  создаёт массив в заданном диапазоне индексов с заданными значениями, соответствующими индексам.

Определение:

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

Функция определена в виде примитива.

Первый аргумент функции определяет пару индексов — наименьший и наибольший. Все остальные индексы расположены между ними  (поэтому на тип индексов накладывается ограничение в наличии экземпляра класса Ix). Второй аргумент этой функции является списком пар вида (индекс, элемент). Обычно этот список строится при помощи генератора.

Значение массива не определено (?), если индекс выходит за заданные границы. Кроме того, стандартом языка Haskell определяется, что если во входном

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

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

Функция: listArray

Описание: создаёт массив из пары индексов (нижний и верхний) и из списка, в котором значения полагаются идущими по порядку от нижнего индекса к верхнему. Определение:

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

Функция определена в виде примитива.

Функция: accumArray

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

Определение:

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

Функция определена в виде примитива.

Первым аргументом является аккумулирующая функция, вторым — началь ное значение для накопления результата. Остальные  аргументы такие же, как и у функции array  (см. стр. 227).

Например, для заданного списка соответствий значений некоторым индексам следующая функция строит гистограмму:

hist :: (Ix a, Num  b)  => (a, a)  ->  [a] ->  Array  a b

hist bnds is = accumArray (+) 0 bnds [(i, 1)  | i < is, inRange bnds i]

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

Функция: (!)

Описание: возвращает значение массива для заданного индекса.

Определение:

(!) :: Ix i => Array  i e ->  i ->  e

Функция определена в виде примитива.

Функция: bounds

Описание: возвращает пару, состоящую из нижней и верхней границ заданного массива.

Определение:

bounds :: Ix i => Array  i e ->  (i, i)

Функция определена в виде примитива.

Функция: indices

Описание: возвращает список индексов заданного массива.

Определение:

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

Функция определена в виде примитива.

Функция: elems

Описание: возвращает список элементов заданного массива.

Определение:

elems :: Ix i => Array  i e ->  [e]

Функция определена в виде примитива.

Функция: assocs

Описание: возвращает список соответствий (пар вида (индекс, значение)) для заданного массива, причём список отсортирован в соответствии с увеличением индексов исходного массива.

Определение:

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

Функция определена в виде примитива.

Функция: (//)

Описание: создаёт такой же  массив, как и первый аргумент, за  исключением того, что элементы из списка соответствий (второй аргумент) заменяют элементы старого массива.

Определение:

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

Функция определена в виде примитива.

Повторяющиеся индексы в списке соответствий обрабатываются также, как и для функции array  (см. стр. 227). Стандарт языка говорит, что значения мас-

сива на таких индексах не определено (?), но компилятор GHC, тем не менее,

возвращает значение, которое стояло последним в списке соответствий для данного индекса.

Функция: accum

Описание: получает на вход аккумулирующую функцию, массив и список соответствий, а возвращает массив, в котором значения переработаны аккумулирующей функцией.

Определение:

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

Функция определена в виде примитива.

Функция: ixmap

Описание: позволяет производить изменения в индексации массивов. создаёт массив, в котором индексы элементов заменены в соответствии с заданной функцией, а элементы такие же, как и в исходном массиве.

Определение:

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

Функция определена в виде примитива.

Подобная трансформация массива может быть проделана при помощи метода

fmap (см. стр. 211) из экземпляра класса Functor  для типа Array.

Источник: Душкин Р. В., Справочник по языку Haskell. М.: ДМК Пресс, 2008. 544 с., ил.

По теме:

  • Комментарии