## 2016年8月10日 星期三

### [Python 文章收集] Monads, part 1: a design pattern

Source From Here
Preface
The use of monads can be thought of as a design pattern that allows us to redefine how function composition works. Before we define what a monad is, let’s develop our intuition with some motivational examples.

Example 1: exception handling (a.k.a. “Maybe”)
To get our feet wet, let’s use a purely functional subset of Python to describe a function which computes the quotient of 100 and some divisor. In the special case where the divisor is zero, we’ll return None
1. def divide100(divisor):
2.     if divisor == 0:
3.         return None
4.     else:
5.         return 100 / divisor
Let’s also write a function to compute the square root of a number. If the input is negative, we’ll return None
1. def sqrt(x):
2.     if x < 0:
3.         return None
4.     else:
5.         return x ** 0.5
Can we compose these functions? What if we wanted to compute something like sqrt(divide100(sqrt(x)))? That would work as long as x is positive. If we explicitly handle the case when any of those functions returns None, the code becomes much longer:
1. a = sqrt(x)
2. if a is not None:
3.     b = divide100(a)
4.     if b is not None:
5.         c = sqrt(b)
You can imagine how tedious it would be if we had to do manual error checking like this for all of our function calls. Perhaps a better solution is to rewrite divide100 and sqrt such that they each do the error handling themselves. For example, we might modify them as follows:
1. def composable_divide100(divisor):
2.     if divisor is None or divisor == 0:
3.         return None
4.     else:
5.         return 100 / divisor
6.
7. def composable_sqrt(x):
8.     if x is None or x < 0:
9.         return None
10.     else:
11.         return x**0.5
Now we can evaluate expressions like composable_sqrt(composable_divide100(composable_sqrt(x))). When x <= 0, the entire expression evaluates to None just as we would expect. Rather than modifying all of our functions to check forNone, let’s write a wrapper function (let’s call it bind) to do the error handling for us. It takes a value (either a number or None) and a function (such as divide100 or sqrt) and applies the function to that value. If the input is None, we skip the function application and just return None
1. def bind(x, f):
2.     if x is None:
3.         return None
4.     else:
5.         return f(x)
Now we can compose these functions like: bind(bind(bind(x, sqrt), divide100), sqrt). Sweet! We have a way to compose numerical functions that might fail. You’ve essentially just implemented Haskell’s Maybe monad, which is a simple form of exception handling. Let’s try some more complex examples.

Example 2: vector operations (a.k.a. “List”)
We know that, mathematically, positive numbers have two square roots. Let’s modify sqrt to return a list of values:
1. def sqrt(x):
2.     if x < 0:
3.         return []
4.     elif x == 0:
5.         return [0]
6.     else:
7.   return [x**0.5, -x**0.5]
So there are three cases we have to consider. If x is positive, we return its two square roots. If x is 0, we return [0]. If x is negative, we return the empty list. Great! Our sqrt function now makes more mathematical sense, at least for real numbers. But we have the same problem as in Example 1—it is no longer composable with itself. We can’t just compute sqrt(sqrt(x)), because the inner call to sqrt returns a list, and the outer call expects a number. As before, we need to define a bind function to help us with composition:
1. def bind(x, f):
2.   return [j for i in x for j in f(i)]
Here, bind takes a list of numbers x and a function f. The doubly-iterated list comprehension might look cryptic—you can think of it like this: We apply f to each value in x, which gives us a list of lists. Then we flatten the result into one list and return it. Now we can compute the square roots of a list of numbers, and then compute all the square roots of the results:
>>> bind(bind([5, 0, 3], sqrt), sqrt)
[1.4953487812212205, -1.4953487812212205, 0, 1.3160740129524924, -1.3160740129524924]

