Unknown - haskell-notes

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

whereupdate 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> letx =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 ( Nega)

=a

negate x

= Negx

...

...

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

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

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

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

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

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)