Monads in Python in more detail

    Good day!

    In the last topic, I tried to depict Maybe monad using Python. In general, the task was achieved, it seems to me, but it will not be easy for a person completely unfamiliar with the subject to understand what's what, and most importantly, why. This time I’ll try to dwell on monads in more detail, including to consolidate my own understanding.


    The material will largely repeat the individual chapters of Learn you a Haskell for great Good , but through the prism of my understanding and within the framework of the Python language. I highly recommend reading the book itself, even if you have no plans to write such a task in Haskell: your horizons will expand significantly. I'll start, perhaps.

    Context


    Quite often, data that is processed by programs is in some context. For simplicity, you can imagine it in the form of a box in which data is stored (although the “boxed" analogy is not entirely accurate, and sometimes even not applicable, but for now we will try to stick to it). For example, the list is quite similar to the box in which the items are. And the list forms a certain context - many operations designed to work with list items work with items as if they were obsessed with “boxes”, and not just with data as it is. The box for the data stored in the fields is the object to which these fields belong. A tree built on related objects is a container for data stored in its branches / leaves.
    In OOP, it is customary to encapsulate object data inside it, and access is recommended to be provided through object methods. It is difficult to unify methods of working with object data for objects of different classes, at least in the general case, but for objects that can be speculatively presented in the form of a context (“box”) in which the data is located, this is quite feasible.
    Sometimes you need to apply a simple function to the data, which can be universal enough to work with simple data types, but is unable to work with data inside the “box”.
    Example: on with a felt-tip pen and a box of paper, sticking a felt-tip pen into a box through a hole and trying to draw something there is pointless. The logical solution: get the data out of the box, apply a function to it, and put it back.
    So, if the box has a mechanism for applying the function to the content, our “box” becomes a functor .

    Functors


    So a functor is an implementation of a certain context in which the data is located, and you can get data to this data, apply a function to it, and put it back into context. Moreover, the function requires only the ability to work with the data itself, but not with the context.

    We implement the following prototype class:
    class Functor(Infixable):
        '''Прототип функтора'''
        def fmap(self, func):
            raise NotImplementedError() # в прототипе метод - абстрактный
    

    While you do not need to pay attention to the ancestor (Infixable), you can still consider the ancestor object.
    The mechanism for applying a function to data inside a functor is the fmap method.

    By the way, a list in Python is the most functor, and the mechanism for applying a function to the contents of a list is map (). map (abs, [-2, -1,0,1,2]) - this is the extraction of the elements of the list, applying the function to each, and putting it back into the list.
    Imagine the list as a functor:
    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
    

    Now you can do this:
    >>> print List(-2,-1,0,1,2).fmap(abs).fmap(lambda x: x*2).fmap(str).result
    ['4', '2', '0', '2', '4']
    


    In Haskell, the type system allows you to implement the Functor type class, and all data types that belong to this class (and they can and usually belong to several type classes). The type class method in use looks like a regular function:
    fmap abs [-2,-1,0,1,2]
    

    This is somewhat more aesthetic, but the Python version is applicable.

    Now we can apply a regular function to the data in context. But we may want to apply a function to the data in the context, which is also in the context (in the same as the data). Those. and the function above the data and the data are in context: both a felt-tip pen and pieces of paper in one box. You need to get a felt-tip pen, get a piece of paper, draw, put the result back. If our box can do this, it is an applicative functor .

    Here we digress and implement one auxiliary class, namely Infixable (the one that is in the ancestors of Functor). And he is needed to realize the possibility of using infix notation. so

    Infix notation


    There is no normal infix notation for custom functions in Python - the syntax is frozen. And sometimes I really want to implement something like:
    (/*/) = lambda x,y: (x + y) * (x - y)
    print 5 /*/ 4 /*/ 3
    

    Alas, no way. I wrote a class that allows you to use infix notation for object methods. The class itself:
    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
    

    The + operator is overloaded in this class, and all salt is contained in the attribute of the INFIX_OPS class. If a certain MyObj - a descendant of Infixable - implements the mmm (self, value) method and supplements INFIX_OPS with a dictionary of the form {'/ * /': 'mmm', ...}, this form of recording the sequence of operations on the instance will become possible:
    obj = MyObj() +'/*/+ 1 +'/*/'+ 2 +'/*/'+ 3
    

    Not very beautiful, but it works. Maybe then I will find an alternative.

    Applicative functors


    So, we need to implement getting the function and data out of the box, applying the function to the data and putting them back in and we get an applicative functor. We implement a suitable class. Moreover, we will have an ordinary functor, because it’s not bad to be able to draw on our pieces of paper and with an external felt-tip pen. So the class:
    class Applicative(Functor):
        INFIX_OPS = Functor.INFIX_OPS + [{
            '<*>': 'applicate'
        }]
        def applicate(self, value):
            raise NotImplementedError()
    

    The descendants of this class will receive the applicate (value) method and the infix operator for it is '<*>'. Replace the ancestor List
    class described above with Applicative and add an implementation of the new method. This will require an auxiliary function to lower the list nesting level ([[a, b], [c, d]] -> [a, b, c, d]). Function and class:
    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
    

    Now you can do this:
    >>> List(str).applicate(List(1,2,3,4,5)).result
    ['1', '2', '3', '4', '5']
    

    Here we have in the context a function that we apply to the data in the context (in the list).
    But, and this is the most interesting, you can do this (at the same time apply infix notation):
    >>> print (
    ...     List(str, abs) +'<*>'+ List(-10, -20)
    ... ).result
    ['-10', '-20', 10, 20]
    

    We got the results of applying all the functions to all parameters. And you can do this:
    >>> 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]
    

    First, all the functions of the two arguments are applied to all the first arguments. Functions are curried and return the functions of the second argument, which apply to all second arguments!

    Now we are able to put functions in context and apply to values ​​in context: on each leaflet in the box, draw each felt-tip pen out of the box, taking out the felt-tip pens, which are removed only after they are drawn on each piece of paper.

    Now imagine the situation: we want to implement streaming production of drawings. Suppose we have input sheets, they are put in a box to get the initial context. Further, each workplace on the line is a function that can take an object previously taken out of the box, do something with it and put it in a new box (context). The function itself does not take data from the box, because he doesn’t know how to choose them correctly, and indeed it’s easier - they gave it and processed it, and putting it into a new empty box doesn’t need much mind.
    It turns out that each operation is interface unified: data taken out -> processing -> box with the results. We only need to implement getting data from the previous box and applying functions to them to get a new box.
    A function that takes a normal value and returns the result in context ( monadic value ) is called a monadic function . And an applicative functor that can take a simple value and pass through a chain of monad functions is the monad .

    Monads


    Monotype class prototype:
    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()
    

    The monad provides 2 methods bind (>> =) and then (>>).
    bind () gets the value from the context, passes to the monad function, which returns the next value in the context (monad value).
    then () discards the previous monad value, calls a function with no arguments, which returns the new monad value.

    Monad List


    Now, the full implementation of the List monad loomed before us :
    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 “pulls” a regular function into context: a “retracted” function returns a monad value.

    And here is an example of using a list as a monad: the task is to check whether it is possible to reach the second indicated point from one specified point on the chessboard in exactly 3 moves with the knight.
    # все точки, достижимые шахматным конем из указанной точки
    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 Monad


    Maybe monad implements a context in which the monadic value characterizes one of two states:
    - the previous step completed successfully, with some value (just x)
    - the previous step failed (nothing)

    In this case, the sequence of calculations in the context of the Maybe monad is a sequence of steps, each of which relies on the result of the previous one, while any step may fail, which will mean an unsuccessful completion of the entire sequence. In the Maybe context, if an unsuccessful result is obtained at any step, the subsequent steps are skipped as meaningless.
    As a Maybe functor, they will apply a function to the value through fmap, if there is a value, there is no value (unsuccessful result) - so the function has nothing to apply to, well, it does not apply!

    If there is a function inside the Maybe-context and arguments inside Maybe (Maybe, like an applicative functor), then the function will be applied if it is and there are all arguments, otherwise the result will immediately fail.

    Maybe Monad Class:
    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) and nothing () are simply shorthand for easier creation of corresponding monad values. liftMaybe - “pulling” into the Maybe context.

    Examples of use as a functor and applicative functor:
        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)
    )
    


    Let me give you an example of using Maybe as monads. A tightrope walker walks along a rope with a pole, but birds like to sit on a pole, and then they can fly away. The tightrope walker can keep his balance if the difference in the number of birds on the sides of the pole is no more than 4. Well, the tightrope walker can just fall slipping on a banana peel. It is necessary to simulate a sequence of events with the output in the form of “fell” / “did not fall”. The code:
    # посадка птиц на левую сторону
    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)
    )
    


    Instead of an afterword

    Similarly, you can implement other famous monads, or some of your own.
    You can only make a functor, but, for example, for a tree on related objects.

    Note

    I deliberately did not touch on the topic of monad laws, it is important, but the topic was already voluminous. There will be something to tell next time.

    Changed

    Thanks to the comment (thanks, funca) I eliminated the contradiction regarding the values ​​returned by the monad functions in the context of the List monad. Now they should return exactly the List instance as the result.

    A new version

    Lies here .
    Description of changes:
    - The possibility of infix recording is removed - it looks very bad
    - Methods of functors and monads now return new context values, and do not change the inplace context.
    - List monad is now an inheritor of the list. So the monadic result is also a list. T.O. You can write modifying monad functions that return a list. Only one generating function at the beginning of the monadic sequence is necessary and sufficient.

    Also popular now: