Что такое монада в программировании

Монада (программирование)

Мона́да в программировании — это абстракция линейной цепочки связанных вычислений. Её основное назначение — инкапсуляция функций с побочным эффектом от чистых функций, а точнее их выполнений от вычислений [1] . Монады применяются в языке Haskell, так как он повсеместно использует ленивые вычисления, которые вместе с побочным эффектом, как правило, образуют плохо прогнозируемый результат. Она описывается [2] полиморфным контейнерным типом для выполнений с одним параметром, стратегией «поднятия» значения в монаду и стратегией связывания двух вычислений, второе из которых зависит от параметра, вычисляемого первым:

m :: * -> * 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 class Functor f where fmap :: (a -> b) -> f a -> f b

Функция return описывает «возвращение» (втягивание) типа a в монаду m , то есть обрамление его контейнером. Функция fail не имеет отношения к теоретической сущности монад, однако используется в случае ошибки сопоставления с образцом внутри монадического кода — останавливает процесс последовательных действий и выводит сообщение о причине ошибки (в будущих версиях библиотеки может быть переведён в отдельный класс [3] ). Оператор >>= описывает, что в монаде действия происходят последовательно, то есть после применения функции её результат передаётся далее (.. -> a -> b -> ..), примером которой может быть передача текста в буфер: типы данные облачаются в монаду (конструктором), а затем с ними функция производит действия, в данном случае добавление. Оператор >> — частный случай оператора >>= , когда предыдущие данные просто заменяются следующими, которые не формируются на основании предыдущих.

В частности, к монадам относятся:

• IO (монада строго последовательных вычислений): стратегия связывания — «сначала первое вычисление, затем второе»;
• Maybe (монада вычислений с отсутствующими значениями): стратегия связывания — «если первое вычисление дало результат, то второе; иначе — отсутствие результата»;
• List (монада вычислений с несколькими результатами): стратегия связывания — «все возможные результаты второго вычисления, примененного к каждому из вычисленных первым значений параметра»;
• State (монада вычислений с переменной состояния): стратегия связывания — «начать второе вычисление с состоянием, измененным в результате первого»;
• и некоторые другие типы.

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

Концепция монад в программировании была унаследована из теории категорий: Монада (математика)

Примечания

1. ↑ Контейнер не имеет задачи инкапсулирования данных.
2. ↑ Описание класса Monad находится в модуле Monad пакета Control и в стандартном модуле Prelude , класса Functor и MonadPlus — только в модуле Monad пакета Control .
3. ↑Евгений Кирпичев.Монады в Haskell (рус.) . Монады — «обобщение некоторых привычных идиом, а также как еще один метод для их абстракции».

Ссылки

Учебные пособия

• Monad Tutorials Timeline (англ.) Большая коллекция пособий по монадам, представлены в порядке появления.
• What the hell are Monads?
• You Could Have Invented Monads! (And Maybe You Already Have.), простое введение
• All About Monads
• Monads as Computation
• Monads as Containers
• Monads for the Working Haskell Programmer
• The Haskell Programmer’s Guide to the IO Monad — Don’t Panic
• Introduction to Haskell, Part 3: Monads
• On Monads
• Crash Monad Tutorial (англ.) — статья о монадах, объясняющая их с точки зрения теории категорий
• Learn You a Haskell for Great Good! (англ.) — книга содержит доступное описание языка Haskell, в котором много внимания уделено понятию монады и аналогичным конструкциям

Другие статьи

• A tour of the Haskell Monad functions (англ.)
• Notions of Computation and Monads от Eugenio Moggi, первая статья, предлагающая использование монад в программировании
• «Monads for Functional Programming» от Philip Wadler, описание монад в языке Хаскелл (написано еще до того, как они в нем появились)
• 4. Монады — простое изложение основ языка

Литература

• Душкин Р.В. Охрана // Приёмы программирования // Функции // Синтаксис и идиомы языка // Справочник по языку Haskell / Гл. ред. Д. А. Мовчан. — М .: ДМК Пресс, 2008. — С. 37-38. — 554 с. — 1500 экз. — ISBN 5-94074-410-9, ББК 32.973.26-018.2, УДК 004.4
• П. Д. Симон. 8. Лекция: Стандартное начало (Prelude) // Язык и библиотеки Haskell 98.
• Erkok Levent. Value Recursion in Monadic Computations. Oregon Graduate Institute. — 2002. — 162 p.

• Теория категорий
• Haskell
• Концепции языков программирования

Wikimedia Foundation . 2010 .

Записки программиста

Когда я впервые увидел код в стиле f1 >>= \x -> f2 >>= \y -> Right ( x , y ) моя реакция была «Ааа! Что тут происходит? Как вообще кто-то может писать на таком языке?». Но, как выяснилось, если сесть и спокойно во всем разобраться, в монадах нет абсолютно ничего сложного. Кроме того, оказывается, монады имеют множество важных практических применений и способны существенно облегчить выполнение нашей с вами повседневной работы.

Что такое монада?

В Haskell монада — это совершенно обычный класс типов:

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

С тем же успехом мы можем объявить интерфейс в Java или абстрактный класс в C++. В большинстве случаев для превращения некого типа в монаду достаточно определить только функции ( >>= ) (произносится «bind») и return , потому что остальные функции имеют разумную реализацию по умолчанию.

Функции (>>=), (>>), return и fail

Давайте временно забудем о монадах вообще и подумаем об одной конкретной, всем хорошо знакомой, монаде IO. Если заменить в перечисленных ранее функциях «m» на «IO», получим:

( >>= ) :: IO a -> ( a -> IO b ) -> IO b
( >> ) :: IO a -> IO b -> IO b
return :: a -> IO a
fail :: String -> IO a

Вспомним тип функции putStrLn:

ghci> :t putStrLn
putStrLn :: String -> IO ()
ghci> :t putStrLn «hello»
putStrLn «hello» :: IO ()

Смотрите-ка! Функция putStrLn , примененная к строке, имеет тип IO ( ) , прямо как аргументы функции ( >> ) , если заменить a или b на конкретный тип ( ) . Давайте попробуем вызвать ( >> ) и посмотрим, что будет:

ghci> putStrLn «hello» >> putStrLn «world»
hello
world
ghci> :t putStrLn «hello» >> putStrLn «world»
putStrLn «hello» >> putStrLn «world» :: IO ()

Как интересно! Сначала была выведена первая строка, а потом вторая. При этом тип всего выражения оказался IO ( ) , что позволяет снова передать его в качестве аргумента функции ( >> ) :

