Монады и аппликативные функторы на Python за 50 минут

"Ещё один туториал по монадам" -- на эту тему есть классическая шутка Haskell-программистов. Дескать, это обязательный путь хаскель-новичка.

Как известно, "монада -- это моноид в категории эндофункторов". Этот легендарный мем можно найти на куче форумов. В оригинале он звучит так: "A Monad is just a monoid in the category of endofunctors", и получил массовость, будучи упомянут в2009 г. в шутливой анти-истории программирования "Brief, Incomplete and Mostly Wrong History of Programming Languages" от JamesIry. Но эти темы на самом деле относятся к теории категорий и абстрактной алгебре.

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

В императивном программировании для реализации такого подхода всё содержимое каждой функции, претендующей на роль монады (точнее, аппликативного функтора (см. далее) -- более "слабой" в математическом смысле модели), надо охватить блоком try-catch. Также надо проверять, не вернула ли уже предыдущая функция некий условный код ошибки, чтобы сразу же передать его по цепочке дальше. В итоге код получается разбухшим и совсем не наглядным.

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

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

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

pip install PyMonad

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

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

Вот как можно реализовать эту схему (эх, тут текст с отступами не отформатировать...):

from math import pi, sin as _sin

def sin(theta, state):

.... return (_sin(theta), state + 1)

Переменная count работает тут как счётчик, однако огромный недостаток данного подхода в том, что мы храним временное значение -- заводим изменяемые, мутабельные объекты.

Условно говоря, мы получим что-то вроде

(x, count) = sin(pi, 0)

(x, count) = sin(pi/2, count)

(x, count) = sin(pi/4, count)

но это, очевидно, абсурдный способ.

Можно добавить в модуль глобальный счётчик:
sin_counter = 0

def sin(theta):

.... global sin_counter

.... sin_counter = sin_counter + 1

.... return _sin(theta)

x1 = sin(pi)

x2 = sin(pi/2)

x3 = sin(pi/4)

но такой подход (инъекция внешних зависимостей) считается абсолютно вредным.

Далее напрашивается классический вариант из объектно-ориентированного программирования: объявим класс sin и например метод compute(), который при каждом вызове вернёт значение синуса от аргумента, и при этом увеличит внутренний счётчик на единицу. Также понадобится метод get_count() для получения его значения.

Минус этого подхода, во-первых, в том, что даже для такой тривиальной задачи потребуется написать довольно много кода, объявить новый тип данных Sin, и хранить внутри него мутабельное значение, текущее состояние. А во-вторых, и это самое главное, если мы захотим таким же способом определить косинус, нам придётся либо копипастой создавать копию класса Sin, либо создавать иерархию и наследовать наши Sin и Cos.

А если нам далее потребуется строить из подобных классов цепочки вызовов, по которым нужна статистика, сколько раз в рамках такой цепочки было сделано вычислений? И в эти цепочки желательно также включать и совсем сторонние вычисления... Такая исходно совсем простая задача по мере развития требований резко усложняется практически на ровном месте. Как же тут можно подстелить побольше соломки?

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

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

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

Библиотека PyMonad предоставляет декоратор curry, который превращает обычную функцию в каррированную. Например, есть функция add, вычисляющая сумму своих аргументов:

from pymonad import curry

@curry

def add(x, y):

.... return x + yadd(2,3) # 5

Но так как add() каррированная, мы можем также записать

add(3)

Что она вычислит? Ничего, возвращена будет некая промежуточная функция, так как числа аргументов недостаточно для полного расчёта. В частности,

f = add(3)

type(f).__name__

вернёт Reader -- это специальный каррированный тип из PyMonad.

И тут сразу начинается магия!

В терминологии функционального программирования мы "замораживаем" аргумент 3, и дальше можем использовать такую промежуточную функцию, например, для увеличения другого аргумента на три:

add3 = add(3) # add3 - функция

Зато add3 мы можем использовать для финального вычисления:

add3(2) # 5

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

PyMonad не делает различия между их количеством, декоратор curry универсальный.

Пусть функция add_3() складывает все три свои аргумента:

@curry

def add_3(x, y, z):

.... return x + y + z

Можно вызвать её со всеми аргументами:
add_3(2,3,5)

и сразу получить 10. Либо можно частично её применить -- вызвать

add_3(2,3)

Сохраним такую функцию:
add23 = add_3(2,3)

