Основы функционального программирования/Haskell/Модули и монады: различия между версиями

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
мНет описания правки
Строка 155: Строка 155:
== Ответы для самопроверки ==
== Ответы для самопроверки ==


#Первое, что приходит в голову это то, что монада — это контейнерный тип. Ведь действительно, список — это контейнерный тип, т.к. внутри списка содержатся элементы другого типа. Именно это и показано в определении монадического типа:
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


<code>class Monad m where
Запись «m a» как бы показывает, что тип a (необходимо чётко помнить, что при определении классов и других типов данных символы типа a, b и т.д. обозначают переменные типов) обрамлён монадическим типом m. Однако в реальности физическое обрамление доступно только для монадического типа «список», т.к. его обозначение в виде квадратных скобок пошло традиционно. В строгой нотации Haskell’а нужно было бы писать что-нибудь вроде: List (1 2 3 4 5) — это список [1, 2, 3, 4, 5].
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
return :: a -> m a
fail :: String -> m a</code>


Запись «<code>m a</code>» как бы показывает, что тип <code>a</code> (необходимо чётко помнить, что при определении классов и других типов данных символы типа <code>a</code>, <code>b</code> и&nbsp;т.&nbsp;д. обозначают переменные типов) обрамлён монадическим типом <code>m</code>. Однако в реальности физическое обрамление доступно только для монадического типа «список», т.&nbsp;к. его обозначение в виде квадратных скобок пошло традиционно. В строгой нотации Хаскела нужно было бы писать что-нибудь вроде: <code>List (1 2 3 4 5)</code> — это список <code>[1, 2, 3, 4, 5]</code>.
#Применение монад в функциональных языках — это по существу возвращение к императивности. Ведь операции связывания (>>=) и (>>) предполагают последовательное выполнение связанных выражений с передачей или без результатов вычисления. Т.е. монады — это императивное ядро внутри функциональных языков. С одной стороны это идёт в разрез с теорией функционального програмирования, где отрицается понятие императивности, но с другой стороны некоторые задачи решаются только при помощи императивных принципов. И опять же, Haskell предоставляет удивительную возможность по генерации списков, но это только благодаря тому, что сам тип «список» выполнен в виде монады.

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

Версия от 10:26, 24 марта 2006

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

В Хаскеле также есть понятие модуля. Но более завораживающее неофитов явление в языке есть понятие монады. В этой лекции будут подробно рассмотрены оба понятия.

Модули

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

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

Как известно, на верхнем уровне модуля в Хаскеле может быть множество деклараций (описаний и определений): типы, классы, данные, функции. Однако один вид деклараций должен стоять в модуле на первом месте (если этот вид деклараций вообще используется). Речь идет о включении в модуль других модулей; для этого используется служебное слово 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.

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

module Main where

import qualified Tree

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

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

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

В Хаскеле модуль является единственным способом создать так называемые абстрактные типы данных, то есть такие, в которых скрыто представление типа, но открыты только специфические операции над созданным типом, набор которых вполне достаточен для работы с типом. Например, хотя тип 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, ничего менять не будет, ибо его программа все так же останется работоспособной.

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

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

  • В декларации импорта (import) можно выборочно спрятать некоторые из экспортируемых объектов служебным словом hiding. Это бывает полезным для явного исключения определений некоторых объектов из импортируемого модуля.
  • При импорте можно определить псевдоним модуля для квалификации имен экспортируемых из него объектов. Для этого используется служебное слово as. Это может быть полезным для того укорачивания имен модулей.
  • Все программы неявно импортируют модуль Prelude. Если сделать явный импорт этого модуля, то в его декларации возможно скрыть некоторые объекты, чтобы впоследствии их переопределить.
  • Все декларации instance неявно экспортируются и импортируются всеми модулями.
  • Методы классов могут быть так же как и подтипы данных перечислены в скобках после имени соответствующего класса во время декларации экспорта/импорта.

Монады

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

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

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

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