ghci> putStrLn «hello» >> putStrLn «world» >> putStrLn «of monads»
hello
world
of monads

Получается, ( >> ) позволяет создавать что-то вроде цепочек последовательно выполняемых команд. Есть, правда, одна проблема. Что, если я хочу передать второй функции в цепочке значение, возвращенное первой функцией? Например, сначала получить от пользователя строку с помощью getLine , а затем вывести эту строку с помощью putStrLn . Как раз для этого и нужна функция ( >>= ) . Давайте посмотрим на типы:

getLine :: IO String
putStrLn :: String -> IO ( )
( >>= ) :: IO a -> ( a -> IO b ) -> IO b

Получается, функцию getLine можно связать с putStrLn при помощи функции ( >>= ) , при этом a будет типом String , а b будет ( ) :

ghci> :t getLine >>= putStrLn
getLine >>= putStrLn :: IO ()
ghci> getLine >>= putStrLn
Hello
Hello
ghci> getLine >>= (\s -> putStrLn $ «Hello, » ++ s)
Alex
Hello, Alex

Очень, очень хорошо! А что, если у нас есть чистая функция, возвращающая строку, и мы хотим вывести ее при помощи putStrLn? Мы не можем просто поместить функцию в цепочку, потому что после применения к своим аргументам она будет иметь тип String, а нам нужен IO String. Вот для этого и нужна функция return, которая «оборачивает» произвольный тип в монаду:

ghci> let f x y = x ++ «, » ++ y ++ «!»
ghci> f «Hello» «World»
«Hello, World!»
ghci> return (f «Hello» «World») >>= putStrLn
Hello, World!

Наконец, функция fail нужна для обработки исключительных ситуаций. В контексте монады IO она бросает исключение IOError. Хотя, в зависимости от конкретной монады, она может делать и что-то более осмысленное.

do-нотация

Все это замечательно, но при работе с монадой IO мы же просто пишем:

main :: IO ( )
main = do
putStrLn «What’s your name?»
name putStrLn $ «Hello, » ++ name ++ «!»

Никаких стрелочек! Как же так? В действительности, приведенный выше код полностью аналогичен следующему:

main :: IO ( )
main =
putStrLn «What’s your name?» >>
getLine >>=
\name -> putStrLn $ «Hello, » ++ name ++ «!»

Другими словами, do-нотация — это просто синтаксический сахар над стрелочками. Можно спокойно писать на Haskell без нее, просто код будет чуть менее понятен и придется вводить чуть больше символов.

Кстати, при работе в ghci мы на самом деле находимся внутри монады и используем do-нотацию.

Монадные законы

Когда вы работаете с монадами, предполагается, что выполняются следующие правила:

return a >>= k = k a
m >>= return = m
m >>= ( \x -> k x >>= h ) = ( m >>= k ) >>= h

Компилятор не может проверить выполнение этих законов на этапе компиляции, поэтому ответственность за их соблюдение при объявлении новых монад ложиться на программиста. Если внимательно присмотреться, первые два правила напоминают свойство существования нейтрального элемента, а последнее — это что-то вроде ассоциативности. Давайте проверим на примерах, что эти правила выполняются для монады IO.

ghci> let k = (\x -> return $ x * x + 1) :: Int -> IO Int
ghci> let a = 2 :: Int
ghci> return a >>= k
5
ghci> k a
5

ghci> let m = return 2 :: IO Int
ghci> m >>= return
2
ghci> m
2
ghci> let h = k
ghci> m >>= (\x -> k x >>= h)
26
ghci> (m >>= k) >>= h
26

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

Монада Maybe

В заметке Пишем простой RESTful сервис с использованием Scotty мы видели такую вот странную функцию:

extractNamePhone :: M . Map String String -> Maybe ( String , String )
extractNamePhone m =
M . lookup «name» m >>=
\name -> M . lookup «phone» m >>=
\phone -> Just ( name , phone )

Давайте разберемся, как это работает. Экземпляр класса Monad для типа Maybe определен следующим образом:

instance Monad Maybe where
( Just x ) >>= k = k x
Nothing >>= _ = Nothing

( Just _ ) >> k = k
Nothing >> _ = Nothing

return = Just
fail _ = Nothing

Обратите внимание на функцию ( >>= ) . Благодаря ей мы можем определить extractNamePhone всего лишь в три строчки кода вместо того, чтобы писать:

extractNamePhone m =
case M . lookup «name» m of
Nothing -> Nothing
Just name ->
case M . lookup «phone» m of
Nothing -> Nothing
Just phone -> Just ( name , phone )

Если бы Maybe не был монадой, а нам нужно было бы извлечь из Map’а десяток значений, пришлось бы написать десяток вложенных case of. Кроме того, что монады в данном случае позволяют писать меньше кипятильно-тарелочного кода, также мы фактически получаем что-то вроде механизма исключений для чистых функций.

Благодаря do-нотации мы можем записать это выражение еще проще. А при помощи аппликативных функторов можно записать его вообще в одну строку. Однако об аппликативных функторах речь пойдет как-нибудь в другой раз.

Монада Either

В модуле Control.Monad.Error объявлен экземпляр класса Monad для типа Either:

ghci> :m + Control.Monad.Error
ghci> let f x = Right x
ghci> Right 1 >>= f :: Either String Int
Right 1
ghci> Left «Error 123» >> Right 1 >>= f
Left «Error 123»
ghci> Left 1.0 >> Right 1 >>= f
Left 1.0

Здесь все работает аналогично Maybe, только вместо того, чтобы в случае неудачи просто возвращать Nothing, мы можем как-то уточнить причину ошибки.

Монада State

Монада State бывает полезна, когда имеется некоторое состояние, которое мы постоянно изменяем. Например, если у нас есть Map, в который мы хотим поместить десять значений, возвращаемых разными функциями, нам придется ввести множество переменных m0, m1, m2, … m9. Благодаря монаде State мы можем создать изменяемое состояние, не потеряв при этом чистоты функций, и избежать тем самым описанной проблемы.

Работает это как-то так:

ghci> :m + Control.Monad.State
ghci> let f = (\x y -> modify (+1) >>= \_ -> get >>= \t -> return $ x ++ y ++ show t) :: String -> String -> State Int String
ghci> evalState (f «aaa» «bbb») 0
«aaabbb1»
ghci> execState (f «aaa» «bbb») 0
1
ghci> runState (f «aaa» «bbb») 0
(«aaabbb1»,1)

