неизменяемых), это связано с различными нюансами размещения элементов в массивах, о которых мы пока
умолчим. Для предостваления общего интерфейса к различным массивам был определён класс:
class (HasBounds a, Monad m) => MArray a e m where
newArray
:: Ix i => (i, i) -> e -> m (a i e)
newArray_ :: Ix i => (i, i) -> m (a i e)
MArray – это сокращение от mutable (изменяемый) array. Метод newArray создёт массив типа a, который
завёрнут в тип-монаду m. Первый аргумент указывает на диапазон значений индексов массива, а вторым
аргументом передаётся элемент, который будет записан во все ячейки массива. Вторая функция записывает
в массив элемент undefined.
Посмотрим на вспомогательные классы:
class Ord a => Ix a where
range :: (a, a) -> [a]
index :: (a, a) -> a -> Int
inRange :: (a, a) -> a -> Bool
rangeSize :: (a, a) -> Int
class HasBounds a where
bounds :: Ix i => a i e -> (i, i)
Класс Ix описывает тип индекса из непрерывного диапазона значений. Наверняка по имени функции
и типу вы догадаетесь о назначении методов (можете свериться с интерпретатором на типах Int или (Int,
Int)). Класс HasBounds обозначает массивы размер, которых фиксирован. Но вернёмся к массивам. Мы можем
не только выделять память под массив, но и читать элементы и обновлять их:
readArray
:: (MArray a e m, Ix i) => a i e -> i -> m e
writeArray :: (MArray a e m, Ix i) => a i e -> i -> e -> m ()
В случае ST-ссылок у нас была функция runST. Она возвращала значение из памяти, но что будет возвра-
щать аналогичная функция для массива? Посмотрим на неё:
Монада изменяемых значений ST | 121
freeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e)
Возможно за всеми классами схожесть с функцией runST прослеживается не так чётко. Новый класс
IArray обозначает неизменяемые (immutable) массивы. Функцией freeze мы превращаем изменяемый мас-
сив в неизменяемый, но завёрнутый в специальный тип-монаду. В нашем случае этим типом будет ST. В
модуле Data.Array.ST определена специальная версия этой функции:
runSTArray :: Ix i => (forall s . ST s (STArray s i e)) -> Array i e
Здесь Array – это обычный неизменяемый массив. Он живёт в модуле Data.Array мы можем строить
массивы из списков значений, преобразовывать их разными способами, превращать в обратно в списки и
многое другое. Об о всём этом можно узнать из документации к модулю. Обратите на появление слова
forall и в этой функции. Оно несёт тот же смысл, что и в функции runST.
Для тренировки напишем функцию, которая меняет местами два элемента массива:
module Qsort where
import Data.STRef
import Control.Monad.ST
import Data.Array
import Data.Array.ST
import Data.Array.MArray
swapElems :: Ix i => i -> i -> STArray s i e -> ST s ()
swapElems i j arr = do
vi <- readArray arr i
vj <- readArray arr j