Учебник по Haskell

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

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

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

происходит:

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

qsort xs = elems $ runSTArray $ do

arr <- newListArray (left, right) xs

qsortST left right arr

return arr

where left

= 0

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

right = length xs - 1

qsortST :: Ord a => Int -> Int -> STArray s Int a -> ST s ()

qsortST left right arr = do

when (left <= right) $ do

swapArray left (div (left + right) 2) arr

vLeft <- readArray arr left

(last, _) <- forLoop (left + 1) (<= right) succ

(update vLeft) (return (left, arr))

swapArray left last arr

qsortST left (last - 1) arr

qsortST (last + 1) right arr

where update vLeft i st = do

(last, arr) <- st

vi <- readArray arr i

if (vi < vLeft)

then do

swapArray (succ last) i arr

return (succ last, arr)

else do

return (last, arr)

Это далеко не самый быстрый вариант быстрой сортировки, но самый простой. Мы просто учимся обра-

щаться с изменяемыми массивами. Протестируем:

*Qsort> qsort ”abracadabra”

”aaaaabbcdrr”

*Qsort> let x = 1000000

*Qsort> last $ qsort [x, pred x .. 0]

-- двадцать лет спустя

1000000

7.6 Краткое содержание

Мы посмотрели на примерах как применяются типы State, Reader и Writer. Также мы познакомились

с монадой изменяемых значений ST. Она позволяет писать в имеративном стиле на Haskell. Мы узнали два

новых элемента пострения типов:

• Типы-обёртки, которые определяются через ключевое слово newtype.

• Записи, они являются произведением типов с именованными полями.

Также мы узнали несколько полезных типов:

• Map – хранение значений по ключу (из модуля Data.Map).

• Tree – деревья (из модуля Data.Tree).

• Array – массивы (из модуля Data.Array).

• Типы для накопления результата (из модуля Data.Monoid).

Отметим, что экземпляр класса Monad определён и для функций. Мы можем записать функцию двух ар-

гументов (a -> b -> c) как (a -> (-> ) b c). Тогда тип (-> ) b будет типом с одним параметром, как раз

то, что нужно для класса Monad. По смыслу экземпляр класса Monad для функций совпадает с экземпляром

типа Reader. Первый аргумент стрелочного типа b играет роль окружения.

7.7 Упражнения

• Напишите с помощью типа Random функцию игры в кости, два игрока бросают по очереди кости (два

кубика с шестью гранями, грани пронумерованы от 1 до 6). Они бросают кубики 10 раз выигрывает тот,

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

игры: суммарные баллы игроков.

Краткое содержание | 123

• Напишите с помощью типа Random функцию, которая будет создавать случайные деревья заданной

глубины. Значение в узле является случайным числом от 0 до 100, также число дочерних деревьев в

каждом узле случайно, оно изменяется от 0 до 10.

• Опишите в виде конечного автомата поведение амёбы. Амёба может двигаться на плоскости по четырём

направлениям. Если она чувствует свет в определённой стороне, то она ползёт туда. Если по-близости

нет света, она ползает в произвольном направлении. Амёба улавливает интенсивность света, если по

всем четырём сторонам интенсивность одинаковая, она стоит на месте и греется.

• Казалось бы, зачем нам сохранять вычисления в выражениях, почему бы нам просто не вычислить их

сразу? Если у нас есть описание выражения мы можем применить различные техники оптимизации, ко-

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

на аргумент, мы можем выразить это так:

instance Num Exp where

negate (Neg a)

= a

negate x

= Neg x

...

...

Так мы сократили вычисления на две операции. Возможны и более сложные техники оптимизации.

Мы можем учесть ноль и единицу при сложении и умножении или дистрибутивность сложения отно-

сительно умножения.

В этом упражнении вам предлагается провести подобную оптимизацию для логических значений. У

нас есть абстрактное синтаксическое дерево:

data Log

= True

| False

| Not Log

| Or

Log Log

| And Log Log

Напишите функцию, которая оптимизирует выражение Log. Эта функция приводит Log к конъюнктив-

ной нормальной форме (КНФ). Дерево в КНФ обладает такими свойствами: все узлы с Or находятся

ближе к корню чем узлы с And и все узлы с And находятся ближе к корню чем узлы с Not. В КНФ выра-

жения имеют вид:

(True ‘And‘ Not False ‘And‘ True) ‘Or‘ True ‘Or‘ (True ‘And‘ False)

(True ‘And‘ True ‘And‘ False) ‘Or‘ True

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

операции And, затем только Not.

КНФ замечательна тем, что её вычисление может пройти досрочно. КНФ можно представить так:

data Or’