Здесь Int — это наше состояние, а String — как бы значение, возвращаемое функцией. Получить текущее состояние можно с помощью функции get, сохранить — при помощи put, а изменить — при помощи modify. Для выполнения функции и получения возвращаемого ею значения используйте evalState. Если же вы хотите получить конечное состояние, воспользуйтесь execState. Если вам нужно как возвращаемое значение, так и конечное состояние, скажите runState.

В do-нотации монада State, конечно, выглядит намного красивее.

Монада Reader

Это своего рода State, доступный только на чтение. Монада Reader удобна в случае, когда у нас есть множество функций, работающих в некотором неизменяемом окружении. Вместо того, чтобы передавать между этими функциями одни и те же параметры, мы можем завернуть их в монаду Reader.

ghci> :m + Control.Monad.Reader
ghci> let f = (\x y -> local (+1) (asks (+1) >>= \t1 -> ask >>= \t2 -> return $ x ++ y ++ show t1 ++ show t2) ) :: String -> String -> Reader Int String
ghci> runReader (f «aaa» «bbb») 0
«aaabbb21»

С помощью функции local мы можем создать скоп с измененным окружением. Это намного удобнее, чем читать окружение и создавать на его основе новое. Функция ask возвращает текущее окружение. Функция asks применяет заданную функцию к текущему окружению и возвращает результат. Ее удобно использовать в сочетании с селекторами.

По понятным причинам функций execReader и evalReader не предусмотрено.

Монада Writer

Если Reader — это State, из которого можно только читать, то Writer — это State, в который можно только писать. Монада Writer часто применяется для логирования и трассировки без потери чистоты функций.

ghci> let f = (\x y -> tell [«111»] >>= \_ -> tell [«222»] >>= \_ -> return $ x ++ y ) :: String -> String -> Writer [String] String
ghci> runWriter (f «aaa» «bbb»)
(«aaabbb»,[«111″,»222»])
ghci> execWriter (f «aaa» «bbb»)
[«111″,»222»]
ghci> runWriter (censor (map (++ «!»)) $ f «aaa» «bbb»)
(«aaabbb»,[«111!»,»222!»])
ghci> runWriter (listen $ f «aaa» «bbb»)
((«aaabbb»,[«111″,»222»]),[«111″,»222»])
ghci> runWriter (listens (filter (/= «111»)) $ f «aaa» «bbb»)
((«aaabbb»,[«222»]),[«111″,»222»])

Функция tell производит запись в лог. Интересно, что лог при этом должен быть моноидом. В рамках данного поста будет достаточно сказать, что списки являются моноидами. Функция censor применяется для модификации записей в логе. Функция listen превращает Writer, который возвращает a и пишет w, во Writer, который возвращает (a, w) и пишет w. Функция listens позволяет делать с логом что угодно. Мы можем отфильтровать записи в нем, добавить новые, привести их к другому типу или сделать все это одновременно.

Монада [] (список)

Список тоже являются монадой. Вот классический пример:

— почему при игре в кости выгодно ставить на семь

combinations :: Int -> [ ( Int , Int ) ]
combinations n = do
a b if a + b == n then return ( a , b ) else [ ]

solve :: [ ( Int , Int ) ]
solve = do
n return ( n , length $ combinations n )

main = do
putStrLn $ show solve

Вызываем функцию main:

ghci> main
[(2,1),(3,2),(4,3),(5,4),(6,5),(7,6),(8,5),(9,4),(10,3),(11,2),(12,1)]

Можно сказать, что это другой способ записи генераторов списков.

Некоторые функции для работы с монадами

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

(= <<) :: Monad m =>(a -> m b) -> m a -> m b
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
( <=<) :: Monad m =>(b -> m c) -> (a -> m b) -> a -> m c
mapM :: Monad m => (a -> m b) -> [a] -> m [b]
mapM_ :: Monad m => (a -> m b) -> [a] -> m ()
forM :: Monad m => [a] -> (a -> m b) -> m [b]
forM_ :: Monad m => [a] -> (a -> m b) -> m ()
foldM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a
foldM_ :: Monad m => (a -> b -> m a) -> a -> [b] -> m ()
filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]
zipWithM :: Monad m => (a -> b -> m c) -> [a] -> [b] -> m [c]
zipWithM_ :: Monad m => (a -> b -> m c) -> [a] -> [b] -> m ()
liftM :: Monad m => (a1 -> r) -> m a1 -> m r
liftM2 :: Monad m => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
replicateM :: Monad m => Int -> m a -> m [a]
replicateM_ :: Monad m => Int -> m a -> m ()
sequence :: Monad m => [m a] -> m [a]
sequence_ :: Monad m => [m a] -> m ()
when :: Monad m => Bool -> m () -> m ()
unless :: Monad m => Bool -> m () -> m ()
forever :: Monad m => m a -> m b
join :: Monad m => m (m a) -> m a
ap :: Monad m => m (a -> b) -> m a -> m b

Поэкспериментируйте с ними на досуге в ghci с конкретными монадами, например, IO, Maybe и [], чтобы разобраться, как эти функции работают. Если хотите, можете считать это своим домашним заданием.

Заключение

Помимо перечисленных в данной заметке монад есть и другие. Например, уже знакомая нам монада STM, а также Indentity, монада цитирования Q, Error, ST, Cont, Eval, Par, ActionM и многие другие. В языке Scala много, так сказать, завуалированных монад, среди которых особый интерес представляет Future. Еще в Haskell есть моноиды, MonadPlus, функторы, аппликативные функторы, monad trasformer’ы и другие интересные вещи. Но эти вопросы выходят за рамки поста.

В качестве источников дополнительной информации я бы советовал:

• Две главы в «Learn You a Haskell for Great Good» — раз и два;
• Еще две главы из «Real World Haskell» — эту и эту;
• «Еще одно руководство по монадам», оригинал на английском и перевод на русский первых четырех частей из цикла;
• Хороший туториал по монадам в Haskell Wiki;

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

Дополнение: Вот отличный пример для медитации:

ghci> liftM3 (,,) (+1) (> 0) show 23
(24,True,»23″)

Попробуйте посмотреть на типы в REPL и понять, как это работает.

Вы можете прислать свой комментарий мне на почту, или воспользоваться комментариями в Telegram-группе.

Введение

Как узнать, что человек понял, что такое монады? Он сам вам об этом расскажет в первые 5 минут общения и обязательно попробует объяснить. А ещё напишет об этом текст и по возможности где-нибудь его опубликует, чтобы все остальные тоже поняли, что такое монады.

