Python
February 2012 22

Монады в Python поподробнее

Доброго времени суток!

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


Материал будет во многом повторять отдельные главы книги Learn you a Haskell for great Good, но сквозь призму моего понимания и в рамках языка Python. Саму книгу я настоятельно рекомендую к прочтению, даже если у Вас и в планах нет такой задачи — писать на Haskell: кругозор расширит значительно. Начну, пожалуй.

Контекст


Довольно часто данные, которые подвергаются обработке программами находятся в некотором контексте. Для простоты можно представить себе его в виде некоторой коробки, в которой данные хранятся (хотя «коробочная» аналогия не совсем точна, и иногда даже неприменима, но пока мы попробуем её придерживаться). Например, список, вполне, похож на коробку, в которой лежат элементы. И список образует некий контекст — многие операции, предназначенные для работы с элементами списка, работают с элементами, как с одержимым «коробки», а не просто с данными как есть. Коробкой для данных, хранимых в полях, является и объект, которому эти поля принадлежат. Дерево, построенное на связанных объектах, является контейнером для данных, хранящихся в его ветках/листьях.
В ООП принято инкапсулировать данные объекта внутри него, а доступ рекомендуется предоставлять через методы объекта. Методы работы с данными объектов сложно унифицировать для объектов разных классов, по крайней мере в общем случае, но для объектов, которые могут быть умозрительно представлены в виде контекста («коробки»), в котором находятся данные, это, вполне, осуществимо.
Иногда к данным нужно применить простую функцию, которая может быть достаточно универсальна для работы с простыми типами данных, но неспособна работать с данными внутри «коробки».
Пример: у на с есть фломастер и коробка с бумагой, совать фломастер в коробку через дырку и что-то там пытаться нарисовать бессмысленно. Логичное решение: достать данные из коробки, применить к ним функцию, и положить обратно.
Так вот, наличии у коробки механизма применения функции к содержимому, наша «коробка» становится функтором.

Функторы


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

Реализуем следующий класс-прототип:
class Functor(Infixable):
    '''Прототип функтора'''
    def fmap(self, func):
        raise NotImplementedError() # в прототипе метод - абстрактный

Пока не нужно обращать внимание на предка (Infixable), можно пока считать предком object.
Механизм применения функции к данным внутри функтора — метод fmap.

Кстати, список в Python, это самый, что ни на есть, функтор, а механизм применения функции к содержимому списка — map(). map(abs, [-2,-1,0,1,2]) — это извлечение элементов списка, применение функции к каждому, и помещение обратно в список.
Представим список в виде функтора:
class List(Functor):

    def __init__(self, *items):
        super(List, self).__init__()
        self._items = items

    def fmap(self, func):
        self._items = map(func, self._items) # а внутри у него - неонка, т.е. map()
        return self

    @property
    def result(self):
        return self._items

Теперь можно делать так:
>>> print List(-2,-1,0,1,2).fmap(abs).fmap(lambda x: x*2).fmap(str).result
['4', '2', '0', '2', '4']


В Haskell система типов позволяет реализовать класс типов Functor, и все типы данных, принадлежащие к этому классу (а они могут принадлежать и, обычно, принадлежат к нескольким классам типов). Метод класса типов в использовании выглядит как обычная функция:
fmap abs [-2,-1,0,1,2]

Это несколько эстетичнее, но и Python-вариант применим.

Теперь мы можем применять обычную функцию к данным в контексте. Но у нас может возникнуть желание применять к данным в контексте функцию, которая тоже в контексте (в таком, же, что и данные). Т.е. и функция над данными и данные находятся в контексте: и фломастер и бумажки в одной коробке. Нужно достать фломастер, достать бумажку, нарисовать, положить результат обратно. Если наша коробка такое умеет — она аппликативный функтор.

Тут мы отвлечемся и реализуем один вспомогательный класс, а именно Infixable (тот, что стоит в предках у Functor). А нужен он для реализации возможности использования инфиксной нотации. Итак

Инфиксная нотация


