Функциональное программирование. Основы (Файлы для подготовки к экзамену), страница 8

Сама функция thenMB не зависит от того, какиеименно вычисления она комбинирует, лишь бы они удовлетворяли еесигнатуре. Ее можно использовать не только для нашего примера, но идля любых других аналогичных задач. Она определяет некоторое правило комбинирования вычислений в цепочку, заключающееся в том, чтоесли одно из вычислений не выполнилось, не выполняется и вся цепочка.Усовершенствуем наш пример. Мы перечисляли случаи, в которыхфункция getPhoneByName может не найти телефон. Однако в любомслучае она вернет значение Nothing.

В реальности нас может интересовать, почему именно она не нашла телефон. Пусть функции getPhone,getAddress и getPhoneByName возвращают значение типа Value,который определим следующим образом:data Value a = Value a | Error String42Значение типа Value a представляет собой либо значение типа a, обернутое в конструктор Value, либо строковое сообщение об ошибке, содержащееся в конструкторе Error. Функцию getAddress определимтогда так:getAddress :: AddressDB -> String -> Value StringgetAddress [] _ = Error "no address"getAddress ((name,address):rest) n | n == name = Value address| otherwise = getAddress rest nВ случае ошибки getAddress вернет значение Error "no address".Аналогично можно определить и функцию getPhone, которая в случаеошибки вернет значение Error "no phone".

Тогда функцию getPhoneByNameможно определить следующим образом:getPhoneByName :: AddressDB -> PhoneDB ->getPhoneByName a p n = case (getAddress aError s -> ErrorValue address ->String -> Value Integern) ofscase (getPhone p address) oError s -> Error sValue phone -> Value phonЗдесь мы видим аналогичную проблему, что и с предыдущим определением.

Для ее решения воспользуемся тем же примем: определимвспомогательную функцию:thenV :: Value a -> (a -> Value b) -> Value bthenV mV f = case mV ofError s -> Error sValue v -> f vС использованием этой функции можно упростить наше определение:getPhoneByName a p n = getAddress a n‘thenV‘ \address ->getPhone p address ‘thenV‘ \phone ->Value phoneНельзя не отметить некоторое сходство в функциях thenMB и thenV,а также в определениях функции getPhoneByName. Забегая вперед,скажем, что тип Value также представляет собой пример монады.Наконец, сделаем другое обобщение нашей исходной задачи. До сихпор мы предполагали, что записи в наших базах данных уникальны,т. е.

каждому человеку соответствует только один адрес, а каждомуадресу только один телефон. Предположим теперь, что это не так, т.43е. одному человеку может соответствовать несколько адресов, а одномуадресу — несколько телефонов. Тогда функции getPhone, getAddressи getPhoneByName должны возвращать списки, и их сигнатуры можнозаписать следующим образом:getAddress:: AddressDB -> String -> [String]getPhone:: PhoneDB -> String -> [Integer]getPhoneByName :: AddressDB -> PhoneDB -> String -> [Integer]Предположим, что у нас уже определены функции getPhone и getAddress.В случае неудачи они возвращают пустые списки, в случае успешногопоиска — списки, состоящие из произвольного количества элементов.Как, используя эти функции, определить функцию getPhoneByName?Для каждого адреса, возвращенного функцией getAddress, она должна вызвать функцию getPhone; результаты всех вызовов этой функциинеобходимо объединить в один список.

Определение, учитывающее этиособенности:getPhoneByName a p n =case (getAddress a n) of[] -> [](address:rest) -> getPhone p addresses ++ getPhones p restwhere getPhones _ [] = []getPhones p (x:xs) = getPhone p x ++ getPhones p xsЗдесь также можно определить вспомогательную функцию:thenL :: [a] -> (a -> [b])thenL mL f = case mL of[] -> [](x:xs) -> fwhere getRestgetRest-> [b]x ++ getRest xs f[] _ = [](x:xs) f = f x ++ getRest xs fС использованием комбинатора определение примет вид:getPhoneByName a p n = getAddress a n‘thenL‘ \address ->getPhone p address ‘thenL‘ \phone ->[phone]Можно догадаться, что список также является монадой.Итак, что же такое монада? Монада — это некоторый тип данных,подразумевающий определенную стратегию комбинирования вычислений44значения этого типа.

Так, монада Maybe подразумевает такое комбинирование вычислений, что «не сработавшее» вычисление заставляет «несрабатывать» и всю цепочку вычислений. Монада Value подразумеваетпри этом, что цепочка вычислений должна вернуть сообщение об ошибке от «не сработавшего» вычисления. Монада «список» отображает концепцию вычислений, которые могут вернуть неоднозначный результат, ицепочка вычислений должна учитывать все возможные результаты.С другой стороны, монаду можно рассматривать как контейнерныйтип, т. е. как тип, значения которого содержат в себе некоторое количество элементов другого типа. Особенно ярко это проявляется на примересписков, однако нетрудно заметить, что типы Maybe и Value также являются контейнерными и могут содержать ноль или одно значение типа,являющегося их параметром.В стандартной библиотеке языка Haskell определен класс типов, являющихся монадами.

