1. Нашёл ошибку?
2. Выдели её мышью.
3. Нажми Ctrl-Enter.

[ закрыть ]

Лекция 6. "Модули и монады в Haskell'е"

Понравились лекции? Используете их для обучения? Можете отблагодарить автора:

рублей Яндекс.Деньгами
на счет 4100137733052 (Лекции по Функциональному программированию)

Ни один язык программирования не обходится без понятия модуля, разве что только языки самого низкого уровня, да и те в последнее время приобретают свойства языков более высокого уровня. Модули пришли из давнего прошлого, когда программирование, как искусство (или ремесло), только развивалось. Возникла необходимость разбивать программы на логические части, каждую из которых создавал бы отдельный разработчик или коллектив разработчиков.

В Haskell'е также существует понятие модуля. Однако более интригующим и завораживающим неофитов явлением в языке является понятие "монада". Далее в этой лекции будут подробно рассмотрены оба понятия — "модуль" и "монада".

Модули

В Haskell'е модули несут двоякое назначение — с одной стороны модули необходимы для контроля за пространством имён (как, собственно, и во всех других языках программирования), с другой стороны при помощи модулей можно создавать абстрактные типы данных.

Определение модуля в Haskell'е достаточно просто. Именем модуля может быть любой символ, начинается имя только с заглавной буквы. Дополнительно имя модуля никак не связано с файловой системой (как, например, в Pascal'е и в Java), т.е имя файла, содержащего модуль, может быть не таким же, как и название модуля. На самом деле, в одном файле может быть несколько модулей, т.к. модуль — это всего лишь навсего декларация самого высокого уровня.

Как известно, на верхнем уровне модуля в Haskell'е может быть множество деклараций (описаний и определений) — типы, классы, данные, функции. Однако один вид деклараций должен стоять в модуле на первом месте (если этот вид деклараций вообще используется). Речь идет о включении в модуль других модулей — для этого используется служебное слово import. Остальные определения могут появляться в любой последовательности.

Определение модуля должно начинаться со служебного слова module. Например, ниже приведено определение модуля Tree:

module Tree (Tree (Leaf, Branch), fringe) where

data Tree a	= 	Leaf a
			| Branch (Tree a) (Tree a)

fringe			:: Tree a -> [a]
fringe (Leaf x)		= [x]
fringe (Branch left right)	= fringe left ++ fringe right

В этом модуле описан один тип (Tree — ничего страшного, что имя типа совпадает с названием модуля, в данном случае они находятся в различных пространствах имён) и одна функция (fringe). В данном случае модуль Tree явно экспортирует тип Tree (вместе со своими подтипами Leaf и Branch) и функцию fringe — для этого имена типа и функции указаны в скобках после имени модуля. Если наименование какого-либо объекта не указывать в скобках, то он не будет экспортироваться, т.е. этот объект не будет виден извне текущего модуля.

Использование модуля в другом модуле выглядит еще проще:

module Main where

import Tree (Tree(Leaf, Branch), fringe)

main = print (fringe (Branch (Leaf 1) (Leaf 2)))

В приведенном примере видно, что модуль Main импортирует модуль Tree, причём в декларации import явно описано, какие именно объекты импортируются из модуля Tree. Если это описание опустить, то импортироваться будут все объекты, которые модуль экспортирует, т.е. в данном случае можно было просто написать: import Tree.

Бывает так, что один модуль импортирует несколько других (надо заметить, что это обычная ситуация), но при этом в импортируемых модулях существуют объекты с одним и тем же именем. Естественно, что в этом случае возникает конфликт имён. Чтобы этого избежать в Haskell'е существует специальное служебное слово qualified, при помощи которого определяются те импортируемые модули, имена объектов в которых приобретают вид: <Имя Модуля>.<Имя Объекта>, т.е. для того, чтобы обратиться к объекту из квалифицированного модуля, перед его именем необходимо написать имя модуля:

module Main where

import qualified Tree

main = print (Tree.fringe (Tree.Leaf 'a'))

