Geum.ru

Душкин Роман Викторович darkus@yandex ru Москва, 2001 лекция

Вид материалаЛекция

Содержание


Встроенные монады
Подобный материал:
1   ...   11   12   13   14   15   16   17   18   19

Монады


Многие новички в функциональном програмировании бывают часто озадачены по­ня­ти­ем монады в Haskell’е. Но монады очень часто встречаются в языке, так, например, сис­те­ма ввода/вывода основана именно на понятии монады, а стандартные библиотеки со­дер­жат целые модули посвященные монадам. Необходимо отметить, что понятие монады в Has­kell’е основано на теории категорий, однако для того, чтобы не вдаваться в аб­с­т­рак­т­ную математику, далее будет представлено интуитивное понимание монад.

Монады являются типами, которые представляют собой экземпляры одного из сле­ду­ю­щих монадических классов: Functor, Monad и MonadPlus. Ни один из этих классов не мо­жет являться предком для другого класса, т.е. монадические классы ненаследуемы. В мо­ду­ле Prelude определены три монады: IO, [] и Maybe, т.е. список также является монадой.

Математически монада определяется через набор правил, которые связывают операции, про­изводимые над монадой. Эти правила дают интуитивное понимание того, как должна ис­пользоваться монада и какова ее внутренняя структура. Для конкретизации далее рас­с­мат­ривается класс Monad, в котором определены две базовые операции и одна функция:

class Monad m where

(>>=) :: m a -> (a -> m b) -> m b

(>>) :: m a -> m b -> m b

return :: a -> m a

fail :: String -> m a


m >> k = m >>= \_ -> k

Две операции (>>=) и (>>) — это операции связывания. Они комбинируют два мо­на­ди­чес­ких значения, тогда как функция return преобразует переданное значение некоторого ти­па a в монадическое значения типа m a. Сигнатура операции (>>) помогает понять опе­ра­цию связывания: выражение (m a >>= \v  m b) комбинирует монадическое значение m a, содержащее объект типа a, с функцией, которая оперирует значением v типа a и воз­вра­щает результат типа m b. Результатом же комбинации будет монадическое значение ти­па m b. Операция (>>) используется тогда, когда функция не использует значения, по­лу­чен­ного первым монадическим операндом.

Точное значение операция связывания конечно же зависит от конкретной реализации мо­нады. Так, например, тип IO определяет операцию (>>=) как последовательное вы­пол­не­ние двух её операндов, а результат выполнения первого операнда последовательно пе­ре­дается во второй. Для двух других встроенных монадических типов (списки и Maybe) эта операция определена как передача нуля или более параметров из одного вы­чис­ли­тель­но­го процесса в следующий.

В Haskell’е определено специальное служебное слово, которое на уровне языка под­дер­жи­вает использование монад. Это слово do, понимание которого можно увидеть в сле­ду­ю­щих правилах его применения:

do e1 ; e2 = e1 >> e2

do p <- e1 ; e2 = e1 >>= \p -> e2

Первое выражение выполняется всегда (переноса значений из первого операнда во вто­рой не производится). Во втором выражении может произойти ошибка, в этом случае про­из­водится вызов функции fail, которая также определена в классе Monad. Поэтому более точ­ное определение служебного слова do для второго случая будет выглядеть так:

do p <- e1 ; e2 = e1 >>= (\v -> case v of

p -> e2

_ -> fail ”s”)

где s — это строка, которая может определять местоположение оператора do в прог­рам­ме, а может просто нести некоторую семантическую нагрузку. Например, в монаде IO дей­с­твие (‘a’  getChar) вызовет функцию fail в том случае, если считанный символ не яв­ля­ется символом ‘a’. Это действие прерывает исполнение программы, т.к. определенная в мо­наде IO функция fail в свою очередь вызывает системную функию error.

Класс MonadPlus используется для тех монад, в которых есть нулевой элемент и опе­ра­ция «+». Определение этого класса выглядит следующим образом:

class (Monad m) => MonadPlus m where

mzero :: m a

mplus :: m a -> m a -> m a

Нулевой элемент в этом классе монад подчиняется следующим правилам:

m >>= \x -> mzero = mzero

mzero >>= m = mzero

Например, для списков нулевым элементом является пустой список [], а операцией «+» — конкатенация списков. Поэтому монада списков является экземпляром класса MonadPlus. С другой стороны монада IO не имеет нулевого элемента, поэтому монада IO яв­ляется экземпляром только класса Monad.

Встроенные монады


Для конкретизации полученных сведений необходимо рассмотреть что-нибудь более при­земленное. Так как списки являются монадами и в то же время списки достаточно скру­пулезно изучены, они являются отличным материалом, на котором можно рас­с­мот­реть практическое применение механизма монад.

Для списков операция связывания обретает смысл в соединении вместе набора опе­ра­ций, производимых над каждым элементом списка. При использовании со списками сиг­на­тура операции (>>=) приобретает следующий вид:

(>>=) :: [a] -> (a -> [b]) -> [b]

Это обозначает, что дан список значений типа a и функция, которая проецирует зна­че­ние типа a на список значений типа b. Связывание применяет функцию к каждому эле­мен­ту данного списка значений типа a и возвращает полученный список значений типа b. Эта опе­рация уже известна — определители списков работают именно таким образом. Т.е. сле­дующие три выражения абсолютно одинаковы:

-- Выражение 1 ----------------------------------------------------------------------------------

[(x, y) | x <- [1, 2, 3], y <- [1, 2, 3], x /= y]


-- Выражение 2-----------------------------------------------------------------------------------

do x <- [1, 2, 3]

y <- [1, 2, 3]

True <- return (x /= y)

return (x, y)


-- Выражение 3-----------------------------------------------------------------------------------

[1, 2, 3] >>= (\x -> [1, 2, 3] >>= (\y -> return (x /= y) >>=

(\r -> case r of

True -> return (x, y)

_ -> fail ””)))

Какое выражение использовать в написании программ — выбирать программисту.