Monads in Python in detail
Good day!
In the past topic, I tried to portray the Maybe monad using Python tools. In general, the task was achieved, it seems to me, but it would be difficult for a person completely unfamiliar with the subject to understand what was happening, and most importantly - why. This time I will try to dwell on the monads in more detail, including to consolidate my own understanding.
The material will largely repeat the individual chapters of the book Learn you a Haskell for great Good , but through the lens of my understanding and within the framework of the Python language. I highly recommend the book itself for reading, even if you don’t have such a task in your plans - write in Haskell: it will broaden the horizons considerably. I'll start, perhaps.
')
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 inapplicable, but for now we will try to stick to it). For example, the list is quite similar to the box in which the elements lie. And the list forms a certain context - many operations designed to work with list items work with elements as if they are obsessed with boxes, and not just as they are with data. 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 data of an object inside it, and access is recommended to be provided through object methods. Methods of working with data objects are difficult to unify 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 are located, this is quite feasible.
Sometimes you need to apply a simple function to the data, which can be quite versatile to work with simple data types, but is unable to work with the data inside the “box”.
Example: there is a felt-tip pen and a box with paper on it, to put the marker into the box through the hole and there is no point in trying to draw something there. 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 .
So a functor is an implementation of a certain context in which the data is located, and you can get to this data, apply a function to it, and put it back into the 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:
While you do not need to pay attention to the ancestor (Infixable), you can still be considered the ancestor of object.
The mechanism for applying a function to data inside a functor is the fmap method.
By the way, the list in Python is the most that is not a functor, and the mechanism for applying a function to the contents of a list is map (). map (abs, [-2, -1,0,1,2]) is the extraction of list items, applying a function to each, and putting it back into the list.
Imagine the list as a functor:
Now you can do this:
In Haskell, the type system allows you to implement the Functor type class, and all data types belonging to this class (and they can belong to and usually belong to several type classes). The type class method in use looks like a regular function:
This is a bit more aesthetic, but the Python version is applicable.
Now we can apply the normal function to the data in the context. But we may want to apply a function to the data in the context, which is also in the context (in the same way as the data). Those. and the function above the data and the data are in context: both the pen and the pieces of paper in one box. You need to get a marker, 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 stands in the ancestors of the Functor). And he needs to implement the possibility of using infix notation. so
Normal Python infix notation for user-defined functions cannot be obtained - the syntax is frozen. And sometimes you really want to implement something like:
Alas, no way. I wrote a class that allows you to use infix notation for object methods. The class itself:
In this class, the "+" operator is overloaded, and the whole salt is contained in the INFIX_OPS class attribute. If a certain MyObj, a descendant of Infixable, implements the mmm (self, value) method and complements INFIX_OPS with a dictionary like {'/ * /': 'mmm', ...}, this form of writing a sequence of operations on an instance will be possible:
Not very nice, but it works. Can then find an alternative.
So, we need to implement taking functions and data out of the box, applying the function to the data and putting them back, and we get an applicative functor. We implement a suitable class. Moreover, our ancestor will have an ordinary functor, because it is not bad to be able to draw on our pieces of paper and with an external felt-tip pen. So, the class:
The descendants of this class will receive the applicate method (value) and the infix operator for it '<*>'.
Replace the ancestor of Applicant with the above described List class and add the implementation of the new method. This will require the auxiliary function of lowering the list nesting level ([[a, b], [c, d]] -> [a, b, c, d]). Function and class:
Now you can do this:
Here we have in context a function that we apply to data in the context of the same (listed).
But, and this is the most interesting, you can do this (at the same time we apply infix notation):
We obtained the results of applying all functions to all parameters. And it is possible and so:
First, all functions of the two arguments are applied to all first arguments. Functions are curried and return functions of the second argument that apply to all second arguments!
Now we are able to put functions in context and apply to values ​​in context: on each piece of paper in a box we draw each felt-tip pen out of the box, alternately taking out markers that are removed only after we draw on each piece of paper.
Now imagine a situation: we want to implement streaming production of drawings. Suppose we have input sheets, they are placed 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 does not know how to choose them correctly, and it is simpler to do that - they have given it and process it, but to put it in a new empty box - you don’t need a lot of mind.
It turns out that each operation is interface-standardized: the extracted data -> processing -> box with the results. We only need to implement the retrieval of data from the previous box and apply functions to it to get a new box.
A function that takes a normal value and returns the result in a context ( monadic value ) is called a monadic function . And an applicative functor that can take a simple value and pass through a chain of monadic functions is a monad .
Prototype monad class:
Monad provides 2 methods bind (>> =) and then (>>).
bind () takes a value out of context, passes a monad function, which returns the next value in the context (monad value).
then () discards the previous monad value, calls the function with no arguments, which returns the new monad value.
Now we see the complete implementation of the List monad :
liftList “pulls in” a normal function into context: a “pulled in” function returns a monad value
And here is an example of using the list as a monad: the task is to check whether it is possible to reach the second specified point from exactly one point on the chess board in exactly 3 knight moves.
The Maybe monad implements a context in which a monadic value characterizes one of two states:
- the previous step was completed successfully, with some value (just x)
- the previous step failed (nothing)
In this case, the sequence of calculations in the context of the monad. Maybe is a sequence of steps, each of which is based on the result of the previous one, and any step can fail unsuccessfully, which means that the entire sequence has failed. In the context of Maybe, if at any step an unfortunate result is obtained, the subsequent steps are skipped as meaningless.
As a functor, Maybe, using fmap, will apply a function to a value, if there is a value, there is no value (bad result) - there’s nothing to apply the function to, well, it doesn’t apply!
If the function is inside the Maybe context and the arguments are inside Maybe (Maybe, as an applicative functor), then the function will be applied if it is and is all the arguments, otherwise the result will immediately fail.
Maybe monad class:
just (x) and nothing () are just abbreviations for easier creation of the corresponding monadic values. liftMaybe - “pulling in” the context of Maybe.
Examples of use as a functor and applicative functor:
I will give an example of using Maybe as a monad. A ropewalker walks a rope with a pole, but birds like to sit on a pole, and then they can fly away. A tightrope walker can keep balance if the difference in the number of birds on the sides of a pole is no more than 4. Well, the tightrope walker can simply fall off slipping on a banana peel. It is necessary to simulate a simulation of a sequence of events with the output of the result in the form of "fell" / "did not fall." Code:
Similarly, you can implement other known monads, or some of their own.
You can only make a functor, but, for example, for a tree on related objects.
I deliberately did not touch on the topic of monad laws, it is important, but the topic is already voluminous. There will be something to tell next time.
Thanks to the comment (thanks, funca), I resolved the contradiction regarding the values ​​returned by monad functions in the context of the List monad. Now they must return exactly the List instance as a result.
Lies here .
Description of the changes:
- The possibility of infix notation is removed - it looks very bad
- Functors and monads methods now return new context values, rather than changing the inplace context.
- Monad List is now a list heir. So the monad result is also a list. So it is possible to write changing monad functions returning a list. Only one generating function at the beginning of the monad sequence is necessary and sufficient.
In the past topic, I tried to portray the Maybe monad using Python tools. In general, the task was achieved, it seems to me, but it would be difficult for a person completely unfamiliar with the subject to understand what was happening, and most importantly - why. This time I will try to dwell on the monads in more detail, including to consolidate my own understanding.
The material will largely repeat the individual chapters of the book Learn you a Haskell for great Good , but through the lens of my understanding and within the framework of the Python language. I highly recommend the book itself for reading, even if you don’t have such a task in your plans - write in Haskell: it will broaden the horizons considerably. 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 inapplicable, but for now we will try to stick to it). For example, the list is quite similar to the box in which the elements lie. And the list forms a certain context - many operations designed to work with list items work with elements as if they are obsessed with boxes, and not just as they are with data. 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 data of an object inside it, and access is recommended to be provided through object methods. Methods of working with data objects are difficult to unify 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 are located, this is quite feasible.
Sometimes you need to apply a simple function to the data, which can be quite versatile to work with simple data types, but is unable to work with the data inside the “box”.
Example: there is a felt-tip pen and a box with paper on it, to put the marker into the box through the hole and there is no point in trying to draw something there. 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 to this data, apply a function to it, and put it back into the 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 be considered the ancestor of object.
The mechanism for applying a function to data inside a functor is the fmap method.
By the way, the list in Python is the most that is not a functor, and the mechanism for applying a function to the contents of a list is map (). map (abs, [-2, -1,0,1,2]) is the extraction of list items, applying a 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 belonging to this class (and they can belong to 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 a bit more aesthetic, but the Python version is applicable.
Now we can apply the normal function to the data in the context. But we may want to apply a function to the data in the context, which is also in the context (in the same way as the data). Those. and the function above the data and the data are in context: both the pen and the pieces of paper in one box. You need to get a marker, 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 stands in the ancestors of the Functor). And he needs to implement the possibility of using infix notation. so
Infix notation
Normal Python infix notation for user-defined functions cannot be obtained - the syntax is frozen. And sometimes you 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 In this class, the "+" operator is overloaded, and the whole salt is contained in the INFIX_OPS class attribute. If a certain MyObj, a descendant of Infixable, implements the mmm (self, value) method and complements INFIX_OPS with a dictionary like {'/ * /': 'mmm', ...}, this form of writing a sequence of operations on an instance will be possible:
obj = MyObj() +'/*/+ 1 +'/*/'+ 2 +'/*/'+ 3 Not very nice, but it works. Can then find an alternative.
Applicative Functors
So, we need to implement taking functions and data out of the box, applying the function to the data and putting them back, and we get an applicative functor. We implement a suitable class. Moreover, our ancestor will have an ordinary functor, because it is 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 method (value) and the infix operator for it '<*>'.
Replace the ancestor of Applicant with the above described List class and add the implementation of the new method. This will require the auxiliary function of lowering 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 context a function that we apply to data in the context of the same (listed).
But, and this is the most interesting, you can do this (at the same time we apply infix notation):
>>> print ( ... List(str, abs) +'<*>'+ List(-10, -20) ... ).result ['-10', '-20', 10, 20] We obtained the results of applying all functions to all parameters. And it is possible and so:
>>> 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 functions of the two arguments are applied to all first arguments. Functions are curried and return functions of the second argument that apply to all second arguments!
Now we are able to put functions in context and apply to values ​​in context: on each piece of paper in a box we draw each felt-tip pen out of the box, alternately taking out markers that are removed only after we draw on each piece of paper.
Now imagine a situation: we want to implement streaming production of drawings. Suppose we have input sheets, they are placed 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 does not know how to choose them correctly, and it is simpler to do that - they have given it and process it, but to put it in a new empty box - you don’t need a lot of mind.
It turns out that each operation is interface-standardized: the extracted data -> processing -> box with the results. We only need to implement the retrieval of data from the previous box and apply functions to it to get a new box.
A function that takes a normal value and returns the result in a context ( monadic value ) is called a monadic function . And an applicative functor that can take a simple value and pass through a chain of monadic functions is a monad .
Monads
Prototype monad class:
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() Monad provides 2 methods bind (>> =) and then (>>).
bind () takes a value out of context, passes a monad function, which returns the next value in the context (monad value).
then () discards the previous monad value, calls the function with no arguments, which returns the new monad value.
Monad List
Now we see the complete implementation of the List monad :
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 in” a normal function into context: a “pulled in” function returns a monad value
And here is an example of using the list as a monad: the task is to check whether it is possible to reach the second specified point from exactly one point on the chess board in exactly 3 knight moves.
# , 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)) # Monad Maybe
The Maybe monad implements a context in which a monadic value characterizes one of two states:
- the previous step was completed successfully, with some value (just x)
- the previous step failed (nothing)
In this case, the sequence of calculations in the context of the monad. Maybe is a sequence of steps, each of which is based on the result of the previous one, and any step can fail unsuccessfully, which means that the entire sequence has failed. In the context of Maybe, if at any step an unfortunate result is obtained, the subsequent steps are skipped as meaningless.
As a functor, Maybe, using fmap, will apply a function to a value, if there is a value, there is no value (bad result) - there’s nothing to apply the function to, well, it doesn’t apply!
If the function is inside the Maybe context and the arguments are inside Maybe (Maybe, as an applicative functor), then the function will be applied if it is and is all the 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 just abbreviations for easier creation of the corresponding monadic values. liftMaybe - “pulling in” the context of Maybe.
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) ) I will give an example of using Maybe as a monad. A ropewalker walks a rope with a pole, but birds like to sit on a pole, and then they can fly away. A tightrope walker can keep balance if the difference in the number of birds on the sides of a pole is no more than 4. Well, the tightrope walker can simply fall off slipping on a banana peel. It is necessary to simulate a simulation of a sequence of events with the output of the result in the form of "fell" / "did not fall." 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 epilogue
Similarly, you can implement other known monads, or some of their 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 is already voluminous. There will be something to tell next time.
Changed
Thanks to the comment (thanks, funca), I resolved the contradiction regarding the values ​​returned by monad functions in the context of the List monad. Now they must return exactly the List instance as a result.
A new version
Lies here .
Description of the changes:
- The possibility of infix notation is removed - it looks very bad
- Functors and monads methods now return new context values, rather than changing the inplace context.
- Monad List is now a list heir. So the monad result is also a list. So it is possible to write changing monad functions returning a list. Only one generating function at the beginning of the monad sequence is necessary and sufficient.
Source: https://habr.com/ru/post/138676/
All Articles