Среди функциональных программистов, особенно на Haskell, монады стали чем-то вроде локального мема. Их часто пытаются объяснить, отталкиваясь от частных случаев и сразу приводя примеры использования. Из-за этого слушатель может не уловить основную суть понятия, а монады так и останутся чёрной магией, ну или просто средством костылизации побочных эффектов в чисто функциональных языках.

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

Моё изложение во многом основывается на книге Бартоша Милевски «Теория категорий для программистов», которая создавалась как серия блогпостов, доступна в PDF, а недавно вышла в бумаге.

Примеры приводятся на Haskell, предполагается, что читатель знаком с синтаксисом и основными понятиями языка. В упомянутой книге есть примеры и на С++, можете сравнить чистоту и понятность кода.

Категории

Определение

Категории сами по себе — очень простые конструкции. Категория — это набор объектов и морфизмов между ними. Морфизмы можно рассматривать как однонаправленные стрелки, соединяющие объекты. В общем случае про сущность самих объектов ничего не известно. Теория категорий работает не с объектами, а с морфизмами, точнее — с их композицией.

Используется следующая нотация:

• Ob_C — объекты категории C;
• Hom_C(A, B) — морфизмы из A в B;
• g ∘ f — композиция морфизмов f и g.

В определении категории на морфизмы накладываются дополнительные ограничения:

1. Для пары морфизмов f и g, если f — морфизм из A в B (f ∈ Hom(A, B)), g — морфизм из B в C (g ∈ Hom(B, C)), то существует их композиция g ∘ f — морфизм из A в C (g ∘ f ∈ Hom(A, C)).
2. Для каждого объекта задан тождественный морфизм id_A ∈ Hom(A, A).

Существуют два важных свойства, которым должна удовлетворять любая категория (аксиомы теории категорий):

1. Ассоциативность композиции: h ∘ (g ∘ f) = (h ∘ g) ∘ f;
2. Композиция с тождественным морфизмом: если f ∈ Hom(A, B), то f ∘ id_A = id_B ∘ f = f.

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

