Главная » Haskell » Модуль Base для определения программных сущностей в модулях IArray

0

Модуль   Base  содержит   описания  примитивов,  которые   используются для определения программных сущностей в модулях IArray (см. подраздел 8.1.3.) и MArray (см. подраздел 8.1.5.). Этот модуль входит в стандартную поставку, однако он не должен напрямую использоваться при разработке программного обеспечения.  Вместо  него необходимо подключать либо модуль IArray, либо модуль MArray.

8.1.1.       Модуль Diff

Модуль Diff позволяет создавать функциональные  массивы с константным временам обновления элементов (функция (//) — см. стр. 369). Данный модуль необходимо подключать следующим образом:

import Data.Array.Diff

Дифференциальные  массивы имеют неизменяемый  интерфейс,  однако используют примитивные функции для ускорения доступа к своим элементам. Если к такому массиву применяется функция (//), то в нём происходит физическая замена элементов в старой памяти (деструктивное присваивание). Старый массив просто заменяет свои внутренние поля, без изменения внешнего поведения.

Такая технология позволяет производить выборку элементов массива (функция (!) — см. стр. 325) за время O(1), а замену элементов массива за время O(n), где n — количество изменяемых элементов.

Однако дифференциальные массивы позволяют получать доступ и к старым элементам, которые были заменены в процессе работы. Это значит, что все эти элементы сохраняются, однако доступ к ним постепенно  становится  всё медленнее и медленнее (по мере замены новыми значениями).

Тип: IOToDiffArray

Описание: главный алгебраический тип данных для описания дифференциальных массивов.

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

data  IOToDiffArray a i e = …

Тип определён в виде примитива.

Произвольное значение типа MArray (см. подраздел 8.1.5.) может быть преобразовано к дифференциальному массиву. Этот алгебраический тип данных имеет около двадцати различных экземпляров класса IArray для многих примитивных типов данных (в том числе и для типов, представляющих значения из внешних языков программирования).

Для облегчения работы с дифференциальными массивами определено два дополнительных синонима. Первый является типом для полностью полиморфных ленивых ограниченных дифференциальных массивов:

type  DiffArray = IOToDiffArray  IOArray

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

type  DiffUArray = IOToDiffArray  IOUArray

В рассматриваемый модуль импортируется модуль IArray для предоставления общих интерфейсов к массивам.

Также в этом модуле описывается три примитивных функции, которые, однако, могут понадобиться при определении дополнительных экземпляров класса IArray для типа IOToDiffArray при использовании произвольных типов элементов. К этим функциям относятся следующие:

Функция: newDiffArray

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

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

newDiffArray :: (MArray  a e IO,  Ix i) => (i,  i)  -> [(Int,  e)]  ->

IO (IOToDiffArray a i e)

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

Функция: readDiffArray

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

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

readDiffArray :: (MArray  a e IO,  Ix i) => IOToDiffArray a i e ->  Int ->  IO e

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

Функция: replaceDiffArray

Описание: заменяет значения в дифференциальном  массиве в соответствии с заданным списком соответствий.

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

replaceDiffArray :: (MArray  a e IO,  Ix i) => IOToDiffArray  a  i e -> [(Int,  e)] ->

IO (IOToDiffArray a i e)

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

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

По теме:

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