Нормальной инфиксной нотации для пользовательских функций в Python не получить — синтаксис заморожен. А иногда очень хочется реализовать что-то вроде:
(/*/) = lambda x,y: (x + y) * (x - y)
print 5 /*/ 4 /*/ 3

Увы, никак. Я написал класс, который позволяет использовать инфиксную нотацию для методов объекта. Сам класс:
class Infixable(object):

    INFIX_OPS = [{}]

    def __init__(self):
        self._last_is_opcode = False
        self._op = None

        table = {}
        for sub_table in self.INFIX_OPS:
            table.update(sub_table)
        self._op_table = table

    def __add__(self, val):
        if self._last_is_opcode:
            method = getattr(self, self._op_table[self._op])
            method(val)
        else:
            self._op = val
        self._last_is_opcode = not self._last_is_opcode
        return self

В этом классе перегружен оператор "+", а вся соль содержится в атрибуте класса INFIX_OPS. Если некий MyObj — потомок Infixable — реализует метод mmm(self, value) и дополнит INFIX_OPS словарем вида { '/*/': 'mmm',… }, станет возможной такая форма записи последовательности операций над экземпляром:
obj = MyObj() +'/*/+ 1 +'/*/'+ 2 +'/*/'+ 3

Не очень красиво, но работает. Может потом найду альтернативу.

Аппликативные функторы


Итак, нам нужно реализовать доставание функции и данных из коробки, применение функции к данным и помещение их обратно и мы получим аппликативный функтор. Реализуем подходящий класс. Причем, предком у нас будет функтор обыкновенный, ведь неплохо иметь возможность порисовать на наших бумажках и внешним фломастером. Итак, класс:
class Applicative(Functor):

    INFIX_OPS = Functor.INFIX_OPS + [{
        '<*>': 'applicate'
    }]

    def applicate(self, value):
        raise NotImplementedError()

Потомки этого класса получат метод applicate(value) и инфиксный оператор для него '<*>'.
Заменим у выше описанного класса List предка на Applicative и допишем реализацию нового метода. Это потребует вспомогательной функции понижения уровня вложенности списка ( [[a, b], [c, d]] -> [a,b,c,d] ). Функция и класс:
def _concat(lists):
    return reduce(lambda x, y: x + y, lists, [])

class List(Applicative):

    ... # тут все методы из реализации List, как Functor
 
    def applicate(self, value): # value - данные в контексте (тут - в списке)
        self._items = _concat([
            map(fn, value._items)
            for fn in self._items
        ])
        return self

Теперь можно делать так:
>>> List(str).applicate(List(1,2,3,4,5)).result
['1', '2', '3', '4', '5']

Тут у нас в контексте функция, которую мы применяем к данным в контексте же (в списке).
Но, и это самое интересное, можно делать так (заодно применим инфиксную нотацию):
>>> print (
...     List(str, abs) +'<*>'+ List(-10, -20)
... ).result
['-10', '-20', 10, 20]

Мы получили результаты применения всех функций ко всем параметрам. А можно и так:
>>> add = lambda x: lambda y: x + y # каррированное сложение
>>> mul = lambda x: lambda y: x * y # каррированное умножение
>>> print (
...     List(add, mul) +'<*>'+ List(1, 2) +'<*>'+ List(10, 100)
... ).result
[11, 101, 12, 102, 10, 100, 20, 200]

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

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

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

Монады


Прототип класса монад:
class Monad(Applicative):

    INFIX_OPS = Applicative.INFIX_OPS + [{
        '>>=': 'bind',
        '>>': 'then',
    }]

    def bind(self, monad_func):
        raise NotImplementedError()

    def then(self, monad_func):
        raise NotImplementedError()

    @property
    def result(self):
        raise NotImplementedError()

Монада предоставляет 2 метода bind (>>=) и then (>>).
bind() достает значение из контекста, передает монадной функции, которая возвращает следующее значение в контексте (монадное значение).
then() отбрасывает предыдущее монадное значение, вызывает функцию без аргументов, которая возвращает новое монадное значение.

Монада List


Вот теперь перед нами вырисовалась полная реализация монады List:
def _concat(lists):
    return reduce(lambda x, y: x + y, lists, [])

class List(Monad):

    def __init__(self, *items):
        super(List, self).__init__()
        self._items = items


    def fmap(self, func):
        self._items = map(func, self._items)
        return self


    def applicate(self, monad_value):
        self._items = _concat([
            map(fn, monad_value._items)
            for fn in self._items
        ])
        return self


    def bind(self, monad_func):
        self._items = _concat(map(lambda x: monad_func(x)._items, self._items))
        return self

    def then(self, monad_func):
        self._items = monad_func()._items
        return self


    @property
    def result(self):
        return self._items

liftList = lambda fn: lambda x: List( *(fn(x)) )

liftList «втягивает» обычную функцию в контекст: «втянутая» функция возвращает монадное значение

А вот пример использования списка как монады: задача — проверить, можно ли из одной указанной точки на шахматной доске достигнуть второй указанной точки ровно за 3 хода конём.
# все точки, достижимые шахматным конем из указанной точки
raw_jumps = lambda (x, y): List(
    (x + 1, y + 2),
    (x + 1, y - 2),
    (x - 1, y + 2),
    (x - 1, y - 2),
    (x + 2, y + 1),
    (x + 2, y - 1),
    (x - 2, y + 1),
    (x - 2, y - 1),
)
# отбрасывание точек, выходящих за пределы доски
if_valid = lambda (x, y): List( (x, y) ) if 1 <= x <= 8 and 1 <= y <= 8 else List()

# ход конём из точки во всё возможные допустимые точки
jump = lambda pos: List(pos) +'>>='+ raw_jumps +'>>='+ if_valid

# проверка, можно ли достичь некоторой точки шахматной доски
# из исходной ровно за 3 хода коня
in3jumps = lambda pos_from, pos_to: pos_to in (
    List(pos_from) +'>>='+ jump +'>>='+ jump +'>>='+ jump
).result

print in3jumps((3,3), (5,1)) # нельзя
print in3jumps((3,3), (5,2)) # можно


Монада Maybe


Монада Maybe реализует контекст, в котором монадное значение характеризует одно из двух состояний:
— предыдущий шаг завершился удачно, с некоторым значением (just x)
— предыдущий шаг завершился неудачно (nothing)

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

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

Класс монады Maybe:
class Maybe(Monad):

    def __init__(self, just=None, nothing=False):
        super(Maybe, self).__init__()
        self._just = just
        self._nothing = nothing


    def fmap(self, func):
        if not self._nothing:
            self._just = func(self._just)
        return self


    def applicate(self, monad_value):
        if not self._nothing:
            assert isinstance(monad_value, Maybe)
            app_nothing, just = monad_value.result
            if app_nothing:
                self._nothing = True
            else:
                self._just = self._just(just)
        return self


    def bind(self, monad_func):
        if not self._nothing:
            monad_value = monad_func(self._just)
            assert isinstance(monad_value, Maybe)
            nothing, just = monad_value.result
            if nothing:
                self._nothing = True
            else:
                self._just = just
        return self


    def then(self, monad_func):
        monad_value = monad_func()
        assert isinstance(monad_value, Maybe)
        self._nothing, just = monad_value.result
        if not self._nothing:
            self._just = just
        return self


    @property
    def result(self):
        return (self._nothing, self._just)


just = lambda x: Maybe(just=x)
nothing = lambda: Maybe(nothing=True)

liftMaybe = lambda fn: lambda x: just(fn(x))


just(x) и nothing() это просто сокращения для более простого создания соответствующих монадных значений. liftMaybe — «втягивание» в контекст Maybe.

Примеры использования в качестве функтора и аппликативного функтора:
    def showMaybe(maybe):
        nothing, just = maybe.result
        if nothing:
            print "Nothing!"
        else:
            print "Just: %s" % just

# ==== Maybe as functor ====
showMaybe(
    just(-3).fmap(abs)
)

# ==== Maybe as applicative functor ====
add = lambda x: lambda y: x+y
# нет функции - нет результата
showMaybe(
    nothing() +'<*>'+ just(1) +'<*>'+ just(2)
)
# нет хотя бы одного аргумента - нет результата
showMaybe(
    just(add) +'<*>'+ nothing() +'<*>'+ just(2)
)
showMaybe(
    just(add) +'<*>'+ just(1) +'<*>'+ nothing()
)
# если всё есть - будет и результат
showMaybe(
    just(add) +'<*>'+ just(1) +'<*>'+ just(2)
)


Приведу пример использования Maybe, как монады. Некий канатоходец ходит по канату с шестом, но на шест любят садиться птицы, а потом могут и улететь. Канатоходец может держать равновесие, если разность кол-ва птиц на сторонах шеста не более 4. Ну и канатоходец просто может упасть подскользнувшись на банановой кожуре. Нужно смоделировать симуляцию последовательности событий с выдачей результата в виде «упал»/«не упал». Код:
# посадка птиц на левую сторону
to_left = lambda num: lambda (l, r): (
    nothing()
    if abs((l + num) - r) > 4
    else just((l + num, r))
)

# посадка птиц на правую сторону
to_right = lambda num: lambda (l, r): (
    nothing()
    if abs((r + num) - l) > 4
    else just((l, r + num))
)

# банановая кожура
banana = lambda x: nothing()

# отображение результата
def show(maybe):
    falled, pole = maybe.result
    print not falled

# начальное состояние
begin = lambda: just( (0,0) )

show(
    begin()
    +'>>='+ to_left(2)
    +'>>='+ to_right(5)
    +'>>='+ to_left(-2) # канатоходец упадёт тут
)
show(
    begin()
    +'>>='+ to_left(2)
    +'>>='+ to_right(5)
    +'>>='+ to_left(-1)
) # в данном случае всё ок
show(
    begin()
    +'>>='+ to_left(2)
    +'>>='+ banana # кожура всё испортит
    +'>>='+ to_right(5)
    +'>>='+ to_left(-1)
)


Вместо послесловия

Подобным образом можно реализовать и другие известные монады, или какие-то свои.
Можно сделать только функтор, но, например, для дерева на связанных объектах.

Примечание

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

Изменено

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

Новая версия

Лежит тут.
Описание изменений:
— Убрана возможность инфиксной записи — совсем плохо смотрится
— Методы функторов и монад теперь возвращают новые значения контекста, а не изменяют контекст inplace.
— Монада List теперь является наследником списка. А значит монадный результат — тоже список. Т.о. можно писать изменяющие монадные функции возвращающими список. Необходима и достаточна только одна порождающая функция в начале монадной последовательности.
+34
7.7k 115
Comments 18
Top of the day