Главная » Haskell » Модуль MArray

0

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

import Data.Array.MArray

Типы, которые поддерживают описываемый в этом модуле интерфейс (класс), в свою очередь описаны в модулях IO (см. подраздел  8.1.4.),  ST  (см. подраздел 8.1.6.) и Storable (см. подраздел 8.1.7.).

Класс:  MArray

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

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

class Monad  m   => MArray a e m   where getBounds :: Ix i => a i e ->  m   (i,  i) newArray   :: Ix i => (i, i) ->  e  ->  m   (a  i e) newArray_ :: Ix i => (i,  i) ->  m   (a  i e)

Массив, которые может быть экземпляром этого класса, должен иметь форму (a i e), где a — конструктор массива, i — тип индексов массива (этот тип должен в обязательном порядке быть экземпляром класса Ix), e — тип элементов, хранящихся в массиве.

Класс MArray параметризуется и типом массива, и типом элементов, которые в нём хранятся (поэтому экземпляры этого класса могут определяться в том же стиле, что и для класса IArray — см. стр. 233). Кроме того, класс также параметризуется монадой m, в которой происходит работа с изменяемым массивом.

Метод getBounds возвращает пару индексов  массива — самый нижний и самый верхний. Метод newArray создаёт новый массив, в  котором  каждый элемент в заданном интервале проинициализирован  заданным значением. Метод newArray_ создаёт новый массив, в котором каждое значение не определено (рав-

но (?)).

Для  класса MArray  определено  множество экземпляров типов   IOUArray (см. стр. 235), StorableArray (см. стр. 244) и STArray (см.  стр. 242), которые охватывают все примитивные  типы элементов.

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

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

Функция: newArray

Описание:  реализация одноимённого метода  класса  MArray,   используемая по умолчанию.

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

newArray :: (MArray  a e m, Ix i) => (i, i) ->  e  -> m   (a  i e) newArray (l, u)  init = do marr  < newArray_ (l, u)

sequence_ [unsafeWrite  marr  i init |

i < [0..rangeSize (l, u)  1]]

return  marr

Функция: newArray-

Описание:  реализация одноимённого метода  класса  MArray,   используемая по умолчанию.

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

newArray_ :: (MArray  a e m, Ix i) => (i, i)  -> m   (a  i e) newArray_ (l, u)  = newArray (l,  u)  arrEleBottom

Функция: newListArray

Описание: создаёт изменяемый  массив, наполняя его значениями из заданного списка. Считается, что значения в списке идут по порядку от наименьшего к наибольшему.

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

newListArray :: (MArray  a e m, Ix i) => (i, i) ->  [e]  -> m   (a  i e) newListArray (l, u)  es

= do marr  < newArray_  (l,  u) let n  =  rangeSize  (l, u)

let fillFromList i xs  | i == n       = return ()

| otherwise =  case xs  of

[]   ->  return ()

y:ys ->  unsafeWrite  marr  i y  >> fillFromList  (i + 1)  ys

fillFromList  0  es return  marr

Функция: readArray

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

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

readArray :: (MArray  a e m, Ix i) => a i e ->  i  ->  m   e readArray marr  i = do (l, u)  < getBounds marr

unsafeRead marr  (index (l, u)  i)

Функция: writeArray

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

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

writeArray :: (MArray  a e m, Ix i) => a i e ->  i ->  e  ->  m   () writeArray marr  i e = do (l, u)  < getBounds  marr

unsafeWrite marr  (index (l,  u)  i) e

Функция: mapArray

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

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

mapArray :: (MArray  a e’ m, MArray a e m, Ix i) => (e’ ->  e)  ->  a i e’ ->  m  (a  i e) mapArray f marr  = do (l, u)  < getBounds marr

marr’ < newArray_ (l, u)

sequence_ [do  e < unsafeRead  marr  i unsafeWrite  marr’  i (f e)

| i < [0..rangeSize (l,  u) 1]] return marr’

Функция: mapIndices

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

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

mapIndices  :: (MArray  a e m, Ix i, Ix j) => (i,i) ->  (i ->  j) ->  a j e ->  m  (a  i e) mapIndices  (l, u)  f marr  = do marr’ < newArray_ (l, u)

sequence_ [do  e < readArray marr  (f i)

unsafeWrite marr’  (unsafeIndex (l,  u)  i) e

| i < range  (l, u)] return marr’

Функция: getBounds

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

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

getBounds :: (MArray  a e m, Ix i) => a i e ->  m   (i, i)

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

Функция: getElems

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

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

getElems  :: (MArray  a e m, Ix i) => a  i  e ->  m   [e] getElems  marr  = do (l, u)  < getBounds marr

sequence [unsafeRead  marr  i | i < [0..rangeSize (l, u)   1]]

Функция:  getAssocs

Описание: возвращает список соответствий вида (индекс, значение).

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

getAssocs  :: (MArray  a e m, Ix i) => a i e  ->  m   [(i, e)] getAssocs  marr  = do (l, u)  < getBounds marr

sequence [do  e < unsafeRead marr  (index (l, u)  i) return  (i, e)

| i < range  (l,  u)]

Функция: freeze

Описание: конвертирует  изменяемый массив (произвольный  экземпляр класса MArray) в неизменяемый массив (соответствующий экземпляр класса IArray — см. стр. 233.

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

freeze :: (Ix i, MArray a e m, IArray b e)  => a i e ->  m   (b  i e)

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

Функция: unsafeFreeze

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

unsafeFreeze  :: (Ix i, MArray a e m, IArray b e)  => a i e ->  m   (b  i e)

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

Функция: thaw

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

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

thaw :: (Ix i, IArray a e, MArray b e m) => a i e ->  m  (b  i e)

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

Функция: unsafeThaw

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

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

unsafeThaw :: (Ix i, IArray a e, MArray b e m) => a i e ->  m  (b  i e)

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

Небезопасные деструктивные функции unsafeFreeze и unsafeThaw должны использоваться с осторожностью. После их применения старые ссылки на заменённые массивы использоваться не должны. Эти  функции полезны при работе с массивами типов IOArray  (см. стр.  234), IOUArray (см. стр. 235), STArray (см. стр. 242) и STUArray (см. стр. 242), для которых эти функции выполняются за время O(1).

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

По теме:

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