Теперь функция add23() ожидает единственный, последний аргумент:
add23(5)

В результате мы получим 10.

Форма комбинации аргументов допускается произвольная!
add_3(2)(3,5)

add_3(2,3)(5)

add_3(2)(3)(5)

Композиция функций естественно расширяет принцип карринга.

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

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

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

@curry

def head(aList):

.... return aList[0]

@curry

def tail(aList):

.... return aList[1:]

lst = [1,2,3,4]

head(lst) # 1

tail(lst) # [2,3,4]

Тогда каррированная функция, являющаяся композицией этих функций, запишется так:
second = head * tail

Учитываем порядок вычислений справа налево! То есть сперва вызовется tail() и мы получим список без первого элемента, а затем к этому результату будет применена head() (изъятие первого элемента из этого промежуточного значения), которая по сути вернет второй элемент исходного списка.

Мы можем применить её к списку и получим второй элемент 2:
second(lst) # 2

Сперва функция tail выделит список [2, 3, 4], а потом из этого промежуточного значения функция head выделит первый элемент 2.

Схожим образом мы можем "составлять" и частично применяемые функции. Например, у нас есть функция сложения двух чисел add, и функция умножения двух чисел mul.
@curry

def add(x, y):

.... return x + y

@curry

def mul(x, y):

.... return x * y

Что будет, если мы скомпозируем их с частичным применением?
comp = add(7) * mul(2)

Порядок вычислений работает так же справа налево.

Вызовем comp(4). Сперва частично применённая функция mul(2) получит второй аргумент 4, после чего она вычислится полностью и выдаст результат 2*4=8.

Этот результат 8 поступит на вход частично применённой функции add(7), которая прибавит к 7 входное значение 8, и выдаст конечный результат 15.

Отмечу, что композиция частично применённых функций некоммутативна, то есть

f1 * f2 != f2 * f1

Это легко проверить:
comp2 = mul(2) * add(7)

Вызовем comp(4) -- сперва к 7 прибавится 4, результат 11 передастся функции mul(), которая умножит 11 на 2 и вернёт 22.

Однако нам более важна ассоциативность. Важно, что частично применённые функции условно можно считать ассоциативными:

f1 * f2 * f3 = (f1 * f2) * f3 = f1 * (f2 * f3)

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

Приближаемся к монадам. Сперва познакомимся с функторами.

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

Например

map((lambda x: x**2), [1,2,3])

вернёт [1,4,9]

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

Функтор -- это такой тип данных, к которому применима функция fmap(). Она применит поступившую ей на вход функцию к каждому элементу функтора, а сама его структура при этом сохранится.

Пока это определение абстрактно и не очень понятно, зачем функторы нужны на практике.

В пакете PyMonad определено несколько стандартных функторов, которые существуют практически во всех функциональных языках.

Это:

Just -- просто обёртка для скалярного значения, превращающая это значение в функтор;

Nothing -- условное обозначение отсутствия значения (или ошибочного значения);

List -- реализация контейнера для списка (по аналогии с Just).

Например:

Just(12) # функтор-обёртка для значения 12

List(1,2,3,4,5) # функтор-обёртка для списка [1,2,3,4,5]

Метод fmap() присущ функтору неотъемлемо. Композиция любой функции f(x) одного аргумента с функтором вернёт такой же функтор (точнее, экземпляр такого же типа), для каждого элемента которого применена эта функция f().

Определим простую функцию, меняющую знак аргумента:

from pymonad.Maybe import *

from pymonad.List import *

def neg(x):

.... return -x

Стоит теперь ей подать на вход один из наших функторов, как они отлично разберутся друг с другом и вернут корректный функтор!

Например:
neg * Just(5) # -5
neg * Nothing # Nothing
neg * List(1, 2, 3) # List(-1, -2, -3)

"*" -- это рассмотренная ранее операция композиции функций.

Другими словами, мы по сути вызываем

fmap( neg, List(1, 2, 3) )

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

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

Простая каррированная функция, складывающая два аргумента:
@curry

def add(x, y):

.... return x + y

add * Just(7) & Just(8)

Оператор & по сути разделяет аргументы левой функции.

Результатом станет сумма Just(15).

Если один из аргументов не определён, будет возвращен Nothing:
add * Nothing & Just(8) # Nothing

