Unknown - haskell-notes

MArray– это сокращение от mutable (изменяемый) array. Метод newArray создёт массив типа a, который

завёрнут в тип-монаду m. Первый аргумент указывает на диапазон значений индексов массива, а вторым

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

в массив элемент undefined.

Посмотрим на вспомогательные классы:

class Orda => Ixa where

range ::(a, a) ->[a]

index ::(a, a) ->a -> Int

inRange ::(a, a) ->a -> Bool

rangeSize ::(a, a) -> Int

class HasBoundsa where

bounds :: Ixi =>a i e ->(i, i)

Класс Ixописывает тип индекса из непрерывного диапазона значений. Наверняка по имени функции

и типу вы догадаетесь о назначении методов (можете свериться с интерпретатором на типах Intили ( Int,

Int)). Класс HasBoundsобозначает массивы размер, которых фиксирован. Но вернёмся к массивам. Мы можем

не только выделять память под массив, но и читать элементы и обновлять их:

readArray

::( MArraya e m, Ixi) =>a i e ->i ->m e

writeArray ::( MArraya e m, Ixi) =>a i e ->i ->e ->m ()

В случае ST-ссылок у нас была функция runST. Она возвращала значение из памяти, но что будет возвра-

щать аналогичная функция для массива? Посмотрим на неё:

Монада изменяемых значений ST | 121

freeze ::( Ixi, MArraya e m, IArrayb e) =>a i e ->m (b i e)

Возможно за всеми классами схожесть с функцией runST прослеживается не так чётко. Новый класс

IArrayобозначает неизменяемые (immutable) массивы. Функцией freeze мы превращаем изменяемый мас-

сив в неизменяемый, но завёрнутый в специальный тип-монаду. В нашем случае этим типом будет ST. В

модуле Data.Array.STопределена специальная версия этой функции:

runSTArray :: Ixi =>(forall s . STs ( STArrays i e)) -> Arrayi 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 :: Ixi =>i ->i -> STArrays i e -> STs ()

swapElems i j arr = do

vi <-readArray arr i

vj <-readArray arr j

writeArray arr i vj

writeArray arr j vi

Протестируем на небольшом массиве:

test :: Int -> Int ->[a] ->[a]

test i j xs =elems $runSTArray $ do

arr <-newListArray (0, length xs -1) xs

swapElems i j arr

return arr

Тир функции test ничем не выдаёт её содержание. Вроде функция как функция:

test :: Int -> Int ->[a] ->[a]

Посмотрим на то, как она работает:

*Qsort>test 0 3 [0,1,2,3,4]

[3,1,2,0,4]

*Qsort>test 0 4 [0,1,2,3,4]

[4,1,2,3,0]

Теперь перейдём к сортировке. Суть метода в том, что мы выбираем один элемент массива, называемый

осью (pivot) и переставляем остальные элементы массива так, чтобы все элементы меньше осевого были сле-

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

тех, что находятся слева и справа от осевого элемента и так пока все элементы не отсортируются. В алго-

ритме очень хитрая процедура перестановки элементов, наша задача переставить элементы в массиве, то

есть не пользуясь никакими дополнительными структурами данных. Я не буду говорить как это делается,

просто выпишу код, а вы можете почитать об этом где-нибудь, в любом случае из кода будет понятно как это

происходит:

qsort :: Orda =>[a] ->[a]

qsort xs =elems $runSTArray $ do

arr <-newListArray (left, right) xs

qsortST left right arr

return arr

whereleft

=0

122 | Глава 7: Функторы и монады: примеры

right =length xs -1

qsortST :: Orda => Int -> Int -> STArrays Inta -> STs ()

qsortST left right arr = do