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

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск
Лекции по функциональному программированию
1. Вводная лекция
2. Структуры данных и базисные операции
3. Структуры данных и базисные операции — 2
4. Основы языка Haskell
5. Служебные слова и синтаксис Haskell'а
6. Модули и монады в Haskell'е
7. Операции ввода/вывода в Haskell'е
8. Конструирование функций
9. Доказательство свойств функций
10. Формализация ФП на основе λ-исчисления
11. Трансформация программ

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

В этой лекции освещается, как в Хаскеле работают модули и более интересное новичкам явление монады.

Модули[править]

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

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