It works! But our original goal was to find the square roots of one number. We could always write bind([x], sqrt) where x is a number, maybe it would be better to use a function to abstract the representation of our input. Let’s call this function unit
1. def unit(x):
2.   return [x]
Yep, it just puts a value into a list. It may seem unmotivated now, but we’ll write a more helpful unit function in the next example. Now we don’t have to put our input into a list—instead, we run it through unit, which puts it in the necessary representation:
>>> bind(bind(unit(4), sqrt), sqrt)
[1.4142135623730951, -1.4142135623730951]

Cool, we can now intelligently compose functions that might return several values! That’s basically Haskell’s List monad

Example 3: debug output (a.k.a. “Writer”)
Suppose we have some functions u and v, and each function takes a number and returns a number. It doesn’t really matter what these functions are, so let’s define them as follows:
1. def u(x):
2.   return x + 4
3.
4. def v(x):
5.   return x * 2
No problem there. We can even compose them, as in u(v(x))What if we wanted these functions to output some extra information along with their normal return value? For example, suppose we want each function to also return a string indicating that the function had been called. We might modify u and v like this:
1. def verbose_u(x):
2.   return (x + 4'[verbose_u was called on ' + str(x) + ']')
3.
4. def verbose_v(x):
5.   return (x * 2'[verbose_v was called on ' + str(x) + ']')
Now we have the same problem as before, we broke composability: verbose_u(verbose_v(x)) doesn’t work. By now, we know the solution to this problem is bind
1. def bind(x, f):
2.   result, output = f(x[0])
3.   return (result, x[1] + output)
Here, x is a tuple containing the result from another operation (such as verbose_u or verbose_v) and the output from that operation. We apply f to x to produce a new result-output tuple. The final result is the result from applying f and the concatenation of the previous output and the output from f. This means we can once again compose verbose_u and verbose_v, using bind
>>> bind(bind((4, ''), verbose_v), verbose_u)
(12, '[verbose_v was called on 4][verbose_u was called on 8]')

Awesome! Not only do we get a numerical result, but we also get a complete stack trace. Notice how we passed (4, ''), when all we cared about was the 4. The empty string means that no functions had been called at that point, but that’s an implementation detail. It would be better to write a unit function to construct this tuple for us, so we don’t have to worry about what goes in the string, the ordering of the elements of the tuple, etc.
1. def unit(x):
2.   return (x, '')
Our example becomes:
>>> bind(bind(unit(4), verbose_v), verbose_u)
(12, '[verbose_v was called on 4][verbose_u was called on 8]')

The pattern
In each example, we had some functions which we wanted to compose, but their type signatures were incompatible. Our functions took a value of some type and returned a value in the corresponding monadic type. All we did was write a wrapper function (bind(x, f)), which defines the logic for how such functions can be chained together. We also defined unit(x) (which is often called return because of the way it is used) to convert a value into a monadic type, so it can be used with our bound functions.

A monad is a type constructor, a bind operation, and a unit function. In Example 1, the monadic type was the union of float and NoneType (we didn’t need a unit function because the monadic type was a superset of the input type). In Example 2, the monadic type was list (of floats), and unit simply put values into a list. Finally, the monadic type for Example 3 was the product (i.e., tuple) of int and str, so unit constructed that tuple from a value and the empty string.So the use of monads is basically a design pattern, and it’s been used to implement several concepts that are normally associated with imperative programming, such as exception handling (much like in Example 2), parsers, state, collections, and I/O (as we will see shortly).

Proper monads must obey three axioms so they behave the way we expect.
1. Left Identity: bind(unit(x), f) == f(x)
2. Right Identity: bind(x, unit) == x
3. Associativity: bind(bind(x, f), g) == bind(x, lambda a: bind(f(a), g))

(Here, equality should be taken to mean the two expressions represent the same computation.

The first two axioms mean that unit and bind roughly do inverse things: unit puts a value into a monadic container for binding and bind takes it out to apply a function. The last axiom means we can compose functions together without worrying about how composition precedence works. I’ll leave it as an exercise for the reader to prove that the versions of unit and bind that we wrote obey the three monad laws.