Доброго времени суток!
В прошлом топике я попробовал изобразить монаду 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) for fn in self._items ]) return self Теперь можно делать так:
>>> List(str).applicate([1,2,3,4,5]).result ['1', '2', '3', '4', '5'] Тут у нас в контексте функция, которую мы применяем к данным в контексте же (в списке).
Но, и это самое интересное, можно делать так (заодно применим инфиксную нотацию):
>>> print ( ... List(str, abs) +'<*>'+ [-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) +'<*>'+ [1, 2] +'<*>'+ [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) for fn in self._items ]) return self def bind(self, monad_func): self._items = _concat(map(monad_func, self._items)) return self def then(self, monad_func): self._items = monad_func() return self @property def result(self): return self._items liftList = lambda fn: lambda x: [fn(x)] liftList «втягивает» обычную функцию в контекст: «втянутая» функция возвращает монадное значение
А вот пример использования списка как монады: задача — проверить, можно ли из одной указанной точки на шахматной доске достигнуть второй указанной точки ровно за 3 хода конём.
# все точки, достижимые шахматным конем из указанной точки raw_jumps = lambda (x, y): [ (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): [(x, y)] if 1 <= x <= 8 and 1 <= y <= 8 else [] # ход конём из точки во всё возможные допустимые точки jump = lambda pos: ( List(pos) +'>>='+ raw_jumps +'>>='+ if_valid ).result # проверка, можно ли достичь некоторой точки шахматной доски # из исходной ровно за 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) ) Вместо послесловия
Подобным образом можно реализовать и другие известные монады, или какие-то свои.
Можно сделать только функтор, но, например, для дерева на связанных объектах.
Примечание
Я намеренно не затрагивал тему монадных законов, она важная, но топик и так объемистый вышел. Будет, что рассказать в следующий раз.
Автор: Astynax