Использование такого синтаксиса полностью лежит на совести программиста. Некоторым нравится полная определённость, которую привносят квалифицированные имена, и они используют их в ущерб размеру программ. Другим нравится использовать короткие мнемонические имена, и они используют квалификаторы (имена модулей) только по необходимости.

Абстрактные типы данных

В Haskell'е модуль является единственным способом создать так называемые абстрактные типы данных, т.е. такие, в которых скрыто представление типа, но открыты только специфические операции над созданным типом, набор которых вполне достаточен для работы с типом. Например, хотя тип Tree является достаточно простым, его все-таки лучше сделать абстрактным типом, т.е. скрыть то, что Tree состоит из Leaf и Branch. Это делается следующим образом:

module TreeADT (Tree, leaf, branch, cell, left, right, isLeaf) where

data Tree a		= Leaf a
			| Branch (Tree a) (Tree a)

leaf				= Leaf
branch			= Branch
cell (Leaf a)		= a
left (Branch l r)		= l
right (Branch l r)	= r
isLeaf (Leaf _)		= True
isLeaf _			= False

Видно, что к внутренностям типа Tree внешний пользователь (программист) может пробраться только при помощи использования определённых функций. Впоследствии, когда создатель этого модуля захочет изменить представление типа (например, оптимизировать его), ему необходимо будет изменить и функции, которые оперируют полями типа Tree. В свою очередь программист, который использовал в своей программе тип Tree, ничего менять не будет, т.к. его программа все так же останется работоспособной.

Другие аспекты использования модулей

Далее приводятся дополнительные аспекты системы модулей в Haskell'е:

· В декларации импорта (import) можно выборочно спрятать некоторые из экспортируемых объектов (при помощи служебного слова hiding). Это бывает полезным для явного исключения определений некоторых объектов из импортируемого модуля.

· При импорте можно определить псевдоним модуля для квалификации имен экспортируемых из него объектов. Для этого используется служебное слово as. Это может быть полезным для того укорачивания имен модулей.

· Все программы неявно импортируют модуль Prelude. Если сделать явный импорт этого модуля, то в его декларации возможно скрыть некоторые объекты, чтобы впоследствии их переопределить.

· Все декларации instance неявно экспортируются и импортируются всеми модулями.

· Методы классов могут быть так же как и подтипы данных перечислены в скобках после имени соответствующего класса во время декларации экспорта/импорта.

Монады

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

Монады являются типами, которые представляют собой экземпляры одного из следующих монадических классов: 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 "")))

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

Упражнения

1. Какое интуитивное понимание можно вложить в понятие "монада"?

2. Какой практический смысл имеет применение монад в функциональном программировании?

Ответы для самопроверки

1. Первое, что приходит в голову это то, что монада — это контейнерный тип. Ведь действительно, список — это контейнерный тип, т.к. внутри списка содержатся элементы другого типа. Именно это и показано в определении монадического типа:

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 a" как бы показывает, что тип a (необходимо чётко помнить, что при определении классов и других типов данных символы типа a, b и т.д. обозначают переменные типов) обрамлён монадическим типом m. Однако в реальности физическое обрамление доступно только для монадического типа "список", т.к. его обозначение в виде квадратных скобок пошло традиционно. В строгой нотации Haskell'а нужно было бы писать что-нибудь вроде: List (1 2 3 4 5) — это список [1, 2, 3, 4, 5].

2. Применение монад в функциональных языках — это по существу возвращение к императивности. Ведь операции связывания (>>=) и (>>) предполагают последовательное выполнение связанных выражений с передачей или без результатов вычисления. Т.е. монады — это императивное ядро внутри функциональных языков. С одной стороны это идёт в разрез с теорией функционального програмирования, где отрицается понятие императивности, но с другой стороны некоторые задачи решаются только при помощи императивных принципов. И опять же, Haskell предоставляет удивительную возможность по генерации списков, но это только благодаря тому, что сам тип "список" выполнен в виде монады.

Наверх | Содержание | Лекции | НАУКА ·]

Сайт управляется системой uCoz