Unknown - haskell-notes

экземпляры классов Functor, Applicativeи Monad. Какое совпадение! Посмотрим на функцию purge:

runST ::(forall s . STs a) ->a

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

Императивные циклы

Реализуем for цикл из языка C:

Result s;

for (i = 0 ; i < n; i++)

update(i, s);

return s;

У нас есть стартовое значение счётчика и результата, функция обновления счётчика, предикат останова и

функция обновления результата. Мы инициализируем счётчик и затем обновляем счётчик и состояние до тех

пор пока предикат счётчика не станет ложным. Напишем чистую функцию, которая реализует этот процесс. В

этой функции мы воспользуемся специальным синтаксическим сахаром, который называется do-нотация, не

пугайтесь это всё ещё Haskell, для понимания этого примера загляните в раздел “сахар для монад” главы~17.

module Loop where

import Control.Monad

import Data.STRef

import Control.Monad.ST

forLoop ::

i ->(i -> Bool) ->(i ->i) ->(i ->s ->s) ->s ->s

forLoop i0 pred next update s0 =runST $ do

refI <-newSTRef i0

refS <-newSTRef s0

iter refI refS

readSTRef refS

whereiter refI refS = do

i <-readSTRef refI

s <-readSTRef refS

when (pred i) $ do

writeSTRef refI $next i

writeSTRef refS $update i s

iter refI refS

Впрочем код выше можно понять если читать его как обычный императивный код. Выражения do-блока

выполняются последовательно, одно за другим. Сначала мы инициализируем два изменяемых значения, для

счётчика цикла и для состояния. Затем в функции iter мы читаем значения и выполняем проверку предиката

pred. Функция when – это стандартная функция из модуля Control.Monad. Она проверяет предикат, и если

он возвращает Trueвыполняет серию действий, в которых мы записываем обновлённые значения. Обратите

внимание на то, что связка when -doэто не специальная конструкция языка. Как было сказано when – это

просто функция, но она ожидает одно действие, а мы хотим выполнить сразу несколько. Следующее за ней

doначинает блок действий (границы блока определяются по отступам), который будет интерпретироваться

как одно действие. В настоящем императивном цикле в обновлении и предикате счётчика может участвовать

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

типе счётчика. Решим типичную задачу, посчитаем числа от одного до десяти:

*Loop>forLoop 1 ( <=10) succ ( +) 0

55

Посчитаем факториал:

*Loop>forLoop 1 ( <=10) succ ( *) 1

3628800

*Loop>forLoop 1 ( <=100) succ ( *) 1

9332621544394415268169923885626670049071596826

4381621468592963895217599993229915608941463976

1565182862536979208272237582511852109168640000

00000000000000000000

Теперь напишем while-цикл:

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

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

whereiter 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( HasBoundsa, Monadm) => MArraya e m where

newArray

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

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