Основы функционального программирования/Haskell/Модули и монады: различия между версиями
Ramir (обсуждение | вклад) Нет описания правки |
|||
Строка 1: | Строка 1: | ||
⚫ | |||
{{ОФП Содержание}} |
{{ОФП Содержание}} |
||
⚫ | |||
Языки программирования не обходятся без понятия [[w:модуль (программирование)|модуля]], разве что за исключением языков самого [[w:Низкоуровневый язык программирования|низкого уровня]], да и те в последнее время приобретают высокоуровневые качества. Модули пришли из давнего прошлого, когда [[w:программирование|программирование]] только развивалось. Возникла надобность разбивать программы на логические части, каждую из которых создавал бы отдельный разработчик или коллектив. |
|||
В [[w:Haskell|Хаскеле]] также есть понятие модуля. Но более завораживающее |
В [[w:Haskell|Хаскеле]] также есть понятие модуля. Но более завораживающее новичков явление в языке есть понятие '''монада'''. В этой лекции будут подробно рассмотрены оба понятия. |
||
== Модули == |
== Модули == |
||
В Хаскеле модули несут двоякое назначение: с одной стороны, они необходимы для контроля за пространством имён (как |
В Хаскеле модули несут двоякое назначение: с одной стороны, они необходимы для контроля за пространством имён (как и во всех других языках), с другой стороны, при помощи модулей можно создавать абстрактные типы данных. |
||
Определить модуль в Хаскеле достаточно просто. |
Определить модуль в Хаскеле достаточно просто. Имя модуля состоит из любых символов, лишь начинаться оно должно с прописной буквы. Имя модуля никак не связано с файловой системой (как, например, в [[w:Паскаль|Паскале]] и в [[w:Java|Java]]), то есть имя файла, содержащего модуль, может быть отлично от названия модуля; также, в одном файле может быть несколько модулей, ибо модуль — это всего лишь навсего декларация самого высокого уровня. |
||
Как известно, на верхнем уровне модуля в Хаскеле может быть множество деклараций (описаний и определений): типы, классы, данные, функции. Однако один вид деклараций должен стоять в модуле на первом месте (если этот вид деклараций вообще используется). Речь идет о включении в модуль других модулей |
Как известно, на верхнем уровне модуля в Хаскеле может быть множество деклараций (описаний и определений): типы, классы, данные, функции. Однако один вид деклараций должен стоять в модуле на первом месте (если этот вид деклараций вообще используется). Речь идет о включении в модуль других модулей, что делается словом <code>import</code>. Остальные определения могут появляться в любой последовательности. |
||
Определение модуля должно начинаться со служебного слова module. Например, ниже приведено определение модуля Tree: |
Определение модуля должно начинаться со служебного слова <code>module</code>. Например, ниже приведено определение модуля <code>Tree</code>: |
||
module Tree (Tree (Leaf, Branch), fringe) where |
<code>module Tree (Tree (Leaf, Branch), fringe) where |
||
data Tree a = Leaf a |
data Tree a = Leaf a |
||
Строка 23: | Строка 23: | ||
fringe :: Tree a -> [a] |
fringe :: Tree a -> [a] |
||
fringe (Leaf x) = [x] |
fringe (Leaf x) = [x] |
||
fringe (Branch left right) = fringe left ++ fringe right |
fringe (Branch left right) = fringe left ++ fringe right</code> |
||
В этом модуле описан один тип |
В этом модуле описан один тип: <code>Tree</code> (не беда, что имя типа совпадает с названием модуля: здесь они в различных пространствах имён) и одна функция: <code>fringe</code>. Здесь модуль <code>Tree</code> явно экспортирует тип <code>Tree</code> (вместе со своими подтипами <code>Leaf</code> и <code>Branch</code>) и функцию <code>fringe</code> — для этого имена типа и функции указаны в скобках после имени модуля. Если наименование какого-либо объекта не указывать в скобках, то он не будет экспортироваться, то есть этот объект не будет виден извне текущего модуля. |
||
Использование модуля в другом модуле выглядит еще проще: |
Использование модуля в другом модуле выглядит еще проще: |
||
module Main where |
<code>module Main where |
||
import Tree (Tree(Leaf, Branch), fringe) |
import Tree (Tree(Leaf, Branch), fringe) |
||
main = print (fringe (Branch (Leaf 1) (Leaf 2))) |
main = print (fringe (Branch (Leaf 1) (Leaf 2)))</code> |
||
В приведенном примере видно, что модуль Main импортирует модуль Tree, причём в декларации import явно описано, какие именно объекты импортируются из модуля Tree. Если это описание опустить, то импортироваться будут все объекты, которые модуль экспортирует, то есть в данном случае можно было просто написать: import Tree. |
В приведенном примере видно, что модуль <code>Main</code> импортирует модуль <code>Tree</code>, причём в декларации <code>import</code> явно описано, какие именно объекты импортируются из модуля Tree. Если это описание опустить, то импортироваться будут все объекты, которые модуль экспортирует, то есть в данном случае можно было просто написать: <code>import Tree</code>. |
||
В обычной практике один модуль импортирует несколько других, но при этом в импортируемых модулях есть объекты с одинаковым именем. Естественно, что в этом случае возникает конфликт имён. Чтобы этого избежать в Хаскеле существует специальное служебное слово <code>qualified</code>, при помощи которого определяются те импортируемые модули, имена объектов в которых приобретают вид: <code><Имя Модуля>.<Имя Объекта></code>, то есть для того, чтобы обратиться к объекту из квалифицированного модуля, перед его именем необходимо написать имя модуля: |
|||
module Main where |
<code>module Main where |
||
import qualified Tree |
import qualified Tree |
||
main = print (Tree.fringe (Tree.Leaf ’a’)) |
main = print (Tree.fringe (Tree.Leaf ’a’))</code> |
||
Использование такого синтаксиса полностью лежит на совести программиста. Некоторым нравится полная определённость, которую привносят квалифицированные имена, и они используют их в ущерб размеру программ. Другим нравится использовать короткие мнемонические имена, и они используют квалификаторы (имена модулей) только по необходимости. |
Использование такого синтаксиса полностью лежит на совести программиста. Некоторым нравится полная определённость, которую привносят квалифицированные имена, и они используют их в ущерб размеру программ. Другим нравится использовать короткие мнемонические имена, и они используют квалификаторы (имена модулей) только по необходимости. |
||
=== Абстрактные типы |
=== Абстрактные типы === |
||
В Хаскеле модуль является единственным способом создать так называемые абстрактные типы данных, то есть такие, в которых скрыто представление типа, но открыты только специфические операции над созданным типом, набор которых вполне достаточен для работы с типом. Например, хотя тип Tree является достаточно простым, его все-таки лучше сделать абстрактным типом, то есть скрыть то, что Tree состоит из Leaf и Branch. Это делается следующим образом: |
В Хаскеле модуль является единственным способом создать так называемые абстрактные типы данных, то есть такие, в которых скрыто представление типа, но открыты только специфические операции над созданным типом, набор которых вполне достаточен для работы с типом. Например, хотя тип <code>Tree</code> является достаточно простым, его все-таки лучше сделать абстрактным типом, то есть скрыть то, что <code>Tree</code> состоит из <code>Leaf</code> и <code>Branch</code>. Это делается следующим образом: |
||
module TreeADT (Tree, leaf, branch, cell, left, right, isLeaf) where |
<code>module TreeADT (Tree, leaf, branch, cell, left, right, isLeaf) where |
||
data Tree a = Leaf a |
data Tree a = Leaf a |
||
Строка 62: | Строка 62: | ||
right (Branch l r) = r |
right (Branch l r) = r |
||
isLeaf (Leaf _) = True |
isLeaf (Leaf _) = True |
||
isLeaf _ = False |
isLeaf _ = False</code> |
||
Видно, что к внутренностям типа Tree внешний пользователь (программист) может пробраться только используя определённые функции. Впоследствии, когда создатель этого модуля захочет изменить представление типа (например, оптимизировать его), ему необходимо будет изменить и функции, которые оперируют полями типа Tree. В свою очередь, программист, использовавший в своей программе тип Tree, ничего менять не будет, ибо его программа все так же останется работоспособной. |
Видно, что к внутренностям типа Tree внешний пользователь (программист) может пробраться только используя определённые функции. Впоследствии, когда создатель этого модуля захочет изменить представление типа (например, оптимизировать его), ему необходимо будет изменить и функции, которые оперируют полями типа Tree. В свою очередь, программист, использовавший в своей программе тип Tree, ничего менять не будет, ибо его программа все так же останется работоспособной. |
||
Строка 70: | Строка 70: | ||
Далее приводятся дополнительные аспекты системы модулей в Хаскеле: |
Далее приводятся дополнительные аспекты системы модулей в Хаскеле: |
||
*В декларации импорта (import) можно выборочно спрятать некоторые из экспортируемых объектов служебным словом hiding. Это бывает полезным для явного исключения определений некоторых объектов из импортируемого модуля. |
*В декларации импорта (<code>import</code>) можно выборочно спрятать некоторые из экспортируемых объектов служебным словом <code>hiding</code>. Это бывает полезным для явного исключения определений некоторых объектов из импортируемого модуля. |
||
*При импорте можно определить псевдоним модуля для квалификации имен экспортируемых из него объектов. Для этого используется служебное слово as. Это может быть полезным для того укорачивания имен модулей. |
*При импорте можно определить псевдоним модуля для квалификации имен экспортируемых из него объектов. Для этого используется служебное слово <code>as</code>. Это может быть полезным для того укорачивания имен модулей. |
||
*Все программы неявно импортируют модуль Prelude. Если сделать явный импорт этого модуля, то в его декларации возможно скрыть некоторые объекты, чтобы впоследствии их переопределить. |
*Все программы неявно импортируют модуль <code>Prelude</code>. Если сделать явный импорт этого модуля, то в его декларации возможно скрыть некоторые объекты, чтобы впоследствии их переопределить. |
||
*Все декларации instance неявно экспортируются и импортируются всеми модулями. |
*Все декларации <code>instance</code> неявно экспортируются и импортируются всеми модулями. |
||
*Методы классов могут быть так же как и подтипы данных перечислены в скобках после имени соответствующего класса во время декларации экспорта/импорта. |
*Методы классов могут быть так же как и подтипы данных перечислены в скобках после имени соответствующего класса во время декларации экспорта/импорта. |
||
Строка 80: | Строка 80: | ||
Многие новички в функциональном програмировании бывают часто озадачены понятием монады в Хаскеле. Но монады очень часто встречаются в языке: так, например, система ввода/вывода основана именно на понятии монады, а стандартные библиотеки содержат целые модули, посвящённые монадам. Необходимо отметить, что понятие монады в Хаскеле основано на [[w:теория категорий|теории категорий]], но чтобы не вдаваться в абстрактную математику, далее будет представлено интуитивное понимание монад. |
Многие новички в функциональном програмировании бывают часто озадачены понятием монады в Хаскеле. Но монады очень часто встречаются в языке: так, например, система ввода/вывода основана именно на понятии монады, а стандартные библиотеки содержат целые модули, посвящённые монадам. Необходимо отметить, что понятие монады в Хаскеле основано на [[w:теория категорий|теории категорий]], но чтобы не вдаваться в абстрактную математику, далее будет представлено интуитивное понимание монад. |
||
Монады суть типы, представляющие собой экземпляры одного из следующих монадических классов: Functor, Monad и MonadPlus. Ни один из этих классов не может быть предком для другого класса, то есть монадические классы ненаследуемы. В модуле Prelude определены три монады: IO, [] и Maybe, то есть список также является монадой. |
Монады суть типы, представляющие собой экземпляры одного из следующих монадических классов: <code>Functor</code>, <code>Monad</code> и <code>MonadPlus</code>. Ни один из этих классов не может быть предком для другого класса, то есть монадические классы ненаследуемы. В модуле <code>Prelude</code> определены три монады: <code>IO</code>, <code>[]</code> и <code>Maybe</code>, то есть список также является монадой. |
||
Математически монада определяется через набор правил, которые связывают операции, производимые над монадой. Эти правила дают интуитивное понимание того, как должна использоваться монада и какова ее внутренняя структура. Для конкретизации далее рассматривается класс Monad, в котором определены две базовые операции и одна функция: |
Математически монада определяется через набор правил, которые связывают операции, производимые над монадой. Эти правила дают интуитивное понимание того, как должна использоваться монада и какова ее внутренняя структура. Для конкретизации далее рассматривается класс Monad, в котором определены две базовые операции и одна функция: |
||
class Monad m where |
<code>class Monad m where |
||
(>>=) :: m a -> (a -> m b) -> m b |
(>>=) :: m a -> (a -> m b) -> m b |
||
(>>) :: m a -> m b -> m b |
(>>) :: m a -> m b -> m b |
||
Строка 90: | Строка 90: | ||
fail :: String -> m a |
fail :: String -> m a |
||
m >> k = m >>= \_ -> k |
m >> k = m >>= \_ -> k</code> |
||
Две операции (>>=) и (>>) — это операции связывания. Они комбинируют два монадических значения, тогда как функция return преобразует переданное значение некоторого типа a в монадическое значения типа m a. Сигнатура операции (>>) помогает понять операцию связывания: выражение |
Две операции <code>(>>=)</code> и <code>(>>)</code> — это операции связывания. Они комбинируют два монадических значения, тогда как функция return преобразует переданное значение некоторого типа a в монадическое значения типа <code>m a</code>. Сигнатура операции (<code>>></code>) помогает понять операцию связывания: выражение <code>m a >>= \v m b</code> комбинирует монадическое значение <code>m a</code>, содержащее объект типа <code>a</code>, с функцией, которая оперирует значением <code>v</code> типа <code>a</code> и возвращает результат типа <code>m b</code>. Результатом же комбинации будет монадическое значение типа <code>m b</code>. Операция <code>(>>)</code> используется тогда, когда функция не использует значения, полученного первым монадическим операндом. |
||
Точное значение операция связывания конечно же зависит от конкретной реализации монады. Так, например, тип IO определяет операцию (>>=) как последовательное выполнение двух её операндов, а результат выполнения первого операнда последовательно передается во второй. Для двух других встроенных монадических типов (списки и Maybe) эта операция определена как передача нуля или более параметров из одного вычислительного процесса в следующий. |
Точное значение операция связывания конечно же зависит от конкретной реализации монады. Так, например, тип <code>IO</code> определяет операцию <code>(>>=)</code> как последовательное выполнение двух её операндов, а результат выполнения первого операнда последовательно передается во второй. Для двух других встроенных монадических типов (списки и <code>Maybe</code>) эта операция определена как передача нуля или более параметров из одного вычислительного процесса в следующий. |
||
В Хаскеле определено служебное слово, на уровне языка поддерживающее использование монад: слово do, понимание которого можно увидеть в следующих правилах его применения: |
В Хаскеле определено служебное слово, на уровне языка поддерживающее использование монад: слово <code>do</code>, понимание которого можно увидеть в следующих правилах его применения: |
||
do e1 ; e2 = e1 >> e2 |
<code>do e1 ; e2 = e1 >> e2 |
||
do p <- e1 ; e2 = e1 >>= \p -> e2 |
do p <- e1 ; e2 = e1 >>= \p -> e2</code> |
||
Первое выражение выполняется всегда (переноса значений из первого операнда во второй не производится). Во втором выражении может произойти ошибка, в этом случае производится вызов функции fail, которая также определена в классе Monad. Поэтому более точное определение служебного слова do для второго случая будет выглядеть так: |
Первое выражение выполняется всегда (переноса значений из первого операнда во второй не производится). Во втором выражении может произойти ошибка, в этом случае производится вызов функции <code>fail</code>, которая также определена в классе <code>Monad</code>. Поэтому более точное определение служебного слова <code>do</code> для второго случая будет выглядеть так: |
||
do p <- e1 ; e2 = e1 >>= (\v -> case v of |
<code>do p <- e1 ; e2 = e1 >>= (\v -> case v of |
||
p -> e2 |
p -> e2 |
||
_ -> fail ”s”) |
_ -> fail ”s”)</code> |
||
где s — это строка, которая может определять местоположение оператора do в программе, а может просто нести некоторую семантическую нагрузку. Например, в монаде IO действие (‘a’ getChar) вызовет функцию fail в том случае, если считанный символ не является символом ‘a’. Это действие прерывает исполнение программы, т.к. определенная в монаде IO функция fail в свою очередь вызывает системную функию error. |
где s — это строка, которая может определять местоположение оператора <code>do</code> в программе, а может просто нести некоторую семантическую нагрузку. Например, в монаде <code>IO</code> действие <code>(‘a’ getChar)</code> вызовет функцию <code>fail</code> в том случае, если считанный символ не является символом <code>‘a’</code>. Это действие прерывает исполнение программы, т.к. определенная в монаде <code>IO</code> функция <code>fail</code> в свою очередь вызывает системную функию <code>error</code>. |
||
Класс MonadPlus используется для тех монад, в которых есть нулевой элемент и операция «+». Определение этого класса выглядит следующим образом: |
Класс <code>MonadPlus</code> используется для тех монад, в которых есть нулевой элемент и операция «<code>+</code>». Определение этого класса выглядит следующим образом: |
||
class (Monad m) => MonadPlus m where |
<code>class (Monad m) => MonadPlus m where |
||
mzero :: m a |
mzero :: m a |
||
mplus :: m a -> m a -> m a |
mplus :: m a -> m a -> m a</code> |
||
Нулевой элемент в этом классе монад подчиняется следующим правилам: |
Нулевой элемент в этом классе монад подчиняется следующим правилам: |
||
m >>= \x -> mzero = mzero |
<code>m >>= \x -> mzero = mzero |
||
mzero >>= m = mzero |
mzero >>= m = mzero</code> |
||
Например, для списков нулевым элементом является пустой список [], а операцией «+» — конкатенация списков. Поэтому монада списков является экземпляром класса MonadPlus. С другой стороны монада IO не имеет нулевого элемента, поэтому |
Например, для списков нулевым элементом является пустой список <code>[]</code>, а операцией «<code>+</code>» — конкатенация списков. Поэтому монада списков является экземпляром класса <code>MonadPlus</code>. С другой стороны монада <code>IO</code> не имеет нулевого элемента, поэтому является экземпляром только класса <code>Monad</code>. |
||
=== Встроенные монады === |
=== Встроенные монады === |
||
Строка 125: | Строка 125: | ||
Для конкретизации полученных сведений необходимо рассмотреть что-нибудь более приземленное. Так как списки являются монадами и в то же время списки достаточно скрупулезно изучены, они являются отличным материалом, на котором можно рассмотреть практическое применение механизма монад. |
Для конкретизации полученных сведений необходимо рассмотреть что-нибудь более приземленное. Так как списки являются монадами и в то же время списки достаточно скрупулезно изучены, они являются отличным материалом, на котором можно рассмотреть практическое применение механизма монад. |
||
Для списков операция связывания обретает смысл в соединении вместе набора операций, производимых над каждым элементом списка. При использовании со списками сигнатура операции (>>=) |
Для списков операция связывания обретает смысл в соединении вместе набора операций, производимых над каждым элементом списка. При использовании со списками сигнатура операции <code>(>>=)</code> обретает следующий вид: |
||
(>>=) :: [a] -> (a -> [b]) -> [b] |
<code>(>>=) :: [a] -> (a -> [b]) -> [b]</code> |
||
Это обозначает, что дан список значений типа a и функция, которая проецирует значение типа a на список значений типа b. Связывание применяет функцию к каждому элементу данного списка значений типа a и возвращает полученный список значений типа b. Эта операция уже известна |
Это обозначает, что дан список значений типа <code>a</code> и функция, которая проецирует значение типа <code>a</code> на список значений типа <code>b</code>. Связывание применяет функцию к каждому элементу данного списка значений типа <code>a</code> и возвращает полученный список значений типа <code>b</code>. Эта операция уже известна: определители списков работают именно таким образом. То значит, что следующие три выражения абсолютно одинаковы: |
||
'''Выражение 1''' |
|||
-- Выражение 1 ---------------------------------------------------------------------------------- |
|||
[(x, y) | x <- [1, 2, 3], y <- [1, 2, 3], x /= y] |
<code>[(x, y) | x <- [1, 2, 3], y <- [1, 2, 3], x /= y]</code> |
||
'''Выражение 2''' |
|||
-- Выражение 2----------------------------------------------------------------------------------- |
|||
do x <- [1, 2, 3] |
<code>do x <- [1, 2, 3] |
||
y <- [1, 2, 3] |
y <- [1, 2, 3] |
||
True <- return (x /= y) |
True <- return (x /= y) |
||
return (x, y) |
return (x, y)</code> |
||
'''Выражение 3''' |
|||
-- Выражение 3----------------------------------------------------------------------------------- |
|||
[1, 2, 3] >>= (\x -> [1, 2, 3] >>= (\y -> return (x /= y) >>= |
<code>[1, 2, 3] >>= (\x -> [1, 2, 3] >>= (\y -> return (x /= y) >>= |
||
(\r -> case r of |
(\r -> case r of |
||
True -> return (x, y) |
True -> return (x, y) |
||
_ -> fail ””))) |
_ -> fail ””)))</code> |
||
Какое выражение использовать в написании программ — выбирать программисту. |
Какое выражение использовать в написании программ — выбирать программисту. |
||
Строка 150: | Строка 151: | ||
== Упражнения == |
== Упражнения == |
||
1. Какое интуитивное понимание можно вложить в понятие «монада»? |
|||
1. Какой практический смысл имеет применение монад в функциональном программировании? |
|||
== Ответы для самопроверки == |
== Ответы для самопроверки == |
Версия от 06:30, 28 марта 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
не имеет нулевого элемента, поэтому является экземпляром только класса 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. Какое интуитивное понимание можно вложить в понятие «монада»? 1. Какой практический смысл имеет применение монад в функциональном программировании?
Ответы для самопроверки
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. Применение монад в функциональных языках — это по существу возвращение к императивности. Ведь операции связывания (>>=
) и (>>
) предполагают последовательное выполнение связанных выражений с передачей или без результатов вычисления. Т. е. монады — это императивное ядро внутри функциональных языков. С одной стороны это идёт в разрез с теорией функционального програмирования, где отрицается понятие императивности, но с другой стороны некоторые задачи решаются только при помощи императивных принципов. И опять же, Хаскел предоставляет удивительную возможность по генерации списков, но это только благодаря тому, что сам тип «список» выполнен в виде монады.