2014-02-13
491
Монады
Классы типов
Классы типов позволяют указывать типы являющиеся экземплярами классов, и предоставлять определения ассоциированных с классом операций, перегруженных для каждого типа. Например, класс, содержащий оператор равенства имеет вид:
class Eq a where
(= =):: а —> а —> Bool
Здесь Eq - имя определяемого класса. = = - операция, определенная в классе. Это определение означает, что «тип а является экземпляром класса Eq, если для него существует перегруженный оператор = =».
Консрукция Eq а выражает ограничение на тип и называется контекстом. Контексты располагаются перед описаниями типов.
Например:
elem:: (Eq a) => а —> [ а ] —> Bool
Эта запись выражает факт, что функция elem определена только для тех тпов, для которых определен оператор равенства. Указать типы принадлежащие классу Eq и определить функции сравнения для этих типов можно с помощью определения принадлежности:
instance Eq Integer where
x = = у = x `integerEq` у
Определение оператора = = называется методом. Функция integerEq сравнивает на равенство два целых числа. В общем случае в правой части определения допустимо любое выражение, как и при обычном определении функции.
При определении принадлежности можно использовать контекст. Пусть определен рекурсивный тип для дерева:
data Tree a = Leaf a | Branch (Tree a) (Tree a)
Тогда можно определить оператор поэлементного сравнения деревьев:
instance (Eq a) => Eq (Tree a) where
Leaf a == Leaf b = a == b
(Branch 1 1 r l) == (Branch 1 2 r 2) = (1 1 == 1 2) && (r l == r 2)
_ == _ = False
В стандартных библиотеках языка Haskell определено много классов типов. Класс Eq в действительности определен следующим образм:
class Eq a where
(==), (/=):: а —> а —> Bool
х /= у = not (х == у)
Здесь определены две операции: равенство и неравенство. При этом использовано определение метода по умолчанию для неравенства. Если метод для какого-либо экземпляра класса пропущен в определении принадлежности, используется метод, определенный в классе, если он существует.
Haskell также поддерживает расширения класса. Например, можно определить класс Ord, который наследует все операции класса Eq, и кроме того, определяет новые операторы сравнения и функции минимум и максимум:
class (Eq a) => Ord a where
(<), (<=), (>=), (>):: a -> a -> Bool
max, min:: a -> a -> a
Говорят, что Eq является суперклассом класса Ord (соответственно, Ord является подклассом Eq).
Понятие монад является одним из важнейших в языке Haskell.
Одной из простейших монад является тип Maybe. Он определен следующим образом:
data Maybe a = Nothing | Just a
Этот тип может использоваться для представления значения функций, включая случай, когда значение отсутсвует. Например, функция f с сигнатурой
f:: а —> Maybe b
принимает значение типа а и возвращает результат типа b (обернутый в конструктор Just), либо может не вычислить значения и тогда вернет значение Nothing.
Типичным примером такого рода функций служат функции для запросов к базе данных. В случае, если данные, удовлетворяющие критериям запроса, существуют, их следует предоставить; в противном случае возвращается Nothing.
Рассмотрим базу данных, содержащую информацию об адресах людей. Она устанавливает соответствие между полным именем человека и его адресом. Для простоты предположим, что имя и адрес задаются строками. Тогда базу данных можно описать следующим образом:
type AddressDB = [(String, String)]
Таким образом, база данных представляет собой список пар, первым компонентом которых будет имя, а вторым - адрес. Определим функцию
getAddress, которая по заданному имени возвращает адрес:
getAddress:: AddressDB —> String —> Maybe String
getAddress [] _ = Nothing
getAddress ((name,address):rest) n | n == name = Just address
| otherwise = getAddress rest n
Для имен, присутствующих в базе, функция возвращает соответствующий адрес. Если такого имени в базе нет, возвращается Nothing.
Предположим, что имеется еще одна база данных, содержащая информвцию об адресах и номерах телефонов:
type PhoneDB = [(String,Integer)]
Пусть имеется функция getPhone, по адресу возвращающая телефон, реализованная с помощью типа Maybe аналогично функции getAddress. Требуется определить функцию, возвращающую телефон по имени владельца.
Значение Nothing эта функция может вернуть в следующих случаях:
1. Указанное имя не содержится в базе адресов.
2. Адрес, соответствующий указанному имени, существует, однако он
не содержится в базе телефонов.
Исходя из этих соображений, функцию getPhoneByName можно определить следующим образом:
getPhoneByName:: AddressDB -> PhoneDB -> String -> Maybe Integer
getPhoneByName a p n =
case (getAddress a n) of
Nothing —> Nothing
Just address —> case (getPhone p address) of
Nothing —> Nothing
Just phone —> Just phone
Использованный стиль программирования может привести к ошибкам. В случае, когда уровень вложенности запросов увеличивается, растет и объем повторяющегося кода. Поэтому определим вспомогательную функцию thenMB, которая реализует использованный в функции getPhoneByName шаблон связывания функций, возвращающих значение типа Maybe.
thenMB:: Maybe a —> (а —> Maybe b) —> Maybe b
thenMB mB f = case mB of
Nothing —> Nothing
Just a —> f a
Эта функция принимает два аргумента: значение типа Maybe а и функцию, отображающую значение типа а в значение типа Maybe b. Если первый аргумент содержит значение Nothing, второй аргумент игнорируется. Если первый аргумент содержит реальное значение, обернутое в конструктор Just, оно извлекается и передается в функцию, являющуюся вторым аргументом. Переопределим функцию getPhoneByName следующим образом:
getPhoneByName a p n = getAddress a n 'thenMB' \address —>
getPhone p address 'thenMB' phone —> Just phone
Вычисление этой функции можно понимать как передачу результата левого аргумента оператора 'thenMB' переменной из лямбда-абстракции правого аргумента.
Таким образом, мы определили функцию thenMB, комбинирующую вычисления, которые могут либо предоставить результат, либо отказ от его вычисления. Функция thenMB не зависит от того, какие вычисления она комбинирует, требуется только, чтобы они удовлетворяли ее сигнатуре. Этуфункцию можно использовать для любых аналогичных задач. Она определяет правило комбинирования вычислений в виде цепочки, заключающееся в том, что если одно из вычислений не выполнилось, не выполняется и вся цепочка.
Усовершенствуем рассматриваемый пример. Потребуем, чтобы в случае неудачи функция getPhone сообщала о причине по которой она не нашла телефон. Для этого определим функции, getAddress и getPhoneByName таким образом, чтобы они возвращали значение типа Value, который определим следующим образом:
data Value a = Value a | Error String
Значение типа Value a представляет собой либо значение типа a, обернутое в конструктор Value, либо строковое сообщение об ошибке, содержащееся в конструкторе Error. Функцию get Address определим следующм образом:
getAddress:: AddressDB -> String -> Value String
getAddress [] _ = 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 -> String -> Value Integer
getPhoneByName a p n = case (getAddress an)of
Error s -> Error s
Value address -> case (getPhone p address) of
Error s -> Error s Value phone -> Value phone
Здесь имеет место проблема, как и в предыдущем варианте. Для ее решения: определим вспомогательную функцию:
thenV:: Value a -> (а -> Value b) -> Value b
thenV mV f = case mV of
Error s -> Error s
Value v -> f v
С использованием этой функции можно упростить определение getPhoneByName:
getPhoneByName a p n = getAddress a n `thenV` \address ->
getPhone p address `thenV` \phone ->
Value phone
Имеется сходство в определении функций thenMB и thenV, а также в определениях функции getPhoneByName. Тип Value также представляет пример монады.
Обобщим рассмотренную задачу. Предположим, что одному человеку может соответствовать несколько адресов, а одному адресу - несколько телефонов. Тогда функции get Phone, getAddress и getPhoneByName должны возвращать списки. Их сигнатуры имеют вид:
getAddress:: AddressDB -> String -> [String]
getPhone:: PhoneDB -> String -> [Integer]
getPhoneByName:: AddressDB -> PhoneDB -> String -> [Integer]
Пусть функции getPhone и getAddress в случае неудачи возвращают пустые списки, а в случае успешного поиска - списки значений. Используя эти функции можно определить функцию getPhoneByName. Однако вначале определим вспомогательную функцию:
thenL:: [а] -> (a -> [b]) -> [b]
thenL mL f = case mL of
[] -> []
(x:xs) -> f x ++ thenL xs f
Тогда:
getPhoneByName a p n = getAddress a n `thenL` \address ->
getPhone p address `thenL` \phone ->
[phone]
Cписок также является монадой.
Монада - это тип данных, подразумевающий определенную стратегию комбинирования вычислений
С другой стороны, монаду можно рассматривать как контейнерный тип, т. е. как тип, значения которого содержат в себе некоторое количество элементов другого типа.
В стандартной библиотеке языка Haskell определен класс типов, являющихся монадами.
class Monad m where
return:: a -> m a
(»=):: m a -> (a -> m b) -> m b
(»):: m a -> m b -> m b
fail:: String -> m a
p» q = p»= \ _ -> q
fail s = error s
Таким образом тип m является монадой, если для него определены указанные функции и операторы. При этом необходимо определить только функцию return и оператор»=; для остальных функций и операторов даны определения по умолчанию.
Инфиксный оператор»= служит обозначением таких функций как thenMB, thenV и thenL. Функция return предназначена для создания монадического типа. Она «вкладывает» значение в монаду, которая рассматривается как контейнер.
Для типа Maybe имеется определение принадлежности вида:
instance Monad Maybe where
(»=) = thenMB
return a = Just a
Таким образом, функцию getPhoneByName, возвращающую значения типа Maybe Integer, можно определить следующим образом:
getPhoneByName a p n = getAddress a n»= \address ->
getPhone p address»= \phone ->
return phone
Можно дать определения принадлежности и для других рассмотренных монад:
instance Monad Value where
(»=) = thenV
return a = Value a
instance Monad [ ] where
(»=) = thenL
return a = [a]
Оператор» используется для комбинирования вычислений, которые не зависят друг от друга.
Поддержка монад встроена непосредственно в язык Haskell. Так называемая do-нотация облегчает запись монадических вычислений. Она позволяет записывать псевдо-императивный код с именованными переменными. Результат монадического вычисления может быть «присвоен» переменной с помощью оператора <-. Выражение справа от этого оператора должно иметь монадический тип m а. Выражение слева представляет собой образец, с которым сопоставляется значение внутри монады. В последующих монадических вычислениях можно использовать переменные, связанные в результате этого сопоставления.
Функция getPhoneByName при использовании do нотации имеет вид:
getPhoneByName a p n =
do address <- getAddress a n
phone <- getPhone p address
return phone
Ключевое слово do вводит правило выравнивания, заключающееся в том, что первый символ, появляющийся после этого слова, задает колонку, в которой должны начинаться последующие строки. Использование символов {, } и; позволяет не использоваь правило выравнивания:
do-нотация использует простые правила преобразования в стандартную нотацию:
1. Конструкция вида do {el; e2} преобразуется в el» e2
2. Конструкция вида do {х <- el; е2} преобразуется в el»= \х -> е2
Понятие монад происходмит из области математики, которая называется теорией категорий. В ней монадами являются объекты, удовлетворяющие набору аксиом; аналогично, для монад языка Haskell должен выполняться ряд законов. Компилятор языка не проверяет их выполнение (это практически невозможно сделать автоматически) и их правильность должна быть гарантирована программистом. Эти законы имеют вид:
return х»= f ≡ f x
f»= return ≡ f
f»= (\x -> g x»= h) ≡ (f»= g)»= h
Первые два закона утверждают, что return является левой и правой единицей для оператора»=, а третий закон утверждает, что оператор»= обладает свойством ассоциативности. Рассмотрим эти законы подробнее.
Если рассматривать монады как вычисления, то return x создает тривиальное вычисление, всегда возвращающее значение х. Если связать его с вычислением f, то это эквивалентно непосредственному выполнению f от х. Если этот закон выполняется, то следующие две программы должны быть эквивалентны:
do х <- return a f х
do f a
Второй закон утверждает, что если выполнено некоторое вычисление f и его результат передан в тривиальное вычисление, то это эквивалентно просто выполнению этого вычисления. Следующие две программы должны быть эквивалентны:
do х <- f
return x
do f
Третий закон утверждает, что независимо от того, в каком порядке сгруппированны действия (слева направо или справа налево), результат не должен меняться. Следующие программы должны быть эквивалентны:
do x <- f
do у <- g x
h у
do у <- do x <- f
g x
h у
В классе Monad определена функция fail. Она вызывается в том случае, если при сопоставлении с образцом в do-нотации произошла ошибка. По умолчанию эта функция печатает сообщение и завершает программу, однако в некоторых монадах ее имеет смысл переопределить. Например, для монады Maybe ее определяют следующим образом:
fail _ = Nothing
Аналогично для списка:
fail _ = []
Рассмотрим так называемые монады состояния. Императивные программы можно представить как ряд последовательных изменений состояния программы. В императивных языках состояние присутствует неявно; в функциональных языках его необходимо явно передавать в качестве аргумента функции.
Рассмотрим задачу генерации псевдослучайных чисел. В компьютере псевдослучайные числа генерируются с помощью рекуррентных соотношений вида x k = f (x k-1), где x k- k- ечисло. Примером такого датчика, генерирующего вещественные числа в диапазоне от 0 до 1, в простейшем случае может служить соотношение
x k = {11 x k-1 + π},
где {} - оператор взятия дробной части.
В императивном языке можно реализовать функцию без аргументов, при каждом вызове возвращающей новое псевдослучайное число. При этом состояние датчика, представляющее в данное случае предыдущее значение последовательности, можно хранить в глобальной переменной. В языке Haskell значение функции полностью определяется ее аргументами и состояние (предыдущее значение последовательности) необходимо передавать явно. Таким образом, функция, вычисляющая объем параллелепипеда со случайными сторонами, запишется следующим образом:
random х = frac (pi + х * 11)
cube x0 = let xl = random x0
x2 = random xl
x3 = random x2
in xl * x2 * x3
Здесь в качестве параметра функции cube выступает начальное значение для генератора, а состояние передается из одного вызова функции random в другой явно.
В данном случае состояние датчика и его возвращаемого значения совпадают. Однако это не обязательно. Датчик может учитывать при вычислении очередного значения не только предыдущее значение, но и предшествующее ему. Можно разделить состояние, передаваемое от одного вызова к другому и возвращаемое значение. Это позволяет рассматривать состояние отдельно от возвращаемого значения. Сделаем следующие определения:
type State =... -- Определение типа состояния
data StateT a = State -> (a, State)
random:: StateT Float
Тип StateT определяет значения, являющиеся преобразователями состояния, т. е. функциями, которые преобразуют заданное состояние в другое состояние, возвращая при этом некоторое значение. Таким образом, функция random фактически имеет тип State -> (Float,State). По заданному состоянию она возвращает два значения: очередное псевдослучайное число и новое состояние. Функция cube запишется таким образом:
cube s0 = let (xl,sl) = random s0
(x2,s2) = random s1
(x3,s3) = random s2
in xl * x2 * x3
Тип StateT можно объявить монадой, если сделать следующие определения:
instance Monad StateT where
st»= f = \s -> let (x,sl) = st s
in f x s1
return a = \s -> (a,s)
Оператор»= связывает состояния, передавая их из одного вычисления в другое, а функция return возвращает функцию, которая оставляет состояние неизменным и возвращает указанное значение. Применяя do-нотацию, получим:
cube:: StateT Float
cube = do x1 <- random
x2 <- random
x3 <- random
return (xl * x2 * x3)
Монады состояния являются основой для определения операций ввода-вывода в языке Haskell. Пусть имеется функция getChar, которая по заданному дескриптору файла типа FileHandle возвращает очередной прочитанный из него символ:
getChar:: FileHandle -> Char
Эта функция не возвращает одно и то же значения, будучи вызвана с одним и тем же аргументом. Ее результат зависит не только от аргумента, но и от состояния файла, которое меняется при вызове этой функции.
Одним из решений этой проблемы будет явная передача этого состояния в функции, осуществляющие ввод-вывод. Таким образом, каждая из функций ввода-вывода будет принимать дополнительный параметр типа World, описывающим состояние внешнего мира, и возвращать, помимо результата, измененное состояние мира.
В Haskell определен тип IO а, аналогичный типу StateT, при этом вместо типа State используется World. Определение оператора связывания >>= гарантирует, что это значение не будет использоваться более одного раза. Определяется ряд базовых операций, осуществляющих основные операции ввода-вывода: открыть файл, считать символ из файла и т. п. Важным свойством этих операций является то, что они возвращают значение типа IO. Например, функция для считывания символа из файла имеет тип
getChar:: FileHandle -> IO Char
Программа на языке Haskell представляет собой функцию main:: IO (), содержащую последовательность операций ввода-вывода (их называют действиями). Эта функция неявно передает состояние мира в последовательность действий.
Необходимо отметить два важных свойства типа IO.
1. Это абстрактный тип данных: пользователю недоступны конструкторы данных этого типа, невозможно извлечь значение из него без использования монадических конструкций и т. д.
2. Любая функция, использующая значение, помеченное конструктором IO, должна возвращать значение, также помеченное этим конструктором. Если функция не содержит в своей сигнатуре типа IO, значит, она не выполняет никаких операций ввода-вывода: это гарантируется системой проверки типов. Таким образом, части программы, которые выполняют ввод-вывод, явно отделены от чисто функционального ядра.
Использование монад позволяет определить небольшой под-язык в рамках языка Haskell и программировать на нем практически в императивном стиле.
