Материалы представленные на сайте исключительно с целью ознакомления пользователям Интернета и не преследуют коммерческих целей или нарушение авторских прав.
© 2018 - 2024
foreach(File rec : listFilesRec(sub))
res.add(rec);
return res;
}
А теперь перепишем эти примеры с использованием операции «;*», вызывающей следующую операцию для всех результатов предыдущей.
int sum = 0;
{
Shop s <- getShops() ;*
Department d <- getDepartments(s) ;*
Order ord <- getOrders(d) ;*
sum += ord.getCost();
}
return sum;
List<File> listFilesRec(File file)
{
List<File> res = new ArrayList<String>();
res.add(file);
{
File contents <- getContents(file) ;*
File rec <- listFilesRec(contents) ;*
res.add(rec);
}
return res;
}
Во всех трех случаях имело место переопределение стратегий связывания двух вычислений – первого и оставшегося, переопределение оператора «;». Можно сказать, что в этом и состоит суть концепции монад. Теперь, чтобы пользоваться этим как средством абстракции, понадобится формализовать эту концепцию.
4.11.4. Операции «>>=» и return
Операция «>>=» - это результат обобщения операций ;, ;?, ;*. Вернемся к вопросу, что является значением выражения a>>=b. >>= - это полиморфная операция – то есть логика ее работы никак не зависит от того, значения каких типов она связывает.
Тип операции (>>=), очевидно, зависит от типов первого и второго вычисления; он будет параметризован, как минимум, двумя типами: – a (тип результата первого вычисления), b (тип результата второго вычисления). Однако просто «значение» и «значение, вычисленное в монаде» - это совсем не одно и то же. Например, просто «значение» и «элемент списка значений». При этом способ вычисления значения должен быть известен операции >>=, но сами функции, участвующие в вычислениях знать об этом не могут и не должны. В этом и состоит назначение операции «>>=».
Итак, получается тип (>>=) :: m a -> (a -> m b) -> m b. Его можно прочитать так: (>>=) в монаде m связывает монадное вычисление параметра (m a) с монадным вычислением, зависящим от этого параметра (a -> m b), давая монадный результат (m b).
Кроме этого, в каждой монаде в той или иной форме должна существовать некоторая операция, позволяющая создать монадное вычисление «из ничего» для произвольного (немонадного) значения. Такая операция добавлена в само понятие монады и называется return. Она имеет тип a -> m a и делает из значения - то, что получилось бы, если бы это значение было вычислено в монаде.
Между двумя определенными операциями существуют определенные связи и зависимости. Например, если выполнить «монадное вычисление параметра» с помощью функции return, то будет логичным потребовать, чтобы результат был таким же, как и если бы параметр был просто передан второму вычислению, т.е.:
(return x >>= f) = f x
Это – первый из трех законов монад. Легко проверить, что для вышеприведенных примеров монад этот закон выполняется.
4.11.5. Законы монад
Согласованность return и (>>=) : (return x >>= f) = f x
Ассоциативность (>>=) : ((x >>= f) >>= g) = (x >>= (\y -> f y >>= g)) . Этот закон позволяет воспринимать последовательность a ; b ; c ; ... как монолитную и не заботиться о расстановке скобок в ней.
Правая единица: (x >>= return) = x, то есть, связывание монадного вычисления x с вычислением, зависящим от параметра и просто возвращающим этот параметр, есть тождественная функция.
Теперь можно окончательно сказать, что такое монада.
Монадой называется тройка (m, return, >>=), где:
m – тип с одним аргументом;
return :: forall a . a -> m a;
(>>=) :: forall a, b . m a -> (a -> m b) -> m b.
Эти требования формализуемы на уровне системы типов, и в Prelude определен класс:
Class Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b
Законы монад обязаны выполняться, они не могут быть проверены компилятором, но их нарушение, скорее всего, приведет к ошибкам:
(return x) >>= f = f x
(x >>= f) >>= g = x >>= (\y -> f y >>= g)
(x >>= return) = x
4.11.6. Стандартные монады
Identity (тождественная монада)
Это - простейшая монада, которой соответствует прилагательное «тождественный»: Identity String – «тождественный (обычный) String». То есть, эта монада, по сути, не меняет ни тип значений, ни стратегию связывания вычислений.
data Identity a = Identity a
return a = Identity a
(Identity a) >>= f = f a
Такая монада находит применение с монадными трансформерами, которые здесь не рассматриваются.
Maybe (монада вычислений с обработкой отсутствующих значений)
Здесь есть два класса значений – «обычные» и специальное значение «значение отсутствует»:
data Maybe a = Nothing
| Just a
Связывание «просто» параметра с параметризованным вычислением – это передача параметра вычислению, связывание отсутствующего параметра с параметризованным вычислением – отсутствующий результат.
return a = Just a
Nothing >>= f = Nothing
(Just a) >>= f = f a
Монада List (вычисления, которые могут возвращать 0 или более результатов)
В этой монаде значения представляют собой списки, которые можно интерпретировать как несколько возможных результатов одного вычисления. Если одно вычисление зависит от другого, то второе вычисление производится для каждого результата первого, и полученные результаты (второго вычисления) собираются в список.
return a = [a]
params >>= f = concat [f x | x <- params]
Типы участвующих значений:
p::[a] – это список результатов некоторого вычисления. Его можно интерпретировать как одно значение с несколькими вариантами;
f::a -> [b] – это «недетерминированная» функция, возвращающая список вариантов результата в зависимости от параметра.
Таким образом, p>>=f::[b], как и следовало ожидать – это список возможных результатов применения функции к каждому из вариантов входного аргумента.
State (монада вычислений с изменяемым состоянием)
Это монада посложнее. В ней каждое вычисление, во-первых, возвращает какое-то значение, а во-вторых, изменяет значение переменной состояния. То есть, вычисление типа «a» с состоянием типа «s» имеет тип s -> (a, s). Так и есть:
newtype State s a = State {runState :: s -> (a, s) }
Рассмотрим, например, программу, реализующую метод Монте-Карло. Для этого понадобится датчик случайных чисел, обладающий состоянием. Тогда для этой программы «a» будет соответствовать типу результата – например, числу успешных экспериментов – а «s» будет представлять внутреннее состояние датчика случайных чисел. Эта программа будет использовать функцию rand - «сгенерировать случайное число», которая будет возвращать новое случайное число и изменять состояние датчика:
Rand :: State RndGen Int
rand = get >>= \(RndGen x) ->
put (RndGen ((x*1367823 + 918237) `mod` 32768)) >>=
Return x
monteCarlo :: (Int -> Bool) -> Int -> State RndGen Int
monteCarlo experiment 0 = return 0
monteCarlo experiment n = rand >>= \r ->
If (experiment r) then
monteCarlo experiment (n-1) >>= \s ->
return (s+1)
Else
MonteCarlo experiment (n-1)
get и put - готовые функции для чтения и изменения состояния в монаде State:
Get :: State s s
get = State $ \s -> (s, s)
put :: s -> State s ()
put s' = State $ \s -> ((), s’)
get – это «вычисление с изменяемым состоянием, возвращающее само состояние», а put – это «вычисление с изменяемым состоянием, не возвращающее ничего, зато изменяющее состояние». Теперь реализация самой монады State:
Дата: 2016-10-02, просмотров: 223.