Определение этого класса приведено ниже:class Monad mreturn ::(>>=) ::(>>)::fail::p >> qfail swherea -> mm a ->m a ->Stringa(a -> m b) -> m bm b -> m b-> m a= p >>= \ _ -> q= error sДанное определение говорит о том, что тип m является монадой, если длянего определены указанные функции и операторы. При этом необходимоопределить только функцию return и оператор >>=; для остальныхфункций и операторов имеются определения по умолчанию.Инфиксный оператор >>= является обобщением наших функций thenMB,thenV и thenL (сравните типы этих функций и оператора).

Функцияreturn предназначена для создания монадического типа из обычногозначения: она «вкладывает» значение в монаду, которая в данном случаерассматривается как контейнер.Тип Maybe является монадой; это отражено в следующем коде:instance Monad Maybe where(>>=) = thenMBreturn a = Just aТаким образом, функцию getPhoneByName, возвращающую значениятипа Maybe Integer, можно определить следующим образом:45getPhoneByName a p n = getAddress a n>>= \address ->getPhone p address >>= \phone ->return phoneМожно дать аналогичные определения для других рассмотренныхмонад:instance Monad Value where(>>=) = thenVreturn a = Value ainstance Monad [ ] where(>>=) = thenLreturn a = [a]Оператор >> используется для комбинирования вычислений, которыене зависят друг от друга; это можно видеть из его определения. Функцию fail рассмотрим несколько позднее.В стандартных библиотеках языка Haskell определено много функцийдля работы с монадами.

Например, функция sequence принимает вкачестве аргумента список монадических вычислений, последовательновыполняет их и возвращает список результатов:sequence :: Monad m => [m a] -> m [a]sequence [] = return []sequence (c:cs) = c>>= \x ->sequence cs>>= \xs ->return (x:xs)Например, выражениеsequence [getAddress a name1, getAddress a name2]вернет список из двух элементов, каждый из которых будет содержатьрезультат выполнения соответствующей функции.Кроме того, поддержка монад встроена непосредственно в язык Haskell.Так называемая do-нотация облегчает запись монадических вычислений.Она позволяет записывать псевдо-императивный код с именованнымипеременными.

Результат монадического вычисления может быть «присвоен» переменной с помощью оператора <-. Выражение справа от этого оператора должно иметь монадический тип m a. Выражение слевапредставляет собой образец, с которым сопоставляется значение внутримонады. Например, (x:xs) может сопоставиться с Maybe [1,2,3]. В46последующих монадических вычислениях можно использовать переменные, связанные в результате этого сопоставления.Проще всего показать использование do-нотации на примере.

Функция getPhoneByName запишется таким образом:getPhoneByName a p n = do address <- getAddress a nphone <- getPhone p addressreturn phoneСравните это определение с определением через оператор >>=. Ключевоеслово do вводит правило выравнивания, заключающееся в том, что первый символ, появляющийся после этого слова, задает колонку, в которойдолжны начинаться последующие строки.

Использование символов {, }и ; позволяет избежать этого правила:getPhoneByName a p n =do { address <- getAddress a n;phone <- getPhone p address; return phone }Do-нотация имеет простые правила преобразования в стандартнуюнотацию:1. Конструкция вида do {e1; e2} преобразуется в e1 >> e22. Конструкция вида do {x <- e1; e2} преобразуется в e1 >>= \x -> e2Таким образом, в этой конструкции нет ничего, что выходило бы зарамки функциональной парадигмы, хотя код, иcпользующий do-нотацию,зачастую напоминает императивный.Для того, чтобы тип был монадой, ему мало принадлежать к классуMonad.

Понятие монад пришло из отрасли математики, которая называется теорией категорий. В ней монадами являются объекты, удовлетворяющие набору аксиом; аналогично, для монад языка Haskell должен выполняться ряд законов. Компилятор языка не проверяет их выполнение(это практически невозможно сделать автоматически) и их правильностьдолжна быть гарантирована программистом.

Вот эти законы:1. return x >>= f ≡ f x2. f >>= return ≡ f3. f >>= (\x -> g x >>= h) ≡ (f >>= g) >>= h47В принципе, первые два закона утверждают, что return являетсялевой и правой единицей для оператора >>=, а третий закон утверждает,что оператор >>= обладает свойством ассоциативности. Рассмотрим этизаконы подробнее.Если мы рассматриваем монады как вычисления, то return x создает тривиальное вычисление, всегда возвращающее значение x.

Еслимы связываем его с другим вычислением f, это эквивалентно непосредственному выполнению f на x. Если этот закон выполняется, следующиедве программы должны быть эквивалентны:law1a = do x <- return af xlaw1b = do f aВторой закон гласит, что если мы выполнили некоторое вычислениеf и передали его результат в тривиальное вычисление, которое просто вернет это значение, это будет эквивалентно тому, что мы простовыполнили это вычисление. Следующие две программы должны бытьэквивалентны:law2a = do x <- freturn xlaw2b = do fНаконец, третий закон утверждает, что независимо от того, в какомпорядке мы группируем действия (слева направо или справа налево),результат не должен меняться. Следующие программы должны быть эквивалентны:law3a = do x <- fdo y <- g xh ylaw3b = do y <- do x <- fg xh yМожно убедиться, что рассмотренные нами монады удовлетворяют этимзаконам.В классе Monad определена функция fail.