Это очень удобно, если например в процессе цепочки вычислений возникла ошибка, и какой-то промежуточный аргумент вычислить не удалось.

Интересно будут сложены списки:
add * List(1, 2) & List(3, 4)

Результатом будет List(4,5,5,6) -- к правому списку последовательно применяются элементы левого списка: (1+3,1+4,2+3,2+4).

Монада -- это тип, который позволяет строить цепочки вычислений. Между этими вычислениями передаются только монады, что и делает эти цепочки в некотором смысле универсальными. Традиционная операция шага такой цепочки называется bind, а обозначается в библиотеке PyMonad как оператор >>.

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

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

def positive_and_negative(x):

.... return List(x, -x)

Подадим на вход оператору >> функтор List (который всегда считается подмножеством монады, как и аппликативный функтор):

List(9) >> positive_and_negative

Результатом станет монада List(9, -9).

Для случаев, когда аргументов требуется несколько, задействуем аппликативные функторы:
@curry

def add_and_sub(x, y):

.... return List(y + x, y - x)

List(2) >> add_and_sub(3)

вернёт список List(5,-1)

add_and_sub() первым аргументом подцепит монаду List(2), которая в ходе вычислений и развернётся в результат.

Чуть более сложный пример:

List(2) >> positive_and_negative >> add_and_sub(3)

Результатом станет List(5, -1, 1, -5)

Сперва List(2) после обработки positive_and_negative превратится в List(2, -2), азатем функция add_and_sub преобразует эту промежуточную монаду-список, удвоив его:add_and_sub(List(2, -2), 3) # List(5, -1, 1, -5)

Из-за того, что функция должна иметь единственный аргумент, в чистых функциональных языках из монад обычно выстраиваются не очень наглядные цепочки. Например, чтобы с помощью монад сложить два числа 3 и 5 -- без создания внешних функций наподобие add(x,y), надо записать примерно следующее:

Just(3) >> (lambda x: Just(5) >> (lambda y: Just(x + y))) # Just(8)

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

Последнее, что нам осталось изучить -- это монады состояний. Они "оборачивают", в отличие от обычных монад-контейнеров значений, не данные, а наоборот -- функции. Причём не все функции, а только такие, которые получают на вход единственный параметр -- состояние (экземпляр любого определённого типа), а выдают список из двух элементов: некий результат своей работы и результирующее состояние (вспомним проблему с функциями Sin и Cos из первых уроков). Из этого описания практически сразу понятно, зачем нужны такие монады состояний: фактически, совершенно произвольная цепочка обработки входного состояния завершится предсказуемо и однозначно.

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

Рассмотрим оба случая для простого примера -- организации цепочки сложений и вычитаний с подсчётом количества вызовов этих операций.

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

@curry

def add(x, y):

.... return State(lambda old_state: (x + y, old_state + 1))
@curry

def subtract(y, x):

.... return State(lambda old_state: (x - y, old_state + 1))

Здесь возникает вопрос, как нам сформировать начальное значение для подобной цепочки, использующей State. Другими словами, монада должна уметь оборачивать сырое значение в себя. В функциональном программировании такую операцию обозначают return, и за счёт развитого полиморфизма специально её переопределять для каждого монадического класса не надо (компилятор поймёт тип возвращаемого значения по контексту). В Питоне с этим посложнее; в качестве return выступает метод unit(). Есть специальный синтаксический сахар -- самостоятельная функция unit().

Сконструируем с её помощью начальный объект для цепочки вычислений. Вот её итоговый пример:
x = unit(State, 1) >> add(2) >> add(4) >> subtract(16) >> add(8)

Результат цепочки, x -- это пока ещё не вычисленное значение, а функция, которую надо явно запустить на исполнение, прямым вызовом с начальным параметром нашего состояния (счётчика вызовов):
x(0)

Результатом вызова станет список (-1, 4).

1+2+4-16+8 = -1, и всего четыре раза мы вызывали bind (>>).

Такойже результат мы получим, если задействуем декоратор State:

@curry

def add2(x, y):

.... @State

.... def state_computation(old_state):

........ return (x+ y, old_state + 1)

.... return state_computation

@curry

def subtract2(y, x):

.... @State

.... def state_computation(old_state):

........ return (x - y, old_state + 1)

.... return state_computation

Эти два способа описания функций для монад состояний можно произвольно комбинировать друг с другом.