8.7. Monads¶
A monad is more of a design pattern than a data structure. That is, there are many data structures that, if you look at them in the right way, turn out to be monads.
The name “monad” comes from the mathematical field of category theory, which studies abstractions of mathematical structures. If you ever take a PhD level class on programming language theory, you will likely encounter that idea in more detail. Here, though, we will omit most of the mathematical theory and concentrate on code.
Monads became popular in the programming world through their use in Haskell, a functional programming language that is even more pure than OCaml—that is, Haskell avoids side effects and imperative features even more than OCaml. But no practical language can do without side effects. After all, printing to the screen is a side effect. So Haskell set out to control the use of side effects through the monad design pattern. Since then, monads have become recognized as useful in other functional programming languages, and are even starting to appear in imperative languages.
Monads are used to model computations. Think of a computation as being like a function, which maps an input to an output, but as also doing “something more.” The something more is an effect that the function has as a result of being computed. For example, the effect might involve printing to the screen. Monads provide an abstraction of effects, and help to make sure that effects happen in a controlled order.
8.7.1. The Monad Signature¶
For our purposes, a monad is a structure that satisfies two properties. First, it must match the following signature:
Second, a monad must obey what are called the monad laws. We will return to those much later, after we have studied the return and bind operations.
Think of a monad as being like a box that contains some value. The value has type ‘a , and the box that contains it is of type ‘a t . We have previously used a similar box metaphor for both options and promises. That was no accident: options and promises are both examples of monads, as we will see in detail, below.
Return. The return operation metaphorically puts a value into a box. You can see that in its type: the input is of type ‘a , and the output is of type ‘a t .
In terms of computations, return is intended to have some kind of trivial effect. For example, if the monad represents computations whose side effect is printing to the screen, the trivial effect would be to not print anything.
Bind. The bind operation metaphorically takes as input:
a boxed value, which has type ‘a t , and
a function that itself takes an unboxed value of type ‘a as input and returns a boxed value of type ‘b t as output.
The bind applies its second argument to the first. That requires taking the ‘a value out of its box, applying the function to it, and returning the result.
In terms of computations, bind is intended to sequence effects one after another. Continuing the running example of printing, sequencing would mean first printing one string, then another, and bind would be making sure that the printing happens in the correct order.
The usual notation for bind is as an infix operator written >>= and still pronounced “bind”. So let’s revise our signature for monads:
All of the above is likely to feel very abstract upon first reading. It will help to see some concrete examples of monads. Once you understand several >>= and return operations, the design pattern itself should make more sense.
So the next few sections look at several different examples of code in which monads can be discovered. Because monads are a design pattern, they aren’t always obvious; it can take some study to tease out where the monad operations are being used.
8.7.2. The Maybe Monad¶
As we’ve seen before, sometimes functions are partial: there is no good output they can produce for some inputs. For example, the function max_list : int list -> int doesn’t necessarily have a good output value to return for the empty list. One possibility is to raise an exception. Another possibility is to change the return type to be int option , and use None to represent the function’s inability to produce an output. In other words, maybe the function produces an output, or maybe it is unable to do so hence returns None .
As another example, consider the built-in OCaml integer division function ( / ) : int -> int -> int . If its second argument is zero, it raises an exception. Another possibility, though, would be to change its type to be ( / ) : int -> int -> int option , and return None whenever the divisor is zero.
Both of those examples involved changing the output type of a partial function to be an option, thus making the function total. That’s a nice way to program, until you start trying to combine many functions together. For example, because all the integer operations—addition, subtraction, division, multiplication, negation, etc.—expect an int (or two) as input, you can form large expressions out of them. But as soon as you change the output type of division to be an option, you lose that compositionality.
Here’s some code to make that idea concrete:
The problem is that we can’t add an int to an int option : the addition operator expects its second input to be of type int , but the new division operator returns a value of type int option .
One possibility would be to re-code all the existing operators to accept int option as input. For example,
But that’s a tremendous amount of code duplication. We ought to apply the Abstraction Principle and deduplicate. Three of the four operators can be handled by abstracting a function that just does some pattern matching to propagate None :
Unfortunately, division is harder to deduplicate. We can’t just pass Stdlib.( / ) to propagate_none , because neither of those functions will check to see whether the divisor is zero. It would be nice if we could pass our function div : int -> int -> int option to propagate_none , but the return type of div makes that impossible.
So, let’s rewrite propagate_none to accept an operator of the same type as div , which makes it easy to implement division:
Implementing the other three operations requires a little more work, because their return type is int not int option . We need to wrap their return value with Some :
Finally, we could re-implement div to use wrap_output :
Where’s the Monad? The work we just did was to take functions on integers and transform them into functions on values that maybe are integers, but maybe are not—that is, values that are either Some i where i is an integer, or are None . We can think of these “upgraded” functions as computations that may have the effect of producing nothing. They produce metaphorical boxes, and those boxes may be full of something, or contain nothing.
There were two fundamental ideas in the code we just wrote, which correspond to the monad operations of return and bind .
The first (which admittedly seems trivial) was upgrading a value from int to int option by wrapping it with Some . That’s what the body of wrap_output does. We could expose that idea even more clearly by defining the following function:
This function has the trivial effect of putting a value into the metaphorical box.
The second idea was factoring out code to handle all the pattern matching against None . We had to upgrade functions whose inputs were of type int to instead accept inputs of type int option . Here’s that idea expressed as its own function:
The bind function can be understood as doing the core work of upgrading op from a function that accepts an int as input to a function that accepts an int option as input. In fact, we could even write a function that does that upgrading for us using bind :
All those type annotations are intended to help the reader understand the function. Of course, it could be written much more simply as:
Using just the return and >>= functions, we could re-implement the arithmetic operations from above:
Recall, from our discussion of the bind operator in Lwt, that the syntax above should be parsed by your eye as
take x and extract from it the value a ,
then take y and extract from it b ,
then use a and b to construct a return value.
Of course, there’s still a fair amount of duplication going on there. We can de-duplicate by using the same techniques as we did before:
The Maybe Monad. The monad we just discovered goes by several names: the maybe monad (as in, “maybe there’s a value, maybe not”), the error monad (as in, “either there’s a value or an error”, and error is represented by None —though some authors would want an error monad to be able to represent multiple kinds of errors rather than just collapse them all to None ), and the option monad (which is obvious).
Here’s an implementation of the monad signature for the maybe monad:
These are the same implementations of return and >>= as we invented above, but without the type annotations to force them to work only on integers. Indeed, we never needed those annotations; they just helped make the code above a little clearer.
In practice the return function here is quite trivial and not really necessary. But the >>= operator can be used to replace a lot of boilerplate pattern matching, as we saw in the final implementation of the arithmetic operators above. There’s just a single pattern match, which is inside of >>= . Compare that to the original implementations of plus_opt , etc., which had many pattern matches.
The result is we get code that (once you understand how to read the bind operator) is easier to read and easier to maintain.
Now that we’re done playing with integer operators, we should restore their original meaning for the rest of this file:
8.7.3. Example: The Writer Monad¶
When trying to diagnose faults in a system, it’s often the case that a log of what functions have been called, as well as what their inputs and outputs were, would be helpful.
Imagine that we had two functions we wanted to debug, both of type int -> int . For example:
(Ok, those are really simple functions; we probably don’t need any help debugging them. But imagine they compute something far more complicated, like encryptions or decryptions of integers.)
One way to keep a log of function calls would be to augment each function to return a pair: the integer value the function would normally return, as well as a string containing a log message. For example:
But that changes the return type of both functions, which makes it hard to compose the functions. Previously, we could have written code such as
or even better still, using the composition operator >> ,
and that would have worked just fine. But trying to do the same thing with the loggable versions of the functions produces a type-checking error:
That’s because inc_log x would be a pair, but dec_log expects simply an integer as input.
We could code up an upgraded version of dec_log that is able to take a pair as input:
That works fine, but we also will need to code up a similar upgraded version of f_log if we ever want to call them in reverse order, e.g., let id = dec_log >> inc_log . So we have to write:
And at this point we’ve duplicated far too much code. The implementations of inc and dec are duplicated inside both inc_log and dec_log , as well as inside both upgraded versions of the functions. And both the upgrades duplicate the code for concatenating log messages together. The more functions we want to make loggable, the worse this duplication is going to become!
So, let’s start over, and factor out a couple helper functions. The first helper calls a function and produces a log message:
The second helper produces a logging function of type ‘a * string -> ‘b * string out of a non-loggable function:
Using those helpers, we can implement the logging versions of our functions without any duplication of code involving pairs or pattern matching or string concatenation:
Here’s an example usage:
Notice how it’s inconvenient to call our loggable functions on integers, since we have to pair the integer with a string. So let’s write one more function to help with that by pairing an integer with the empty log:
And now we can write id’ (e 5) instead of id’ (5, "") .
Where’s the Monad? The work we just did was to take functions on integers and transform them into functions on integers paired with log messages. We can think of these “upgraded” functions as computations that log. They produce metaphorical boxes, and those boxes contain function outputs as well as log messages.
There were two fundamental ideas in the code we just wrote, which correspond to the monad operations of return and bind .
The first was upgrading a value from int to int * string by pairing it with the empty string. That’s what e does. We could rename it return :
This function has the trivial effect of putting a value into the metaphorical box along with the empty log message.
The second idea was factoring out code to handle pattern matching against pairs and string concatenation. Here’s that idea expressed as its own function:
Using >>= , we can re-implement loggable , such that no pairs or pattern matching are ever used in its body:
The Writer Monad. The monad we just discovered is usually called the writer monad (as in, “additionally writing to a log or string”). Here’s an implementation of the monad signature for it:
As we saw with the maybe monad, these are the same implementations of return and >>= as we invented above, but without the type annotations to force them to work only on integers. Indeed, we never needed those annotations; they just helped make the code above a little clearer.
It’s debatable which version of loggable is easier to read. Certainly you need to be comfortable with the monadic style of programming to appreciate the version of it that uses >>= . But if you were developing a much larger code base (i.e., with more functions involving paired strings than just loggable ), using the >>= operator is likely to be a good choice: it means the code you write can concentrate on the ‘a in the type ‘a Writer.t instead of on the strings. In other words, the writer monad will take care of the strings for you, as long as you use return and >>= .
8.7.4. Example: The Lwt Monad¶
By now, it’s probably obvious that the Lwt promises library that we discussed is also a monad. The type ‘a Lwt.t of promises has a return and bind operation of the right types to be a monad:
And Lwt.Infix.( >>= ) is a synonym for Lwt.bind , so the library does provide an infix bind operator.
Now we start to see some of the great power of the monad design pattern. The implementation of ‘a t and return that we saw before involves creating references, but those references are completely hidden behind the monadic interface. Moreover, we know that bind involves registering callbacks, but that functionality (which as you might imagine involves maintaining collections of callbacks) is entirely encapsulated.
Metaphorically, as we discussed before, the box involved here is one that starts out empty but eventually will be filled with a value of type ‘a . The “something more” in these computations is that values are being produced asynchronously, rather than immediately.
8.7.5. Monad Laws¶
Every data structure has not just a signature, but some expected behavior. For example, a stack has a push and a pop operation, and we expect those operations to satisfy certain algebraic laws. We saw those for stacks when we studied equational specification:
peek (push x s) = x
pop (push x empty) = empty
A monad, though, is not just a single data structure. It’s a design pattern for data structures. So it’s impossible to write specifications of return and >>= for monads in general: the specifications would need to discuss the particular monad, like the writer monad or the Lwt monad.
On the other hand, it turns out that we can write down some laws that ought to hold of any monad. The reason for that goes back to one of the intuitions we gave about monads, namely, that they represent computations that have effects. Consider Lwt, for example. We might register a callback C on promise X with bind . That produces a new promise Y, on which we could register another callback D. We expect a sequential ordering on those callbacks: C must run before D, because Y cannot be resolved before X.
That notion of sequential order is part of what the monad laws stipulate. We will state those laws below. But first, let’s pause to consider sequential order in imperative languages.
*Sequential Order. In languages like Java and C, there is a semicolon that imposes a sequential order on statements, e.g.:
First x is printed, then incremented, then printed again. The effects that those statements have must occur in that sequential order.
Let’s imagine a hypothetical statement that causes no effect whatsoever. For example, assert true causes nothing to happen in Java. (Some compilers will completely ignore it and not even produce bytecode for it.) In most assembly languages, there is likewise a “no op” instruction whose mnemonic is usually NOP that also causes nothing to happen. (Technically, some clock cycles would elapse. But there wouldn’t be any changes to registers or memory.) In the theory of programming languages, statements like this are usually called skip , as in, “skip over me because I don’t do anything interesting.”
Here are two laws that should hold of skip and semicolon:
skip; s; should behave the same as just s; .
s; skip; should behave the same as just s; .
In other words, you can remove any occurrences of skip , because it has no effects. Mathematically, we say that skip is a left identity (the first law) and a right identity (the second law) of semicolon.
Imperative languages also usually have a way of grouping statements together into blocks. In Java and C, this is usually done with curly braces. Here is a law that should hold of blocks and semicolon:
In other words, the order is always s1 then s2 then s3 , regardless of whether you group the first two statements into a block or the second two into a block. So you could even remove the braces and just write s1; s2; s3; , which is what we normally do anyway. Mathematically, we say that semicolon is associative.
Sequential Order with the Monad Laws. The three laws above embody exactly the same intuition as the monad laws, which we will now state. The monad laws are just a bit more abstract hence harder to understand at first.
Suppose that we have any monad, which as usual must have the following signature:
The three monad laws are as follows:
Law 1: return x >>= f behaves the same as f x .
Law 2: m >>= return behaves the same as m .
Law 3: (m >>= f) >>= g behaves the same as m >>= (fun x -> f x >>= g) .
Here, “behaves the same as” means that the two expressions will both evaluate to the same value, or they will both go into an infinite loop, or they will both raise the same exception.
These laws are mathematically saying the same things as the laws for skip , semicolon, and braces that we saw above: return is a left and right identity of >>= , and >>= is associative. Let’s look at each law in more detail.
Law 1 says that having the trivial effect on a value, then binding a function on it, is the same as just calling the function on the value. Consider the maybe monad: return x would be Some x , and >>= f would extract x and apply f to it. Or consider the Lwt monad: return x would be a promise that is already resolved with x , and >>= f would register f as a callback to run on x .
Law 2 says that binding on the trivial effect is the same as just not having the effect. Consider the maybe monad: m >>= return would depend upon whether m is Some x or None . In the former case, binding would extract x , and return would just re-wrap it with Some . In the latter case, binding would just return None . Similarly, with Lwt, binding on m would register return as a callback to be run on the contents of m after it is resolved, and return would just take those contents and put them back into an already resolved promise.
Law 3 says that bind sequences effects correctly, but it’s harder to see it in this law than it was in the version above with semicolon and braces. Law 3 would be clearer if we could rewrite it as
(m >>= f) >>= g behaves the same as m >>= (f >>= g) .
But the problem is that doesn’t type check: f >>= g doesn’t have the right type to be on the right-hand side of >>= . So we have to insert an extra anonymous function fun x -> . to make the types correct.
8.7.6. Composition and Monad Laws¶
There is another monad operator called compose that can be used to compose monadic functions. For example, suppose you have a monad with type ‘a t , and two functions:
The composition of those functions would be
compose f g : ‘a -> ‘c t
That is, the composition would take a value of type ‘a , apply f to it, extract the ‘b out of the result, apply g to it, and return that value.
We can code up compose using >>= ; we don’t need to know anything more about the inner workings of the monad:
Введение
Как узнать, что человек понял, что такое монады? Он сам вам об этом расскажет в первые 5 минут общения и обязательно попробует объяснить. А ещё напишет об этом текст и по возможности где-нибудь его опубликует, чтобы все остальные тоже поняли, что такое монады.
Среди функциональных программистов, особенно на Haskell, монады стали чем-то вроде локального мема. Их часто пытаются объяснить, отталкиваясь от частных случаев и сразу приводя примеры использования. Из-за этого слушатель может не уловить основную суть понятия, а монады так и останутся чёрной магией, ну или просто средством костылизации побочных эффектов в чисто функциональных языках.
Я сначала расскажу про базовые понятия теории категорий, а затем мы с практической точки зрения подойдём к определению монады и увидим, что на самом деле очень многие программисты пользуются этой мощной абстракцией в одном из её проявлений.
Моё изложение во многом основывается на книге Бартоша Милевски «Теория категорий для программистов», которая создавалась как серия блогпостов, доступна в PDF, а недавно вышла в бумаге.
Примеры приводятся на Haskell, предполагается, что читатель знаком с синтаксисом и основными понятиями языка. В упомянутой книге есть примеры и на С++, можете сравнить чистоту и понятность кода.
Категории
Определение
Категории сами по себе — очень простые конструкции. Категория — это набор объектов и морфизмов между ними. Морфизмы можно рассматривать как однонаправленные стрелки, соединяющие объекты. В общем случае про сущность самих объектов ничего не известно. Теория категорий работает не с объектами, а с морфизмами, точнее — с их композицией.
Используется следующая нотация:
- ObC — объекты категории C;
- HomC(A, B) — морфизмы из A в B;
- g ∘ f — композиция морфизмов f и g.
В определении категории на морфизмы накладываются дополнительные ограничения:
- Для пары морфизмов 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)).
- Для каждого объекта задан тождественный морфизм idA ∈ Hom(A, A).
Существуют два важных свойства, которым должна удовлетворять любая категория (аксиомы теории категорий):
- Ассоциативность композиции: h ∘ (g ∘ f) = (h ∘ g) ∘ f;
- Композиция с тождественным морфизмом: если f ∈ Hom(A, B), то f ∘ idA = idB ∘ f = f.
Категории очень легко и естественно визуализируются как ориентированные графы. В принципе, любой ориентированный граф можно достроить до категории, добавив композиции морфизмов и тождественные морфизмы, если необходимо.
Для любой категории можно определить двойственную категорию (обозначается C op , в которой морфизмы получены разворотом стрелок исходной категории, а объекты — те же самые. Это позволяет формулировать двойственные утверждения и теоремы, истинность которых не меняется при обращении стрелок.
Объекты и морфизмы не обязательно образуют множества (в классическом смысле из теории множеств), поэтому в общем случае используется словосочетание «класс объектов». Категории, в которых классы объектов и морфизмов всё-таки являются множествами, называются малыми категориями. Далее мы будем работать только с ними.
Типы и функции
Рассмотрим категорию, в которой объектами являются типы языка Haskell, а морфизмами — функции. Например, типы Int и Bool — это примеры объектов, а функция типа Int -> Bool — морфизм.
Тождественным морфизмом является функция id , возвращающая свой аргумент:
Композиция морфизмов — это композиция функций, причём синтаксис этой операции на Haskell почти идентичен математической нотации:
Категория, в которой объекты представляют собой множества, а морфизмы — отображения, называется Set. Типы также можно рассматривать как множества допустимых значений, а функции — как отображения множеств, но с одной оговоркой: вычисления могут не завершиться. Для обозначения такой ситуации вводится специальный тип bottom, обозначаемый _|_ . Считается, что любая функция либо возвращает значение типа, указанного в сигнатуре, либо значение типа bottom. Категория типов языка Haskell, в которой учитывается эта особенность, называется Hask. Для упрощения изложения мы будем работать с ней так же, как с категорией Set. Любопытно, что в этой категории морфизмы между двумя объектами в свою очередь образуют множество, которое является объектом в этой же категории: HomC(A, B) ∈ C. Действительно, функциональный тип a -> b — это тоже тип языка Haskell.
Рассмотрим несколько примеров типов с точки зрения теории категорий.
Пустому множеству соответствует тип Void , у которого нет значений (такой тип называется ненаселённым). Существует даже полиморфная функция absurd , которую можно определить, но невозможно вызвать, поскольку для вызова ей нужно передать значение типа Void , а таких значений нет:
Множеству из одного элемента соответствует тип Unit , единственное значение которого — пустой кортеж, также обозначаемый () . Полиморфная функция unit возвращает это значение, принимая на вход любой другой тип:
Множество из двух элементов — логический тип Bool :
Построим категорию, объектами в которой являются типы Void , Unit и Bool .
Из Void выходят только морфизмы, соответствующие функции absurd , один в Bool , один в Unit . В обратную сторону морфизмов нет, поскольку мы никак не можем получить значения ненаселённого типа Void , просто потому что их не существует, а значит и не можем определить тело этой функции.
Функция типа Bool -> Unit может быть только одна, unit , поскольку независимо от входного значения мы можем вернуть только пустой кортеж. А вот для реализации функции типа Unit -> Bool возможны варианты. Такая функция в любом случае будет принимать значение () , но вернуть можно либо True , либо False . Таким образом, получили два морфизма из Unit в Bool :
Морфизмы из Bool в Bool — это булевы функции от одного аргумента, которых 4 штуки (в общем случае количество булевых функций от n аргументов — 2 2 n ): id , true и false , которые мы уже определяли выше, а также функция not :
Добавив тождественные морфизмы, получим следующую категорию:
В дальнейшем изложении будем использовать Haskell-подобную нотацию сигнатуры типов для обозначения морфизмов.
Функторы
Функтор — это отображение категорий. Для двух категорий, C и D, функтор F осуществляет два вида преобразований. Во-первых, функтор преобразует объекты из категории C в объекты из категории D. Если a — объект из категории C, то F a — соответствующий ему объект из категории D, полученный в результате применения функтора. Во-вторых, функтор действует на морфизмы: морфизм f :: a -> b в категории C преобразуется в морфизм F f :: F a -> F b в категории D.
Кроме того, должны выполняться «законы сохранения» композиции и тождественного морфизма:
- Если h = g ∘ f, то F h = F g ∘ F f.
- Если ida — тождественный морфизм для объекта a, то F ida = idF a — тождественный морфизм для объекта F a.
Таким образом, функтор не «ломает» структуру категории: то, что было связано морфизмом в исходной категории, будет связано и в результирующей. Это верно и для крайних случаев, например, когда результирующая категория состоит из одного объекта и одного (тождественного) морфизма. Тогда все морфизмы исходной категории отобразятся в тождественный морфизм для этого объекта, но упомянутые выше законы нарушены не будут.
Функторы можно комбинировать аналогично функциям. Для двух функторов, F :: C -> D и G :: D -> E можно определить композицию G . F :: C -> E . Кроме того, для каждой категории несложно построить тождественный функтор, который будет переводить как объекты, так и морфизмы, в самих себя. Обозначим их IdC, IdD и IdE. Функторы, действующие из категории в неё саму, называются эндофункторы.
Посмотрим на эту картинку сильно издалека, так, чтобы сами категории превратились в точки-объекты, а функторы — в стрелки между ними (морфизмы). Получим категорию малых категорий, которая называется Cat (название периодически порождает сложные мемы с кошками).
Вернёмся к категории типов языка Haskell и будем работать с эндофункторами в этой категории. Они преобразуют типы в другие типы и, кроме того, каким-то образом преобразуют функции, работающие с этими типами.
Конструктор типа Maybe является примером такого функтора, он преобразует тип a в тип Maybe a (сам по себе Maybe не является типом!):
Для преобразования морфизмов, необходимо уметь получать из функции f :: a -> b функцию F f :: Maybe a -> Maybe b . Это действие можно записать в виде функции высшего порядка fmap . Обратите внимание, что тип этой функции как раз наглядно описывает преобразование морфизмов (из одной функции получаем другую):
Конечно, Maybe — не единственный функтор. Существует целый класс типов, который так и называется, Functor . Единственным методом этого класса является функция fmap , показывающая, как преобразуются морфизмы (а преобразование объектов — это применение конструктора типа к конкретным типам):
В более прикладном смысле функторы — это контейнеры, которые хранят значения других типов, а функция fmap позволяет преобразовывать объекты внутри этих контейнеров. Если опустить скобки вокруг f a -> f b , как это сделано в определении выше, то такая сигнатура лучше подойдёт для описания функторов как контейнеров.
Монады
Все функции, которые были рассмотрены до этого, были чистыми, т.е. предполагалось, что у них нет побочных эффектов. Это функции в математическом смысле: результат чистой функции зависит только от значения её аргумента, он не меняется из-за места или времени вызова.
Поставим перед собой задачу логгировать вызовы функций. На императивном языке проще всего было бы хранить лог как глобальное состояние, которое изменяется в теле каждой функции. Программирование на функциональных языках не располагает к использованию глобального состояния, поэтому будем решать поставленную задачу, оперируя имеющимися у нас чистыми функциями — морфизмами в категории типов языка Haskell.
В качестве примера возьмём функции для преобразования строк: upCase , переводящую все символы строки в верхний регистр, и toWords , разбивающую строки на слова. Пока что их реализация всего лишь использует встроенные функции toUpper и words :
Типы функций позволяют составить их композицию:
Чтобы не отвлекаться на сложности реализации, в качестве представления лога возьмём просто строку. Мы хотим, чтобы после применения функции processString в логе содержалась запись «upCase toWords».
Запись в лог — побочное действие функций, мало относящееся к их основному функционалу. Хотелось бы во-первых, добавить информацию на уровне типов о том, что будет выполняться логгирование, и во-вторых, минимизировать дополнительные действия, которые придётся проделать сторонним разработчикам для работы с этими функциями.
Создадим новый тип данных, который будет помимо самих значений типа a хранить ещё и строку, в которую каждая вызванная функция будет добавлять своё имя.
Заметим, что Writer — это функтор, мы легко можем описать для него функцию fmap :
Преобразуем функции upCase и toWords и сделаем так, чтобы они возвращали значение, «завёрнутое» в тип Writer :
Теперь мы больше не можем записать композицию этих функций так же, как раньше, из-за несоответствия типов. Определим специальную функцию для композиции, которая сначала получает значение типа b и первую строку, передаёт это значение второй функции, получает значение типа c и вторую строку и в качестве финального результата возвращает значение типа c и конкатенацию строк, полученных при вычислении:
Реализация функции processString принимает вид:
Вернёмся к понятиям теории категорий. Мы можем заменить все функции (морфизмы) типа a -> b на a -> Writer b и получить новую категорию, в которой такие функции являются новыми морфизмами между a и b . Осталось только определить тождественный морфизм, т.е. функцию типа a -> Writer a :
Таким образом, мы получили новую категорию, основанную на Hask. В этой категории объектами являются те же типы, но морфизмом между типами a и b являются функции типа не a -> b , а a -> m b , т.е. возвращаемый тип «завёрнут» в какой-то другой фиксированный конструктор типа m . Такие функции мы будем называть обогащёнными (embellished). Композиция морфизмов и тождественный морфизм зависят от m , реализация для Writer — лишь частный случай.
Обобщим сказанное выше для любой категории C и эндофунктора m. Построим категорию K, состоящую из тех же объектов, что и категория C, т.е. ObK = ObC. Морфизм a -> b в категории K соответствует морфизму a -> m b в исходной категории C: HomK(a, b) = HomC(a, m b). Для типов и функций это будет означать, что функции, работающие с типами в категории K — обогащённые функции в категории C.
Для того, чтобы получить настоящую категорию с такими морфизмами, необходимо определить ассоциативную композицию морфизмов и тождественный морфизм для каждого объекта таким образом, чтобы соблюдались аксиомы теории категорий. Тогда полученная категория называется категорией Клейсли, а функтор m — монадой. На Haskell это определение выглядит так (везде далее используются типы из категории Hask):
Тип оператора >=> , который иногда называют «fish», показывает суть монад: это способ композиции обогащённых функций. Побочные эффекты, работа с состоянием, исключения — всё это лишь частные случаи, они не определяют, что такое монады, но являются хорошими примерами их использования. Writer — тоже монада, определённая нами функция compose — это композиция морфизмов >=> , а функция writerId — тождественный морфизм return .
Начнём реализовывать оператор >=> в общем виде. Результатом композиции двух обогащённых функций должна быть тоже функция, поэтому в реализации используем лямбда-выражение. Аргумент этого выражения имеет тип a , и у нас есть функция f , которую к нему можно применить, а дальше работать с результатом её вычисления во вспомогательной функции, которую назовём bind :
Функция bind получает значение типа b «в контейнере» m и функцию, которая принимает на вход аргумент типа b и возвращает m c . Тип результата у неё совпадает с типом результата >=> . Мы получили следующую сигнатуру типов: m b -> (b -> m c) -> m c . Эту функцию необходимо реализовать для каждой монады, чтобы описать способ композиции обогащённых функций. Мы подошли к «классическому» определению монад в Haskell в виде класса типов с методами >>= , или bind , и return :
Теперь попробуем продолжить реализацию в общем виде, для чего каким-то образом нужно применить функцию типа b -> m c к значению типа b , но у нас есть только значение типа m b . Вспомним, что изначально мы работаем с эндофунктором m , поэтому можем воспользоваться функцией fmap , которая в данном случае будет типа (a -> m b) -> m a -> m (m b) . Для завершения реализации >>= необходимо преобразовать значение типа m (m b) к m b , «схлопнув» контейнеры, но это уже невозможно сделать в общем виде. Выразим это преобразование как функцию join :
Например, для типа Writer реализация будет следующей:
Мы пришли к третьему определению класса Monad :
Здесь присутствует явное требование на то, чтобы m был функтором. Это ограничение не было нужно для предыдущих определений, поскольку функция fmap реализуется через >>= :
Практическое применение монад
Приведём примеры практического применения монад для решения задач, которые традиционно решаются с использованием «нечистых» функций и побочных эффектов.
Недетерминированные вычисления
Абстракция недетерминированных вычислений (т.е. таких, у которых может быть несколько возможных результатов) реализуется с помощью списков.
Композиция обогащённых функций должна иметь тип (a -> [b]) -> (b -> [c]) -> (a -> [c]) . Достаточно опытному программисту реализация может быть понятна из одной этой сигнатуры:
Типы практически не оставляют возможности сделать неверный шаг. Получив значение типа a , единственное, что можно с ним сделать — это применить функцию f и получить список [b] . Далее всё, что мы умеем делать со значениями типа b — применить функцию g к каждому из них в списке и получить в результате список списков: map g (f x) :: [[c]] . Чтобы получить нужный результат, конкатенируем их.
Тогда оператор >>= можно записать так:
Осталось реализовать функцию return :: a -> [a] . Здесь реализация снова выводится из типа:
Резюмируем эти реализации в классическом определении класса Monad :
Конечно, список как результат функции не обязательно обозначает недетерминированность вычислений. Хорошим примером, когда это действительно так, является реализация искусственного интеллекта для игр. Список может представлять возможные результаты хода игрока, ответных ходов может быть тоже несколько — всё время приходится работать со списками, списками списков и т.д.
Исключения
Простейшая реализация обработки исключений в чистых функциях состоит в добавлении в тип возвращаемого значения специального варианта, обозначающего, что что-то пошло не так.
Для этого подойдёт, к примеру, уже рассмотренный функтор Maybe . При штатной работе функции будут возвращать значение в конструкторе Just , при возникновении ошибки — значение Nothing . Композиция таких обогащённых функций должна работать таким образом, чтобы каждая следующая функция не вызывалась, если ошибка уже произошла в предыдущем вызове:
Определение методов класса Monad для Maybe :
Недостаток этого подхода состоит в том, что исключение никак не конкретизируется. Мы просто знаем, что в какой-то из функций, участвовавшей в композиции, произошла какая-то ошибка. С этой точки зрения удобнее будет использовать тип Either String a , который представляет собой альтернативу двух значений: либо это строка с описанием ошибки, либо результат штатной работы функции. В общем виде тип определяется так:
Для классификации ошибок можно использовать перечислимый тип или любую другую структуру данных, подходящую для конкретной задачи. Мы в примерах продолжим использовать просто строку. Введём синоним типа для работы с исключениями:
Композиция функций описывается аналогично случаю с использованием Maybe :
Определение экземпляра класса Monad уже не должно вызывать трудностей:
Состояния
Пример с логгером, с которого мы начинали, реализует работу с write-only состоянием, но хотелось бы использовать состояние и для чтения. Модифицируем тип функции a -> b так, чтобы получить обогащённую функцию, работающую с состоянием. Добавим в тип функции один аргумент, обозначающий текущее состояние, а также изменим тип возвращаемого значения (теперь это пара, состоящая из самого значения и изменённого состояния):
Объявим синоним типа для работы с состоянием:
Фиксируем тип состояния s и покажем, что State s является функтором. Нам понадобится вспомогательная функция runState :
Реализация класса Functor :
Таким образом, обогащённые функции из a в b , в которых ведётся работа с состоянием, имеют тип a -> State s b , причём State s — функтор. Попробуем превратить его в монаду, реализовав их композицию:
Отсюда получим реализацию класса Monad . Тождественный морфизм, функция return , ничего не делает с состоянием, а просто добавляет свой аргумент в пару-результат:
Функция для чтения состояния должна всегда возвращать текущее состояния, ей не нужны аргументы. Можно сказать, что это морфизм из Unit в s в категории Клейсли, поэтому функция должна иметь тип Unit -> State s s :
Конечно, в реализации Unit можно опустить. Здесь он добавлен для того, чтобы показать эту операцию с точки зрения теории категорий.
Запись состояния, наоборот, принимает новое значение состояния и записывает его. Нам важен только побочный эффект, но не возвращаемое значение, поэтому соответствующий морфизм идёт в обратную сторону, из s в Unit , а функция имеет тип s -> State s Unit :
Реализация работы с состоянием вышла чуть более сложной, чем предыдущие примеры, но на её основе можно создать формальную модель для работы с вводом/выводом. В ней предполагается, что «окружающий мир» реализован в виде некоторого типа RealWorld , о котором неизвестно никаких подробностей. При общении с внешним миром программа получает на вход объект типа RealWorld и производит какие-то действия, в результате которых получает нужный ей результат и изменяет внешний мир (например, выводит строку на экран или читает символ из потока ввода). Эту абстрактную концепцию можно реализовать с помощью состояния:
Тип IO — один из первых, о котором узнаёт начинающий пользователь Haskell, и наверняка сразу встречает пугающее слово «монада». Такой упрощённый взгляд на этот тип как на состояние для работы с внешним миром может помочь понять, почему это так. Кончено, это описание очень поверхностно, но полноценный рассказ о том, как на самом деле реализован ввод-вывод, зависит от компилятора и выходит далеко за рамки статьи.
Монада — программируемая точка с запятой
Монады — программируемые точки с запятой. Именно так. Монада предоставляет функции, позволяющие упорядочивать действия. Более того, между каждыми двумя действиями выполняется определённый фрагмент кода. Итак, монада — настраиваемая точка с запятой.
Сделаем шаг назад
В императивных языках, таких как C и Java, для выражения последовательности операций используются точки с запятой. Код перед точкой с запятой выполняется перед кодом после другой точки с запятой. В таких языках, как Haskell, где более или менее всё является просто выражением, на первый взгляд не видно, какова последовательность выполнения.
Это интересно: монады происходят из области математики под названием “Теория категорий”. Для использования и понимания монад в Haskell не обязательно знать определения и теоремы этой математической дисциплины.
Секвенирование легче на других языках. Значит ли это, что Haskell плохо спроектирован?
Вовсе нет. Можно сказать, что так сделано преднамеренно. Haskell разработан как ссылочно прозрачный язык. Это просто причудливый способ сказать, что каждый вызов функции может быть заменён его возвращаемым значением.
Представьте, что у вас есть функция с именем doCalculation , которая принимает число, выполняет некоторые вычисления и возвращает другое число. В Haskell выражение doCalculation(x) + doCalculation(x) можно заменить на 2*doCalculation(x) . При этом мы можем быть уверены, что поведение программы не изменится. В Java эта замена вообще не выполнима, поскольку не гарантируется, что doCalculation возвращает один и тот же результат при каждом вызове. Например, метод может просто вызвать генератор случайных чисел и всегда возвращать другой результат. Кроме того, в таких языках, как Java, doCalculation может включать общие побочные эффекты: запись в базу данных или вывод на консоль.
Ссылочная прозрачность имеет много преимуществ. Оптимизация проще для компиляторов ссылочно прозрачных языков. Более того, до некоторой степени можно автоматизировать параллелизм . Однако все эти функции сопряжены с затратами на более сложное разделение инструкций. Но если уж на то пошло, мы можем использовать монады.
Ближе к сути
Как можно запрограммировать и использовать такую точку с запятой? Ответим на вопрос примером: созданием и редактированием списков покупок. Список покупок — это список строк. Мы можем реализовать функции, добавляющие элементы один за другим, а также функцию, удаляющую первый элемент. Кроме того, мы хотим подсчитать, сколько раз список был изменен. Определим новый тип:
Тип Counter состоит из целого числа с именем counter и произвольного элемента. Для наших списков покупок элементом будет список строк. Счётчик будет представлять количество выполненных манипуляций. Давайте перейдём к самой важной части. Чтобы запрограммировать точку с запятой, включив секвенирование, мы пишем следующее:
Именно здесь происходит магия. Начнем с более простой функции.
return просто создаёт новый счётчик для данного элемента. Он может использоваться для построения нового счётчика, начинающегося с 0 манипуляций для данного списка покупок.
Как и всё в Haskell, монада — просто ещё одна функция. В нашем примере она имеет тип Counter a → (a → Counter b) → Counter b (для наших конкретных списков покупок a и b будут списками строк). А теперь то же самое — медленно: >>= получает счётчик с элементом (в коде он называется x ). Он манипулирует элементом с помощью заданной функции, которая снова возвращает счётчик. Наконец, >>= возвращает новый счётчик, в котором целое, представляющее число манипуляций, является целым счётчика из данной функции плюс 1.
Решающее значение в определении нашей программируемой точки с запятой имеет то, что счётчик известен до вычисления функции, заданной во втором аргументе. Таким образом, если счётчик в первом аргументе перед монадой — просто выражение, приводящее к конкретному счётчику, то мы можем быть уверены, что это выражение будет вычислено до вызова функции, заданной во втором аргументе, после монады.
Чтобы иметь возможность добавлять и удалять товары в наших списках, нужно определить ещё две однострочные функции. Кроме того, мы определяем наш первый, пустой список.
Сейчас у нас есть все, чтобы создать типичный список покупок, по одному пункту за раз. Выполнение кода приводит к следующему результату:
Что здесь происходит?
Начнём с пустого списка покупок, в котором нет никаких элементов, с счётчиком на 0 . Монада берет список, полученный из строки, и передаёт его функции в следующей строке.
Пустой список покупок по сути передаётся через строки и подвергается манипуляциям на каждом этапе. Ключевой момент: мы можем быть уверены, что “Bread” добавляется перед “Butter”. Как описано выше, так происходит благодаря определению программируемой точки с запятой.
Заметьте, что все в нашей операции с монадой состоит из функций. Каждая строка, кроме первой, является анонимной функцией, как и >>= .
В заключение отметим, что мы реализовали способ секвенирования действий в чисто функциональном стиле. Haskell предоставляет много синтаксического сахара, который позволяет писать операции с монадами так, чтобы ещё больше подчеркнуть свойство секвенирования:
Эти два определения полностью эквивалентны. В конце концов, это дело вкуса, какой из них использовать. Для начала, однако, желательно использовать явную форму, чтобы помнить о происходящем за кулисами.
Ещё одно важное замечание: после определения в программируемой точке с запятой, подсчёт полностью невидим внутри операции. Магия происходит внутри >>= . Поскольку функциональность монады можно свободно определить, это отличное место, чтобы скрыть что-то. Предопределённая монада maybe , например, скрывает проверку на null и пропускает все следующие строки, если видит null . Кроме того, монадой можно реализовать логирование и скрыть в >>= .
Парсер — ещё одно приложение, использующее монаду состояния, но это совсем другая история. Итак, монады полезны в различных ситуациях. В конце концов, они не больше и не меньше, чем программируемые точки с запятой.
Функциональное программирование с примерами на JavaScript. Часть первая. Основные техники функционального программирования
Функциональное программирование, или ФП, может изменить стиль вашего написания программ к лучшему. Но освоить его довольно непросто, а многие посты и туториалы не рассматривают детали (вроде монад, аппликативных функторов и т.п.) и не предоставляют примеры из практики, которые помогли бы новичкам использовать мощные техники ФП ежедневно. Поэтому я решил написать статью, в которой освещу основные идеи ФП.
В первой части вы изучите основы ФП, такие как каррирование, чистые функции, fantasy-land, функторы, монады, Maybe-монады и Either-монады на нескольких примерах.
Функциональное программирование — это стиль написания программ через составление набора функций.
Основной принцип ФП — оборачивать практически все в функции, писать множество маленьких многоразовых функций, а затем просто вызывать их одну за другой, чтобы получить результат вроде (func1.func2.func3) или в композиционном стиле func1(func2(func3())) .
Кроме этого, структура функций должна следовать некоторым правилам, описанным ниже.
Итак, у вас могло возникнуть несколько вопросов. Если любую задачу можно решить, объединяя вызовы нескольких функций, то:
- Как реализовать условия (if-else)? (Совет: используйте монаду Either);
- Как перехватить исключения типа Null Exception? (В этом может помочь монада Maybe);
- Как убедиться в том, что функция действительно «многоразовая» и может использоваться в любом месте? (Чистые функции);
- Как убедиться, что данные, которые мы передаем, не изменяются, чтобы мы могли бы использовать их где-то еще? (Чистые функции, иммутабельность);
- Если функция принимает несколько значений, но цепочка может передавать только одно значение, как мы можем сделать эту функцию частью цепочки? (Каррирование и функциивысшегопорядка).
Чтобы решить все эти проблемы, функциональные языки, вроде Haskell, предоставляют инструменты и решения из математики, такие как монады, функторы и т.д., из коробки.
Хотя в JavaScript эти инструменты не встроены, к счастью, у него достаточно преимуществ, позволяющих людям реализовывать недостающие функции в собственных библиотеках.
Спецификация Fantasy-Land и библиотеки ФП
В библиотеках, содержащих такие инструменты, как функторы и монады, реализуются функции и классы, которые следуют некоторым спецификациям, чтобы предоставлять функциональность, подобную стандартной библиотеке Haskell.
Fantasy-Land — одна из таких спецификаций, в которой описано, как должна действовать та или иная функция или класс в JS.
На рисунке выше показаны все спецификации и их зависимости. Спецификации — это, по существу, описания функционала, подобные интерфейсам в Java. С точки зрения JS вы можете думать о спецификациях, как о классах или функциях-конструкторах, которые реализовывают некоторые методы ( map , of , chain ), следуя спецификации.
Например, класс в JavaScript является функтором, если он реализует метод map . Метод map должен работать, следуя спецификации.
По аналогии, класс в JS является аппликативным функтором, если он реализует функции map и ap .
JS-класс — монада, если он реализует функции, требуемые функтором, аппликативным функтором, цепочкой и самой монадой.
Библиотеки, следующие спецификациям Fantasy-Land
Какие же из них мне использовать?
Такие библиотеки, как lodash-fp и ramdajs, позволяют вам начать программировать в функциональном стиле. Но они не реализуют функции, позволяющие использовать ключевые математические концепты (монады, функторы, свертки), а без них невозможно решать некоторые из реальных задач в функциональном стиле.
Так что в дополнение к ним вы должны использовать одну из библиотек, следующих спецификациям FL.
Теперь, когда мы знаем основы, давайте посмотрим на несколько практических примеров и изучим на них некоторые из возможностей и техник функционального программирования.
Пример 1: справляемся с проверкой на NULL
Тема покрывает: функторы, монады, Maybe-монады и каррирование.
Сценарий использования: Мы хотим показать различные стартовые страницы в зависимости от языка, выбранного пользователем в настройках. В данном примере мы реализовываем функцию getUrlForUser, которая возвращает правильный URL из списка indexURLs для испанского языка, выбранного пользователем joeUser.
Проблема: язык может быть не выбран, то есть равняться null. Также сам пользователь может быть не залогинен и равняться null. Выбранный язык может быть не доступен в нашем списке indexURLs. Так что мы должны позаботиться о нескольких случаях, при которых значение null или undefined может вызвать ошибку.
Решение (Императивное против Функционального):
Не беспокойтесь, если функциональное решение пока вам не понятно, я объясню его шаг за шагом немного позже.
Давайте для начала попробуем понять некоторые из концептов ФП, которые были использованы в этом решении.
Функторы
Любой класс или тип данных, который хранит значение и реализует метод map , называется функтором.
Например, Array — это функтор, потому что массив хранит значения и реализует метод map , позволяющий нам применять функцию к значениям, которые он хранит.
Давайте напишем свой собственный функтор «MyFunctor». Это просто JS-класс (функция-конструктор). Метод map применяет функцию к хранимым значениям и возвращает новый экземпляр MyFunctor.
Функторы так же должны реализовывать и другие спецификации в дополнение к методу map , но я не буду рассказывать о них в этой статье.
Монады
Монады — это подтип функторов, так как у них есть метод map , но они также реализуют другие методы, например, ap , of , chain .
Ниже представлена простая реализация монады.
Обычные монады используются нечасто, в отличие от более специфичных монад, таких как «монада Maybe» и «монада Either«.
«Maybe»-монада
Монада «Maybe» — это класс, который имплементирует спецификацию монады. Её особенность заключается в том, что с помощью нее можно решать проблемы с null и undefined.
В частности, в случае, если данные равны null или undefined, функция map пропускает их.
Код, представленный ниже, показывает имплементацию Maybe-монады в библиотеке ramda-fantasy. Она возвращает экземпляр одного из двух подклассов: Just или Nothing, в зависимости от значения.
Классы Just и Nothing содержат одинаковые методы ( map , orElse и т.д.). Отличие между ними в реализации этих самых методов.
Обратите особое внимание на функции «map» и «orElse».
Давайте поймем, как Maybe-монада осуществляет проверку на null.
- Если есть объект, который может равняться null или иметь нулевые свойства, создаем экземпляр монады из него.
- Используем библиотеки, вроде ramdajs, чтобы получить значение из монады и работать с ним.
- Возвращаем значение по умолчанию, если данные равняются null.
Каррирование
Освещенные темы: чистые функции и композиция.
Если мы хотим создавать серии вызовов функций, как то func1.func2.func3 или (func1(func2(func3())) , все эти функции должны принимать только один параметр. Например, если func2 принимает два параметра (func2(param1, param2)) , мы не сможем включить её в серию.
Но с практической точки зрения многие функции могут принимать несколько параметров. Так как же нам создавать из них цепочки? Ответ: С помощью каррирования.
Каррирование превращает функцию, которая принимает несколько параметров в функцию, которая принимает только один параметр за один раз. Функция не запустится, пока все параметры не будут переданы.
В дополнение, каррирование может быть также использовано в ситуациях, когда мы обращаемся к глобальным значениям.
Давайте снова взглянем на наше решение:
Пример 2: обработка функций, бросающих исключения и выход сразу после ошибки
Освещенные темы: Монада «Either»
Монада Maybe подходит нам, чтобы обработать ошибки, связанные с null и undefined. Но что делать с функциями, которым требуется выбрасывать исключения? И как определить, какая из функций в цепочке вызвала ошибку, когда в серии несколько функций, бросающих исключения?
Например, если func2 из цепочки func1.func2.func3. выбросила исключение, мы должны пропустить вызов func3 и последующие функции и корректно обработать ошибку.
Монада Either
Монада Either превосходно подойдет для подобной ситуации.
Пример использования: В примере ниже мы рассчитываем «tax» и «discont» для «items» и в конечном счете вызываем showTotalPrice.
Заметьте, что функции «tax» и «discount» выбросят исключение, если в качестве цены передано не числовое значение. Функция «discount», помимо этого, вернет ошибку в случае, если цена меньше 10.
Давайте посмотрим, как можно реализовать этот пример в функциональном стиле, используя монаду Either.
Either-монада предоставляет два конструктора: «Either.Left» и «Either.Right«. Думайте о них, как о подклассах Either. И «Left«, и «Right» тоже являются монадами. Идея в том, чтобы хранить ошибки или исключения в Left и полезные значения в Right.
Экземпляры Either.Left или Either.Right создаются в зависимости от значения функции.
Так давайте же посмотрим, как изменить наш императивный пример на функциональный.
Шаг 1: Оберните возвращаемые значения в Left и Right. «Оборачивание» означает создание экземпляра класса с помощью оператора new.
Шаг 2: Оберните исходное значение в Right, так как оно валидно.
Шаг 3: Создайте две функции: одну для обработки ошибок, а другую для отображения результата. Оберните их в Either.either (из библиотеки ramda-fantasy.js).
Either.either принимает 3 параметра: обработчик успешного завершения, обработчик ошибок и монаду Either. Сейчас мы можем передать только обработчики, а третий параметр, Either, передать позже.
Как только Either.either получит все три параметра, она передаст третий параметр в обработчик успешного завершения или обработчик ошибок, в зависимости от типа монады: Left или Right.
Шаг 4: Используйте метод chain, чтобы создать цепочку из нескольких функций, выбрасывающих исключения. Передайте результат их выполнения в Either.either (eitherLogOrShow).
Все вместе выглядит следующим образом:
В следующей части мы рассмотрим аппликативные функторы, curryN и Validation Applicative.