Для любой категории можно определить двойственную категорию (обозначается C op , в которой морфизмы получены разворотом стрелок исходной категории, а объекты — те же самые. Это позволяет формулировать двойственные утверждения и теоремы, истинность которых не меняется при обращении стрелок.

Объекты и морфизмы не обязательно образуют множества (в классическом смысле из теории множеств), поэтому в общем случае используется словосочетание «класс объектов». Категории, в которых классы объектов и морфизмов всё-таки являются множествами, называются малыми категориями. Далее мы будем работать только с ними.

Типы и функции

Рассмотрим категорию, в которой объектами являются типы языка Haskell, а морфизмами — функции. Например, типы Int и Bool — это примеры объектов, а функция типа Int -> Bool — морфизм.

Тождественным морфизмом является функция id , возвращающая свой аргумент:

id :: a -> a id x = x

Композиция морфизмов — это композиция функций, причём синтаксис этой операции на Haskell почти идентичен математической нотации:

f :: a -> b g :: b -> c g . f :: a -> c (g . f) x = g (f x)

Категория, в которой объекты представляют собой множества, а морфизмы — отображения, называется Set. Типы также можно рассматривать как множества допустимых значений, а функции — как отображения множеств, но с одной оговоркой: вычисления могут не завершиться. Для обозначения такой ситуации вводится специальный тип bottom, обозначаемый _|_ . Считается, что любая функция либо возвращает значение типа, указанного в сигнатуре, либо значение типа bottom. Категория типов языка Haskell, в которой учитывается эта особенность, называется Hask. Для упрощения изложения мы будем работать с ней так же, как с категорией Set. Любопытно, что в этой категории морфизмы между двумя объектами в свою очередь образуют множество, которое является объектом в этой же категории: Hom_C(A, B) ∈ C. Действительно, функциональный тип a -> b — это тоже тип языка Haskell.

Рассмотрим несколько примеров типов с точки зрения теории категорий.

Пустому множеству соответствует тип Void , у которого нет значений (такой тип называется ненаселённым). Существует даже полиморфная функция absurd , которую можно определить, но невозможно вызвать, поскольку для вызова ей нужно передать значение типа Void , а таких значений нет:

absurd :: Void -> a

Множеству из одного элемента соответствует тип Unit , единственное значение которого — пустой кортеж, также обозначаемый () . Полиморфная функция unit возвращает это значение, принимая на вход любой другой тип:

unit :: a -> Unit unit _ = ()

Множество из двух элементов — логический тип Bool :

data Bool = True | False

Построим категорию, объектами в которой являются типы Void , Unit и Bool .

Из Void выходят только морфизмы, соответствующие функции absurd , один в Bool , один в Unit . В обратную сторону морфизмов нет, поскольку мы никак не можем получить значения ненаселённого типа Void , просто потому что их не существует, а значит и не можем определить тело этой функции.

Функция типа Bool -> Unit может быть только одна, unit , поскольку независимо от входного значения мы можем вернуть только пустой кортеж. А вот для реализации функции типа Unit -> Bool возможны варианты. Такая функция в любом случае будет принимать значение () , но вернуть можно либо True , либо False . Таким образом, получили два морфизма из Unit в Bool :

true, false :: a -> Bool true _ = True false _ = False

Морфизмы из Bool в Bool — это булевы функции от одного аргумента, которых 4 штуки (в общем случае количество булевых функций от n аргументов — 2 2 n ): id , true и false , которые мы уже определяли выше, а также функция not :

not :: Bool -> Bool not True = False not False = True

Добавив тождественные морфизмы, получим следующую категорию:

В дальнейшем изложении будем использовать Haskell-подобную нотацию сигнатуры типов для обозначения морфизмов.

Функторы

Функтор — это отображение категорий. Для двух категорий, C и D, функтор F осуществляет два вида преобразований. Во-первых, функтор преобразует объекты из категории C в объекты из категории D. Если a — объект из категории C, то F a — соответствующий ему объект из категории D, полученный в результате применения функтора. Во-вторых, функтор действует на морфизмы: морфизм f :: a -> b в категории C преобразуется в морфизм F f :: F a -> F b в категории D.

Кроме того, должны выполняться «законы сохранения» композиции и тождественного морфизма:

1. Если h = g ∘ f, то F h = F g ∘ F f.
2. Если id_a — тождественный морфизм для объекта a, то F id_a = id_{F a} — тождественный морфизм для объекта F a.

Таким образом, функтор не «ломает» структуру категории: то, что было связано морфизмом в исходной категории, будет связано и в результирующей. Это верно и для крайних случаев, например, когда результирующая категория состоит из одного объекта и одного (тождественного) морфизма. Тогда все морфизмы исходной категории отобразятся в тождественный морфизм для этого объекта, но упомянутые выше законы нарушены не будут.

Функторы можно комбинировать аналогично функциям. Для двух функторов, F :: C -> D и G :: D -> E можно определить композицию G . F :: C -> E . Кроме того, для каждой категории несложно построить тождественный функтор, который будет переводить как объекты, так и морфизмы, в самих себя. Обозначим их Id_C, Id_D и Id_E. Функторы, действующие из категории в неё саму, называются эндофункторы.

Посмотрим на эту картинку сильно издалека, так, чтобы сами категории превратились в точки-объекты, а функторы — в стрелки между ними (морфизмы). Получим категорию малых категорий, которая называется Cat (название периодически порождает сложные мемы с кошками).

Вернёмся к категории типов языка Haskell и будем работать с эндофункторами в этой категории. Они преобразуют типы в другие типы и, кроме того, каким-то образом преобразуют функции, работающие с этими типами.

Конструктор типа Maybe является примером такого функтора, он преобразует тип a в тип Maybe a (сам по себе Maybe не является типом!):

data Maybe a = Nothing | Just a

Для преобразования морфизмов, необходимо уметь получать из функции f :: a -> b функцию F f :: Maybe a -> Maybe b . Это действие можно записать в виде функции высшего порядка fmap . Обратите внимание, что тип этой функции как раз наглядно описывает преобразование морфизмов (из одной функции получаем другую):

-- f F f -- /------\ /------------------\ fmap :: (a -> b) -> (Maybe a -> Maybe b) fmap _ Nothing = Nothing fmap f (Just x) = Just (f x)

Конечно, Maybe — не единственный функтор. Существует целый класс типов, который так и называется, Functor . Единственным методом этого класса является функция fmap , показывающая, как преобразуются морфизмы (а преобразование объектов — это применение конструктора типа к конкретным типам):

class Functor f where fmap :: (a -> b) -> f a -> f b

В более прикладном смысле функторы — это контейнеры, которые хранят значения других типов, а функция fmap позволяет преобразовывать объекты внутри этих контейнеров. Если опустить скобки вокруг f a -> f b , как это сделано в определении выше, то такая сигнатура лучше подойдёт для описания функторов как контейнеров.

Монады

Все функции, которые были рассмотрены до этого, были чистыми, т.е. предполагалось, что у них нет побочных эффектов. Это функции в математическом смысле: результат чистой функции зависит только от значения её аргумента, он не меняется из-за места или времени вызова.

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

В качестве примера возьмём функции для преобразования строк: upCase , переводящую все символы строки в верхний регистр, и toWords , разбивающую строки на слова. Пока что их реализация всего лишь использует встроенные функции toUpper и words :

upCase :: String -> String upCase = map toUpper toWords :: String -> [String] toWords = words

Типы функций позволяют составить их композицию:

processString :: String -> [String] processString = toWords . upCase

Чтобы не отвлекаться на сложности реализации, в качестве представления лога возьмём просто строку. Мы хотим, чтобы после применения функции processString в логе содержалась запись «upCase toWords».

Запись в лог — побочное действие функций, мало относящееся к их основному функционалу. Хотелось бы во-первых, добавить информацию на уровне типов о том, что будет выполняться логгирование, и во-вторых, минимизировать дополнительные действия, которые придётся проделать сторонним разработчикам для работы с этими функциями.

Создадим новый тип данных, который будет помимо самих значений типа a хранить ещё и строку, в которую каждая вызванная функция будет добавлять своё имя.

newtype Writer a = Writer (a, String)

Заметим, что Writer — это функтор, мы легко можем описать для него функцию fmap :

instance Functor Writer where fmap f (Writer (x, s)) = Writer (f x, s)

Преобразуем функции upCase и toWords и сделаем так, чтобы они возвращали значение, «завёрнутое» в тип Writer :

upCase :: String -> Writer String upCase s = Writer (map toUpper s, "upCase ") toWords :: String -> Writer [String] toWords s = Writer (words s, "toWords ")

Теперь мы больше не можем записать композицию этих функций так же, как раньше, из-за несоответствия типов. Определим специальную функцию для композиции, которая сначала получает значение типа b и первую строку, передаёт это значение второй функции, получает значение типа c и вторую строку и в качестве финального результата возвращает значение типа c и конкатенацию строк, полученных при вычислении:

compose :: (a -> Writer b) -> (b -> Writer c) -> (a -> Writer c) compose f g = \x -> let Writer (y, s1) = f x Writer (z, s2) = g y in Writer (z, s1 ++ s2)

Реализация функции processString принимает вид:

processString :: String -> [String] processString = compose upCase toWords

Вернёмся к понятиям теории категорий. Мы можем заменить все функции (морфизмы) типа a -> b на a -> Writer b и получить новую категорию, в которой такие функции являются новыми морфизмами между a и b . Осталось только определить тождественный морфизм, т.е. функцию типа a -> Writer a :

writerId :: a -> Writer a writerId x = Writer (x, "")

Таким образом, мы получили новую категорию, основанную на Hask. В этой категории объектами являются те же типы, но морфизмом между типами a и b являются функции типа не a -> b , а a -> m b , т.е. возвращаемый тип «завёрнут» в какой-то другой фиксированный конструктор типа m . Такие функции мы будем называть обогащёнными (embellished). Композиция морфизмов и тождественный морфизм зависят от m , реализация для Writer — лишь частный случай.

Обобщим сказанное выше для любой категории C и эндофунктора m. Построим категорию K, состоящую из тех же объектов, что и категория C, т.е. Ob_K = Ob_C. Морфизм a -> b в категории K соответствует морфизму a -> m b в исходной категории C: Hom_K(a, b) = Hom_C(a, m b). Для типов и функций это будет означать, что функции, работающие с типами в категории K — обогащённые функции в категории C.

Для того, чтобы получить настоящую категорию с такими морфизмами, необходимо определить ассоциативную композицию морфизмов и тождественный морфизм для каждого объекта таким образом, чтобы соблюдались аксиомы теории категорий. Тогда полученная категория называется категорией Клейсли, а функтор m — монадой. На Haskell это определение выглядит так (везде далее используются типы из категории Hask):

class Monad m where -- композиция морфизмов категории Клейсли (>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c) -- тождественный морфизм return :: a -> m a

Тип оператора >=> , который иногда называют «fish», показывает суть монад: это способ композиции обогащённых функций. Побочные эффекты, работа с состоянием, исключения — всё это лишь частные случаи, они не определяют, что такое монады, но являются хорошими примерами их использования. Writer — тоже монада, определённая нами функция compose — это композиция морфизмов >=> , а функция writerId — тождественный морфизм return .

Начнём реализовывать оператор >=> в общем виде. Результатом композиции двух обогащённых функций должна быть тоже функция, поэтому в реализации используем лямбда-выражение. Аргумент этого выражения имеет тип a , и у нас есть функция f , которую к нему можно применить, а дальше работать с результатом её вычисления во вспомогательной функции, которую назовём bind :

f >=> g = \a -> let mb = f a in (bind mb g) where bind :: m b -> (b -> m c) -> m c

Функция bind получает значение типа b «в контейнере» m и функцию, которая принимает на вход аргумент типа b и возвращает m c . Тип результата у неё совпадает с типом результата >=> . Мы получили следующую сигнатуру типов: m b -> (b -> m c) -> m c . Эту функцию необходимо реализовать для каждой монады, чтобы описать способ композиции обогащённых функций. Мы подошли к «классическому» определению монад в Haskell в виде класса типов с методами >>= , или bind , и return :

class Monad m where (>>=) :: m a -> (a -> m b) -> m b return :: a -> m a

Теперь попробуем продолжить реализацию в общем виде, для чего каким-то образом нужно применить функцию типа b -> m c к значению типа b , но у нас есть только значение типа m b . Вспомним, что изначально мы работаем с эндофунктором m , поэтому можем воспользоваться функцией fmap , которая в данном случае будет типа (a -> m b) -> m a -> m (m b) . Для завершения реализации >>= необходимо преобразовать значение типа m (m b) к m b , «схлопнув» контейнеры, но это уже невозможно сделать в общем виде. Выразим это преобразование как функцию join :

ma >>= g = join (fmap g ma) where join :: m (m a) -> m a

Например, для типа Writer реализация будет следующей:

join :: Writer (Writer a) -> Writer a join (Writer ((Writer (x, s2)), s1)) = Writer (x, s1 ++ s2)

Мы пришли к третьему определению класса Monad :

class Functor m => Monad m where join :: m (m a) -> m a return :: a -> m a

Здесь присутствует явное требование на то, чтобы m был функтором. Это ограничение не было нужно для предыдущих определений, поскольку функция fmap реализуется через >>= :

fmap :: (a -> b) -> m a -> m b fmap f ma = ma >>= (\a -> return (f a))

Практическое применение монад

Приведём примеры практического применения монад для решения задач, которые традиционно решаются с использованием «нечистых» функций и побочных эффектов.

Недетерминированные вычисления

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

Композиция обогащённых функций должна иметь тип (a -> [b]) -> (b -> [c]) -> (a -> [c]) . Достаточно опытному программисту реализация может быть понятна из одной этой сигнатуры:

(>=>) :: (a -> [b]) -> (b -> [c]) -> (a -> [c]) f >=> g = \x -> concat (map g (f x))

Типы практически не оставляют возможности сделать неверный шаг. Получив значение типа a , единственное, что можно с ним сделать — это применить функцию f и получить список [b] . Далее всё, что мы умеем делать со значениями типа b — применить функцию g к каждому из них в списке и получить в результате список списков: map g (f x) :: [[c]] . Чтобы получить нужный результат, конкатенируем их.

Тогда оператор >>= можно записать так:

(>>=) :: [a] -> (a -> [b]) -> [b] xs >>= f = concat (map f xs)

Осталось реализовать функцию return :: a -> [a] . Здесь реализация снова выводится из типа:

return :: a -> [a] return x = [x]

Резюмируем эти реализации в классическом определении класса Monad :

instance Monad [] where xs >>= f = concat (map f xs) return x = [x]

Конечно, список как результат функции не обязательно обозначает недетерминированность вычислений. Хорошим примером, когда это действительно так, является реализация искусственного интеллекта для игр. Список может представлять возможные результаты хода игрока, ответных ходов может быть тоже несколько — всё время приходится работать со списками, списками списков и т.д.

Исключения

Простейшая реализация обработки исключений в чистых функциях состоит в добавлении в тип возвращаемого значения специального варианта, обозначающего, что что-то пошло не так.

Для этого подойдёт, к примеру, уже рассмотренный функтор Maybe . При штатной работе функции будут возвращать значение в конструкторе Just , при возникновении ошибки — значение Nothing . Композиция таких обогащённых функций должна работать таким образом, чтобы каждая следующая функция не вызывалась, если ошибка уже произошла в предыдущем вызове:

(>=>) :: (a -> Maybe b) -> (b -> Maybe c) -> (a -> Maybe c) f >=> g = \x -> case f x of Just y -> g y Nothing -> Nothing

Определение методов класса Monad для Maybe :

instance Monad Maybe where (Just x) >>= f = f x Nothing >>= f = Nothing return x = Just x

Недостаток этого подхода состоит в том, что исключение никак не конкретизируется. Мы просто знаем, что в какой-то из функций, участвовавшей в композиции, произошла какая-то ошибка. С этой точки зрения удобнее будет использовать тип Either String a , который представляет собой альтернативу двух значений: либо это строка с описанием ошибки, либо результат штатной работы функции. В общем виде тип определяется так:

data Either a b = Left a | Right b

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

type WithException a = Either String a

Композиция функций описывается аналогично случаю с использованием Maybe :

(>=>) :: (a -> WithException b) -> (b -> WithException c) -> (a -> WithException c) f >=> g = \x -> case f x of Right y -> g y err -> err

Определение экземпляра класса Monad уже не должно вызывать трудностей:

instance Monad WithException where (Right x) >>= f = f x err >>= f = err return x = Right x

Состояния

Пример с логгером, с которого мы начинали, реализует работу с write-only состоянием, но хотелось бы использовать состояние и для чтения. Модифицируем тип функции a -> b так, чтобы получить обогащённую функцию, работающую с состоянием. Добавим в тип функции один аргумент, обозначающий текущее состояние, а также изменим тип возвращаемого значения (теперь это пара, состоящая из самого значения и изменённого состояния):

a -> s -> (b, s)

Объявим синоним типа для работы с состоянием:

newtype State s a = State (s -> (a, s))

Фиксируем тип состояния s и покажем, что State s является функтором. Нам понадобится вспомогательная функция runState :

runState :: State s a -> s -> (a, s) runState (State f) s = f s

Реализация класса Functor :

instance Functor (State s) where fmap f state = State st' where st' prevState = let (a, newState) = runState state prevState in (f a, newState)

Таким образом, обогащённые функции из a в b , в которых ведётся работа с состоянием, имеют тип a -> State s b , причём State s — функтор. Попробуем превратить его в монаду, реализовав их композицию:

(>=>) :: (a -> State s b) -> (b -> State s c) -> (a -> State s c) f >=> g = \x -> State (\s -> let (y, s') = runState (f x) s in runState (g y) s')

Отсюда получим реализацию класса Monad . Тождественный морфизм, функция return , ничего не делает с состоянием, а просто добавляет свой аргумент в пару-результат:

instance Monad (State s) where stateA >>= f = State (\s -> let (a, s') = runState stateA s in runState (f a) s') return a = State (\s -> (a, s))

Функция для чтения состояния должна всегда возвращать текущее состояния, ей не нужны аргументы. Можно сказать, что это морфизм из Unit в s в категории Клейсли, поэтому функция должна иметь тип Unit -> State s s :

get :: Unit -> State s s get _ = State (\s -> (s, s))

Конечно, в реализации Unit можно опустить. Здесь он добавлен для того, чтобы показать эту операцию с точки зрения теории категорий.

Запись состояния, наоборот, принимает новое значение состояния и записывает его. Нам важен только побочный эффект, но не возвращаемое значение, поэтому соответствующий морфизм идёт в обратную сторону, из s в Unit , а функция имеет тип s -> State s Unit :

put :: s -> State s Unit put s = State (\_ -> ((), s))

Реализация работы с состоянием вышла чуть более сложной, чем предыдущие примеры, но на её основе можно создать формальную модель для работы с вводом/выводом. В ней предполагается, что «окружающий мир» реализован в виде некоторого типа RealWorld , о котором неизвестно никаких подробностей. При общении с внешним миром программа получает на вход объект типа RealWorld и производит какие-то действия, в результате которых получает нужный ей результат и изменяет внешний мир (например, выводит строку на экран или читает символ из потока ввода). Эту абстрактную концепцию можно реализовать с помощью состояния:

type IO a = State RealWorld a

Тип IO — один из первых, о котором узнаёт начинающий пользователь Haskell, и наверняка сразу встречает пугающее слово «монада». Такой упрощённый взгляд на этот тип как на состояние для работы с внешним миром может помочь понять, почему это так. Кончено, это описание очень поверхностно, но полноценный рассказ о том, как на самом деле реализован ввод-вывод, зависит от компилятора и выходит далеко за рамки статьи.

• haskell
• теория категорий
• теория категорий для программистов
• монады
• математика
• функциональное программирование

• Программирование
• Haskell
• Математика
• Функциональное программирование

Монады за 15 минут

На конференции YOW! 2013 один из разработчиков языка Haskell, проф. Филип Вадлер, показал, как монады позволяют чистым функциональным языкам осуществлять императивные по сути операции, такие, как ввод-вывод и обработку исключений. Неудивительно, что интерес аудитории к этой теме породил взрывной рост публикаций о монадах в Интернет. К сожалению, бо́льшая часть этих публикаций использует примеры, написанные на функциональных языках, подразумевая, что о монадах хотят узнать новички в функциональном программировании. Но монады не специфичны для Haskell или функциональных языков, и вполне могут быть проиллюстрированы примерами на императивных языках программирования. Это и является целью данного руководства.

Чем это руководство отличается от остальных? Мы попытаемся не более чем за 15 минут «открыть» монады, используя лишь интуицию и несколько элементарных примеров кода на Python. Мы поэтому не станем теоретизировать и углубляться в философию, рассуждая о буррито, космических скафандрах, письменных столах и эндофункторах.

Мотивационные примеры

Мы рассмотрим три проблемы, относящиеся к композиции функций. Мы решим их двумя способами: обычным императивным и при помощи монад. Затем мы сравним разные подходы.

1. Логгирование

Допустим, у нас есть три унарные функции: f1 , f2 и f3 , принимающие число и возвращающие его увеличенным на 1, 2 и 3 соответственно. Также каждая функция генерирует сообщение, представляющее собой отчёт о выполненной операции.

def f1(x): return (x + 1, str(x) + "+1") def f2(x): return (x + 2, str(x) + "+2") def f3(x): return (x + 3, str(x) + "+3")

Мы хотели бы объединить их в цепочку для обработки параметра x , иначе говоря, мы хотели бы вычислить x+1+2+3 . Кроме того, нам нужно получить человекочитаемое объяснение того, что было сделано каждой функцией.

Можно добиться нужного нам результата следующим способом:

log = "Ops:" res, log1 = f1(x) log += log1 + ";" res, log2 = f2(res) log += log2 + ";" res, log3 = f3(res) log += log3 + ";" print(res, log)

Это решение неидеально, так как состоит из большого количества однообразного связующего кода. Если мы захотим добавить к нашей цепочке новую функцию, мы вынуждены будем повторить этот связующий код. Кроме того, манипуляции с переменными res и log ухудшают читаемость кода, мешая следить за основной логикой программы.

В идеале, программа должна выглядеть как простая цепочка функций, вроде f3(f2(f1(x))) . К сожалению, типы данных, возвращаемых f1 и f2 , не соответствуют типам параметров f2 и f3 . Но мы можем добавить в цепочку новые функции:

def unit(x): return (x, "Ops:") def bind(t, f): res = f(t[0]) return (res[0], t[1] + res[1] + ";")

Теперь мы можем решить проблему следующим образом:

print(bind(bind(bind(unit(x), f1), f2), f3))

Следующая диаграмма показывает вычислительный процесс, происходящий при x=0 . Здесь v1 , v2 и v3 − значения, полученные в результате вызовов unit и bind .

Функция unit преобразует входной параметр x в кортеж из числа и строки. Функция bind вызывает функцию, переданную ей в качестве параметра, и накапливает результат в промежуточной переменной t .

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

bind(f4, bind(f3, . ))

И никаких других изменений нам делать не понадобится.

2. Список промежуточных значений

Этот пример мы также начнём с простых унарных функций.

def f1(x): return x + 1 def f2(x): return x + 2 def f3(x): return x + 3

Как и в предыдущем примере, нам нужно скомпоновать эти функции, чтобы вычислить x+1+2+3 . Также нам нужно получить список всех значений, полученных в результате работы наших функций, то есть x , x+1 , x+1+2 и x+1+2+3 .

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

Решим задачу «в лоб»:

lst = [x] res = f1(x) lst.append(res) res = f2(res) lst.append(res) res = f3(res) lst.append(res) print(res, lst)

К сожалению, это решение также содержит много связующего кода. И если мы решим добавить f4 , нам опять придётся повторять этот код, чтобы получить верный список промежуточных значений.

Поэтому добавим две дополнительные функции, как и в предыдущем примере:

def unit(x): return (x, [x]) def bind(t, f): res = f(t[0]) return (res, t[1] + [res])

Теперь мы перепишем программу в виде цепочки вызовов:

print(bind(bind(bind(unit(x), f1), f2), f3))

Следующая диаграмма показывает вычислительный процесс, происходящий при x=0 . Снова v1 , v2 и v3 обозначают значения, полученные в результате вызовов unit и bind .

3. Пустые значения

Попробуем привести более интересный пример, на этот раз с классами и объектами. Допустим, у нас есть класс Employee с двумя методами:

class Employee: def get_boss(self): # Return the employee's boss def get_wage(self): # Compute the wage

Каждый объект класса Employee имеет руководителя (другой объект класса Employee ) и зарплату, доступ к которым осуществляется через соответствующие методы. Оба метода могут также возвращать None (работник не имеет руководителя, зарплата неизвестна).

В этом примере мы создадим программу, которая показывает зарплату руководителя данного работника. Если руководитель не найден, или его зарплата не может быть определена, то программа вернёт None .

В идеале нам нужно написать что-то вроде

print(john.get_boss().get_wage())

Но в таком случае, если какой-то из методов вернёт None , наша программа завершится с ошибкой.

Очевидный способ учесть эту ситуацию может выглядеть так:

result = None if john is not None and john.get_boss() is not None and john.get_boss().get_wage() is not None: result = john.get_boss().get_wage() print(result)

В этом случае мы допускаем лишние вызовы методов get_boss и get_wage . Если эти методы достаточно тяжелы (например, обращаются к базе данных), наше решение не годится. Поэтому изменим его:

result = None if john is not None: boss = john.get_boss() if boss is not None: wage = boss.get_wage() if wage is not None: result = wage print(result)

Этот код оптимален в плане вычислений, но плохо читается за счёт трёх вложенных if . Поэтому попробуем использовать тот же трюк, что и в предыдущих примерах. Определим две функции:

def unit(e): return e def bind(e, f): return None if e is None else f(e)

И теперь мы можем скомпоновать всё решение в одну строку.

print(bind(bind(unit(john), Employee.get_boss), Employee.get_wage))

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

Обратите внимание также на то, что в Python мы можем использовать методы как функции, что позволило нам написать Employee.get_boss(john) вместо john.get_boss() .

Следующая диаграмма показывает процесс вычислений в том случае, когда у Джона нет руководителя, то есть john.get_boss() возвращает None .

Выводы

Допустим, мы хотим объединить однотипные функции f1 , f2 , … , fn . Если их входные параметры совпадают по типу с результатами, мы можем использовать простую цепочку вида fn(… f2(f1(x)) …) . Следующая диаграмма показывает обобщённый процесс вычислений с промежуточными результатами, обозначенными как v1 , v2 , … , vn .

Зачастую этот подход неприменим. Типы входных значений и результатов функций могут различаться, как в первом примере. Либо же функции могут быть компонуемы, но мы хотим вставить дополнительную логику между вызовами, как в примерах 2 и 3 мы вставляли аггрегацию промежуточных значений и проверку на пустое значение соответственно.

1. Императивное решение

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

Перед вызовом f1 мы выполняли некоторую инициализацию. В первом примере мы инициализировали переменную для хранения общего лога, во втором − для списка промежуточных значений. После этого мы перемежали вызовы функций неким связующим кодом: вычисляли агрегатные значения, проверяли результат на None .

2. Монады

Как мы видели на примерах, императивные решения всегда страдали многословностью, повторениями и запутанной логикой. Чтобы получить более элегантный код, мы использовали некий шаблон проектирования, согласно которому мы создавали две функции: unit и bind . Этот шаблон и называется монадой. Функция bind содержит связующий код, в то время, как unit осуществляет инициализацию. Это позволяет упростить итоговое решение до одной строки:

bind(bind( . bind(bind(unit(x), f1), f2) . fn-1), fn)

Процесс вычисления можно представить диаграммой:

Вызов unit(x) генерирует начальное значение v1 . Затем bind(v1, f1) генерирует новое промежуточное значение v2 , которое используется в следующем вызове bind(v2, f2) . Этот процесс продолжается, пока не будет получен итоговый результат. Определяя различные unit и bind в рамках этого шаблона, мы можем объединять различные функции в одну цепочку вычислений. Библиотеки монад (например, PyMonad или OSlash, − прим. перев.) обычно содержат готовые к употреблению монады (пары функций unit и bind ) для реализации определённых композиций функций.

Чтобы собрать функции в цепочку, значения, возвращаемые unit и bind , должны быть того же типа, что и входные параметры bind . Этот тип называется монадическим. В терминах вышеприведённой диаграммы, тип переменных v1 , v2 , … , vn должен быть монадическим типом.

Наконец, рассмотрим, как можно улучшить код, написанный с использованием монад. Очевидно, повторяющиеся вызовы bind выглядят неэлегантно. Чтобы избежать этого, определим ещё одну внешнюю функцию:

def pipeline(e, *functions): for f in functions: e = bind(e, f) return e

Теперь вместо

bind(bind(bind(bind(unit(x), f1), f2), f3), f4)

мы можем использовать следующее сокращение:

pipeline(unit(x), f1, f2, f3, f4)

Заключение

Монады − это простой и мощный шаблон проектирования, используемый для композиции функций. В декларативных языках программирования он помогает реализовать такие императивные механизмы, как логгирование или ввод/вывод. В императивных языках
он помогает обобщить и сократить код, связывающий серию вызовов однотипных функций.

Эта статья даёт только поверхностное, интуитивное понимание монад. Вы можете узнать больше, обратившись к следующим источникам:

1. Википедия
2. Monads in Python (with nice syntax!)
3. Monad tutorials timeline

• Python
• Функциональное программирование