Читаем Учебник по Haskell полностью

Result s;

while (pred(s))

update(s);

return s;

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

до тех пор пока предикат не станет ложным.

whileLoop :: (s -> Bool) -> (s -> s) -> s -> s

whileLoop pred update s0 = runST $ do

ref <- newSTRef s0

iter ref

readSTRef ref

where iter ref = do

s <- readSTRef ref

when (pred s) $ do

writeSTRef ref $ update s

iter ref

Посчитаем сумму чисел через while-цикл:

*Loop> whileLoop ((> 0) . fst) (\(n, s) -> (pred n, n + s)) (10, 0)

(0,55)

Первый элемент пары играет роль счётчика, а во втором мы накапливаем результат.

Быстрая сортировка

Реализуем императивный алгоритм быстрой сортировки. Алгоритм быстрой сортировки хорош не только

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

массиве, с помощью обмена элементов местами. Но для этого нам понадобятся изменяемые массивы. Этот

тип определён в модуле Data.Array.ST. В Haskell есть несколько типов изменяемых массивов (как впрочем и

неизменяемых), это связано с различными нюансами размещения элементов в массивах, о которых мы пока

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

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

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) и переставляем остальные элементы массива так, чтобы все элементы меньше осевого были сле-

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

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