• Fast fourier transform: An ingenious way to multiply polynomials
Posted on January 16, 2021
Tags: explanation note Categories: math

## Background

I used to hear many people talk about that fast fourier transform (FFT) is one of the most beautiful algorithms in the engineering world, but I never dove deep into that.

Then a few days ago I stumble upon this wonderful Youtube video about FFT created by @Reducible. So I took some note of my learning from the that video. I figured out this note is probably qualified for public consumption so I decided to publicize it.

If you haven’t watched the video yet, I highly recommend you to watch it:

Let’s begin the journey!

## Polynomial multiplication problem

How do we multiply two polynomials? A method we all learned from high school is to use distribution law to expand the terms, and then combine the terms with the same exponent. Here’s an example:

$\begin{equation} \begin{split} (5x^2+4)(2x^2+x+1) & = 5x^2(2x^2+x+1) + 4(2x^2+x+1) \\ & = (10x^4+5x^3+5x^2) + (8x^2+4x+4) \\ & = 10x^4+5x^3+13x^2+4x+4 \\ \end{split} \end{equation}$

## Polynomial representation

If we want to implement the multiplication in a program, we first need to find a way to represent the polynomial.

For polynomial of degree $$d$$, there are two unique ways we can use:

1. use a list $$d+1$$ of coefficients of the powers: $$[p_0, p_1, ..., p_d]$$ (coefficient representation)
2. use a set of $$d+1$$ distinct points: $${(x_0, P(x_0)), (x_1, P(x_1)), ..., (x_d,P(x_d))}$$ (value representation)

The value representation works because a polynomial of degree $$N$$ can be determined by $$N+1$$ distinct interpolation points. For example, two points determine a line, three points determine a parabola.

The coefficient representation is what we demonstrated in Polynomial multiplication problem. It’s straightforward and we already know it. However, it’s not performant enough for polynomial multiplication. The time complexity is $$O(N^2)$$ where $$N$$ is the degree of the polynomial, because we need to multiply all possible pairs of terms.

The value representation, on the other hand, is much faster for multiplying polynomial. To multiply two polynomials, if we assume the $$\mathbf{x}$$ values are consistent in the two representations, we can just pointwise multiply the $$P(\mathbf{x})$$ values. So this algorithm has a time complexity of $$O(N)$$.

## Flowchart for polynomial multiplication

Now we can draw a diagram on how to perform fast multiplication for polynomials. The step involved in converting coefficient representation into value reprentation is where fast fourier transform (FFT) kicks in. ## Coefficient representation conversion

The most naive method to convert coefficient representation is just to plug in some arbitrary values to the polynomial.

However, this will result in us going back to the original complexity because we need to calculate for each term in the polynomial and for each $$x$$ value. This will get us back to $$O(N^2)$$ time complexity with $$N$$ being the degree of the polynomial. Not good.

This is where Fast Fourier Transform algorithm shines. The FFT algorithm is able do the same conversion in just $$O(N \log N)$$ time!

We will learn about the tricks FFT based on and see if we can derive FFT ourselves.

## Polynomial evaluation

First, let’s see how we can improve the naive algorithm. Suppose we have a polynomial term of even power, $$5x^2$$ for example, then we can carefully pick the $$\mathbf{x}$$ points to be symmetrical about the $$y$$ axis. If we do so, we only need to perform half the computation since once we know $$P(x)$$, we automatically know $$P(-x) = P(x)$$. Similarly, for individual odd degree terms, we have $$P(x)=-P(-x)$$.

With this trick, we can cut the number of computations needed by half. For each individual point $$x_i$$, to compute $$P(x_i)$$, we can split the calculation into $$P_e(x_i^2)$$ and $$x_i P_o(x_i^2)$$ which represent the even and odd degree terms, respectively.

For example, $$P(x) = 5x^5 + 6x^4 + 7x^3 + 8x^2 + 9x + 10$$ evaluated at $$x_i$$ can be written as $$P_e(x_i^2) + x P_o(x_i^2)$$, where $$P_e(x^2) = 6x^4 + 8x^2 + 10$$ and $$P_o(x^2) = 5x^5 + 7x^3 + 9x$$.

Then we have:

$\begin{equation} \begin{cases} P( x_i) &= P_e(x_i^2) + x_i P_o(x_i^2) \\ P(-x_i) &= P_e(x_i^2) - x_i P_o(x_i^2) \end{cases} \end{equation}$

In which $$P_e(x_i^2)$$ and $$P_o(x_i^2)$$ can be calculated only once and used twice.

From here we can go with the recursive step. $$P_e(x)$$ and $$P_o(x)$$ each is a polynomial of degree $$d/2$$, which only have half of the terms. We can further apply the algorithm to it with half the size until we reach the base case where $$d=0$$. In such case we just have $$1$$ term - the constant term, so we can just return it as the evaluation result.

Except there is a blocker in the recursion step. The “divide” step works based on the assumption that we can always choose two set of points $$\mathbf{x_i}$$ and $$-\mathbf{x_i}$$. This will not be the case except for the first iteration. In the second iteration we will have $$x_i^2$$ and $$(-x_i)^2$$ which are normally both positive, so we can no longer further split the polynomial - well, unless we introduce complex number into the play.

## Constraints for the sample points

Let’s list out the requirements we need for the $$N$$ sampling points for degree $$N-1$$ polynomial. From now on, for simplicity purpose, we will only talk about polynomial with degree $$2^k-1$$ where $$k\in\mathbb{Z}^{*}$$.

In the first iteration, we have $$N$$ points, half of them need to be negation of the other half. Let’s note down the conditions.

$\label{cond1} x_{\frac{N}{2}+i} = -x_i\quad\text{for } i \in 0,\ldots,\frac{N}{2}$

Note that we only need to compute half of the point set.

Then in the next interation, we will be passing $$x_k^2$$ to the $$P_e$$ and $$P_o$$, where $$k$$ takes values of $$0,..,N/4$$.

$\label{cond2} x_{\frac{N}{4}+i}^2 = -x_i^2\quad\text{for }i \in 0,\ldots,\frac{N}{4}$

Starting from equations and we can inductively deduce all the restrictions on all $$x$$ values.

The base case for polynomial of degree $$N-1$$ is $$x_0^{N}$$. We can assign it to $$x_0^N = 1$$. This value specifies $$x_0^{\frac{N}{2}}$$ and $$x_1^{\frac{N}{2}}$$ to be the two roots of $$x_0^N$$ that are negation of each other. In the next iteration, each of these two values in turn specifies four more values, $$x_i^{\frac{N}{4}}$$ for $$i\in \{0,1,2,3\}$$ and so on. Until we hit the case $$\frac{N}{2^k} = 1$$, then we get all the plain $$x_i^{\frac{N}{2^k}}=x_i$$ values.

Let’s look at the second interation, where we acquired the constraint that $$x_0^{\frac{N}{2}}$$ and $$x_1^{\frac{N}{2}}$$ are roots of $$x_0^N=1$$, so one must be $$1$$ and other be $$-1$$. But in reality they can be of any order. Same choice must be made to all future iterations.

The trick is to take $$x_i$$ to be the $$i$$ th element of the “$$N$$ th root of unity”.

$\begin{equation} x_i=e^{2\pi j\frac{i}{N}} \end{equation}$

Where $$j=\sqrt{-1}$$. We can verify that these points satisfy the constraints we wanted: $$x_0^N=e^{0}=1$$; then $$x_0^{N/2} = e^{0} = 1$$ and $$x_1^{N/2}=e^{\pi j} = -1$$ are the roots of $$x_0^N$$; and so on.

## Symmetrical properties of sample points

If we plot the points for $$e^{2\pi j \frac{i}{N}}$$ for all $$i$$ on the complex plane, we can find that they reside on a circle with equal distance apart. Here’s a graph for $$N=8$$. The $$x$$ points are arranged in an counter-clockwise order, starting from $$x_0=1$$.

We can see that these points are symmetrical about the origin - that is to say, every point $$x_i$$ has a counterpart $$x_{N/2+i}=-x_i$$, which is the reflection of $$x_i$$ about the origin. This property is exactly what we wanted.

In the following iterations, we would square the half of all the $$x_i$$ values. Squaring a unit complex number $$z$$ is the same as doubling angle of the number couter-clockwise. So in the next iterations, we essentially continue to fill the circle with half of the points, resulting a new circle where points are twice the old distance apart. In the last iteration, the result will be just a single point $$x_0^N = 1$$.

## Constructing the algorithm

We now learned how to pick sample points, now let’s formalize the algorithm.

The FFT algorithm should take two arguments, a list of coefficients representing the polynomial, and a list of sampling points. The output is a list of $$P(x_i)$$ values corresponding to each point $$x_i$$. $$N$$ is represented by the length of the coefficient list (or the number of points, which is the same anyway).

The simplest case is when $$N=1$$, where we have to calculate $$\operatorname{FFT}(P=[c_0], X=)$$, which is the same as evaluating $$P(x)=c_0$$ at $$x=1$$. The result is trivial - we just return $$Y=[c_0]$$.

Next simplest case is when $$N=2$$, where we have $$\operatorname{FFT}(P=[c_0, c_1], X=[1, -1])$$. This polynomial is easy to calcualte on its own. Although the recursive algorithm applies at this case, it’s not very representative for demonstration purpose, so we will skip this iteration and assume it works normally.

The next one is $$N=3$$, where we have $$\operatorname{FFT}(P=[c_0, c_1, c_2, c_3], X=[1, j, -1, -j])$$, that is, to evaluate $$c_0 + c_1 x^1 + c_2 x^2 + c_3 x^3$$ at the given $$x_i$$ points.

We first split $$P(x)$$ into even and odd components: $$P_e(x^2)+xP_o(x^2) = (c_0+c_2 x^2) + x(c_1+c_3 x^2)$$. This gave us two smaller polynomials for the recursion step $$P_e=[c_0, c_2]$$ and $$P_o = [c_1, c_3]$$.

Now let’s see what $$x_i$$ values we need to provide for the recursion step. The whole point of the algorithm is to save half of the calculation by exploiting the even/odd polynomials. So we only need to calculate for these polynomials on $$X=[1, j]$$. Note that their arguments are not $$x_i$$ but $$x_i^2$$. So we need to pass $$X=[1, j^2=-1]$$ to them. The same parameter applies to both the even and odd polynomials. In turn, we are left with evaluating two expressions $$Y_e = \operatorname{FFT}(P=[c_0, c_2], X=[1, -1])$$ and $$Y_o=\operatorname{FFT}(P=[c_1, c_3], X=[1, -1])$$. This reduces our problem of size $$N=4$$ to two $$N=2$$ cases.

Now comes the final part - after we computed the $$Y_e$$ and $$Y_o$$, we need to compose them in a way that calculates the final $$Y$$ values. Given that $$x_{N/2+i}=-x_i$$ for $$i \in 0,..,\frac{N}{2}$$, and the nature of even/odd polynomials, we know that $$P_e(x_{N/2+i})=P_e(x_i)$$ and $$P_o(x_{N/2+i}) = -P_o(x_i)$$. Also we know $$P=P_e + x P_o$$. This gave us the way to compose the $$Y_e$$ and $$Y_o$$. $$y_i = y_e+ x_i y_i$$ and $$y_{N/2+i} = y_e - x_i y_i$$ for $$i \in 0,..,\frac{N}{2}$$.

Now we can observe another invariant. For all recursion steps, the $$X$$ values for that step are fixed. In other words, the values of $$X$$ only depend on the degree $$N$$, which can be deduced from length of the coefficient list. For $$N=1$$, we always have $$X=$$; for $$N=2$$, we always have $$X=[1,-1]$$; for $$N=4$$, we always have $$X=[1,j,-1,-j]$$. This result comes from our previous reasoning from last section about squaring roots of unity. As a result, we no longer have to explicitly specify this argument to FFT procedure.

## Implementing in code

To implement the algorithm in code, we basically just copy the steps described above. Note that we represent $$x_i=e^{2 \pi j \frac{i}{N}}$$ with $$w^i$$ where $$w=e^{2 \frac{\pi j}{N}}$$.

import math
import cmath

def fft(p):
n = len(p)
if n == 1:
return p
w = cmath.exp(2*math.pi*1j/n)
y_e = fft(p[0::2])
y_o = fft(p[1::2])
y = [None] * n
for i in range(n//2):
y[i]      = y_e[i] + y_o[i] * w**i
y[i+n//2] = y_e[i] - y_o[i] * w**i
return y

Let’s verify if the result is correct.

def p(x):
return 1 + 2*x + 3*x**2 + 4*x**3

print(fft([1,2,3,4]))
print([p(1), p(1j), p(-1), p(-1j)])
[(10+0j), (-2-2j), (-2+0j), (-1.9999999999999998+2j)]
[10, (-2-2j), -2, (-2+2j)]


Ignoring the round-off error, we can see the two results are the same.

## FFT operation as a matrix

The naive method of evaluating the value of a polynomial of degree $$N-1$$ at $$N$$ sampling points is to calculating $$N$$ values, which are $$P(x_i)$$ where $$i = 0, 1, \ldots, N-1$$. Then, to calculate $$P(x_i)$$, we need to sum up the the value of each terms

$\begin{equation} P(x_i) = \sum_{k=0}^{N-1} x_i^kc_k \end{equation}$

where $$c_k$$ is the k-th coefficient of the polynomial. This means we can construct an $$N$$ by $$N$$ matrix with each element to be $$W_{i,k} = x_i^k$$.

$\begin{equation} W = \begin{pmatrix} 1 & x_0 & x_0^2 & \cdots & x_0^m \\ 1 & x_1 & x_1^2 & \cdots & x_1^m \\ 1 & x_2 & x_2^2 & \cdots & x_2^m \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_m & x_m^2 & \cdots & x_m^m \\ \end{pmatrix} \end{equation}$

where $$m = N-1$$. If we plug in our chosen sampling points $$x_i = w^i = e^{\frac{2\pi j}{n}}$$ we get this matrix:

$\begin{equation} W = \begin{pmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & w & w^2 & \cdots & w^m \\ 1 & w^2 & w^4 & \cdots & w^{2m} \\ 1 & w^3 & w^6 & \cdots & w^{3m} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & w^m & w^{2m} & \cdots & w^{m^2} \\ \end{pmatrix} \end{equation}$

Given a vector of coefficient $$P=[c_0, c_1, \ldots, c_m]$$, the result of $$Y = WP$$ is just the sampled values we wanted.

In fact, this matrix is called the discrete fourier transform matrix (DFT matrix) for this exact reason. The FFT algorithm above is just an more efficient way to perform the matrix multiplication with this matrix.

Correspondingly, the technique to calculate the inverse fourier transform is to find the inverse matrix. And interestingly, the inverse DFT matrix looks very similar to the DFT matrix!

$\begin{equation} W^{-1} = \frac{1}{N}\begin{pmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & w^{-1} & w^{-2} & \cdots & w^{-m} \\ 1 & w^{-2} & w^{-4} & \cdots & w^{-2m} \\ 1 & w^{-3} & w^{-6} & \cdots & w^{-3m} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & w^{-m} & w^{-2m} & \cdots & w^{-m^2} \\ \end{pmatrix} \end{equation}$

The fact that the inverse DFT matrix is similar to the DFT matrix gives us a way to compute inverse fast fourier transform. This means to convert our FFT algorithm to Inverse FFT algorithm, we only need the following two changes,

1. replace all occurences $$w$$ with $$w^{-1}$$;
2. finally, multiply with $$\frac{1}{N}$$.

## Implementation of Inverse FFT algorithm

And - here we have it.

def _ifft(p):
n = len(p)
if n == 1:
return p
w = cmath.exp(-2*math.pi*1j/n)
y_e = _ifft(p[0::2])
y_o = _ifft(p[1::2])
y = [None] * n
for i in range(n//2):
y[i]      = y_e[i] + y_o[i] * w**i
y[i+n//2] = y_e[i] - y_o[i] * w**i
return y

def ifft(p):
n = len(p)
return [x/n for x in _ifft(p)]

Now let’s try out if it’s indeed the inverse of fft function.

print(ifft(fft([1,2,3,4])))
print(fft(ifft([1j,2j+1])))
[(1+0j), (2-5.721188726109833e-18j), (3+0j), (4+5.721188726109833e-18j)]
[1j, (1+2j)]


Ihe inverse does seem to work ignoring the round-off errors.

I tried to understand the IFFT algorithm in a similar way as we exploit the symmetry of even and odd polynomials, but I can’t find a way to make sense of it. The algorithm itself still works like magic - I can’t explain it with a deeper understanding. I am sorry if you’re expecting that.

## Polynomial multiplication Now we have all the components in the flowchart, we can finally implement the algorithm to perform fast polynomial multiplication.

def pad_radix2(xs, n):
b = n.bit_length() - 1
if n & (n-1): # not a power of 2
b += 1
n = 2 ** b
return xs +  * (n - len(xs))

def poly_mult(p1, p2):
max_n = max(len(p1), len(p2)) * 2
y3 = [a * b for a, b in zip(y1, y2)]
return ifft(y3)

# calculate (2x+1)(4x+3)
print(poly_mult([1,2], [3,4]))
[(3+8.881784197001252e-16j), (10-3.599721149882556e-16j), (8-8.881784197001252e-16j), 3.599721149882556e-16j]


3,10,8 - we just calculated that $$(2x+1)(4x+3)=8x^2 + 10x + 3$$. The algorithm worked!

## Summary

In this article we studied how to make use of FFT algorithm to compute polynomial multiplication in $$O(N \log N)$$ time. We mainly studied how the ingenious tricks work together to make FFT algorithm concise and elegant, and finally implemented the multiplication algorithm in code.

Some other sources that are helpful for my understanding:

• Source code of fft function in sympy. I learned how to quickly pad up a list to radix-2 length.
• jakevdp’s post “Understanding the FFT Algorithm”. I learned the trick numpy uses to make it much faster than my implementation.
• This math stackexchange answer. It resolved my confusion on the discrepancy of the formula on Wikipedia and the formula used in the video.
• What I learned about Codata
Posted on December 9, 2020
Tags: explanation Categories: category theory haskell

## Codata as dual of data

### Data

When we define a new type in Haskell, we use the data keyword:

data Foo
= Foo1 Int String
| Foo2 Bool

This is essentially equivalent as defining two data constructors (they are legit functions):

Foo1 :: Int -> String -> Foo
Foo2 :: Bool -> Foo

This type of construct is called “data” by some people.

### Usage of a data

Here’s an example of an inductively defined data structure.

data Tree = Leaf | Node Tree Int Tree
-- i.e.
Leaf :: Tree
Node :: Tree -> Int -> Tree -> Tree

What does it mean to use such data? It means we need to destruct the data by matching on all its constructors:

height :: Tree -> Int
height Leaf = 0
height (Node left _val right) = 1 + max (height left) (height right)

This types of function is called an “eliminator”.

### Data eliminator and initial algebras

A data is an initial algebra we previously learned about. Take the above Tree as an example, it’s defined as the initial algebra on the following functor.

data TreeF a = Leaf | Node a Int a
type Tree = Fix TreeF

You can review the my previous talk on initial algebra.

Then above defintion of height can be expressed as catamorphism on an algebra of TreeF.

heightAlg :: TreeF Int -> Int
heightAlg Leaf = 0
heightAlg (Node left _val right) = 1 + (max left right)

height :: Fix TreeF -> Int
height = cata heightAlg

### Codata

If we revert the arrows that constructs a data, we get two functions dual to the previous data constructors that have the shapes like this:

Bar1 :: Bar -> (Int, String)
Bar2 :: Bar -> Bool

Intuitively, Bar1 and Bar2, instead of two ways to construct a Bar from their components, they specifies two ways to use the Bar. This is what we called codata.

### Construction of codata

Here’s another example of useful codata:

type Stream = (Int, Stream)

tail :: Stream -> Stream

Here’s an example on how to construct this codata.

startFrom :: Int -> Stream
startFrom n = (n, startFrom (n + 1))

### Terminal coalgebra and codata constructor

Above codata Stream can be expressed as terminal coalgebra (fix-point) on the following

type StreamF a = (Int, a)
type Stream = Fix StreamF

Then the startFrom constructor for Stream will be an anamorphism on some coalgebra:

startFromCoalg :: Int -> StreamF Int
startFromCoalg n = (n, n + 1)

startFrom :: Int -> Fix StreamF
startFrom = ana fromCoalg

## General purpose codata

### Church encoding of data types

One intriguing topic in functional programming is Church encoding. Church encoding shows us ways to encode any data and control constructs as purely lambda functions.

\f x -> x               -- 0
\f x -> f x             -- 1
\f x -> f (f x)         -- 2
\n -> \f x -> f (n f x) -- succ :: Nat -> Nat

\x y -> x               -- true
\x y -> y               -- false
\p -> \a b -> p b a     -- not :: Bool -> Bool
\p a b -> p a b         -- if :: Bool -> a -> a -> a

\x y z -> z x y         -- pair :: a -> b -> pair
\p -> p (\x y -> x)     -- fst :: pair -> a

### General eliminator of Bool

Let’s take a look in an eliminator for Bool.

data Bool = True | False
type BoolC a = (a, a) -> a

elimBool :: Bool -> BoolC a
elimBool True  (a, b) = a
elimBool False (a, b) = b

You may recognize that the BoolC for elimBool is equivalent to the Church encoding for Bool. We will show their equivalence in next section.

You may also recognize that that elimBool is the most general eliminator for type Bool. In other words, every valid eliminator can be derived from this eliminator.

In fact, the general eliminator elimBool is the catamorphism of type Bool.

### Isomorphism between Church encoding and the data

We will demonstrate that Bool and BoolC are indeed isomorphic:

from :: Bool -> BoolC a
from = elimBool

to :: BoolC a -> Bool
to f = f (True, False)

It’s easy to prove that from . to = id and to . from = id so I’ll elaborate. So far we have shown that BoolC is indeed a Church encoding for Bool.

### General eliminator for Tree

Let’s look at a more complex type:

data Tree = Leaf | Node Tree Int Tree

type TreeC a = a -> ((a, Int, a) -> a) -> a
elimTree = Tree -> TreeC a
elimTree Leaf                f g = f
elimTree (Node left n right) f g = g left' n right'
where left'  = elimTree f g left
right' = elimTree f g right

You may recognize that elimTree is the catamorphism for Tree. Also TreeC is a legit Church encoding for Tree.

### Visitor pattern on Tree

Now we learned how to find Church encoding and shown how Church encoding is isomorphic as the represented data type.

We can discover a pattern such that we can extract of all the ways we can eliminate a Tree into a single entity. We will call this entity “TreeVisitor”.

type TreeVisitor a = (a, (a, Int, a) -> a)

visitLeaf :: TreeVisitor a -> a
visitNode :: TreeVisitor a -> (a, Int, a) -> a

As the name suggests, this pattern is just the Visitor pattern in OOP. Here I am using a pair to represent the type for TreeVisitor, but the exact way to implement it doesn’t really matter.

The point of TreeVisitor a being a codata type because the only thing we care about it is to be able to derive the two methods visitLeaf and visitNode.

### Tree as Codata

A Tree can then be defined as the all possible TreeVisitor a -> a instances (i.e. TreeC a), as we already proved by showing the isomorphism between Tree and TreeC.

walk :: Tree -> (forall a. TreeVisitor a -> a)

This representation of Tree is also a codata because the actual underlying data structure of Tree is hidden from the outside, and the TreeVisitors already defined all the ways to access it.

## References

Posted on November 16, 2018
Tags: explanation Categories: category theory

This post is the sequel to the yesterday’s post Algebras compatible with list monad gives rise to a monoid. To illustrate how Eilenberg-Moore category can be constructed with algebras on monads.

A question arises as we learned that an adjunction gives rise to a monad and a comonad, does the converse hold as well? Is there a natural way to get an adjunction from a monad? The answer to this is yes. The intuition is that with monad $$T$$, we have plenty of choices for $$C$$, the point is to find out these two functors $$L:T\to C$$ and $$R:C\to T$$ that satisfies the triangular identity.

I’ll review from horizontal composition of natural transformations; then I’ll review the definition of adjunctions and how adjunctions give rise to a monad; finally, I’ll talk about how a Eilenberg-Moore category can be constructed and why it is left adjoint to a monad category.

## Horizontal composition between natural transformations

Natural transformations, of course, can be composed. Natural transformations can compose in two different ways: horizontally and vertically. Vertical composition is just plain morphism composition with little surprise. Horizontal composition is what gets more interesting. Here I’ll denote the identity natural transformation over $$F$$ by simply $$F$$ when there is no ambiguity.

Let’s see what happens if we compose $$\alpha\circ F$$ in the following diagram (called a “whiskering”, because of its shape):

$\xymatrix { E & & D \ar@/_2pc/[ll]^{G'}="a" \ar@/^2pc/[ll]_{G}="b" & C \ar[l]^{F} \ar @2{->}_{\alpha} "b";"a" }$

Now we take $$a:C$$, and see what we get on $$(\alpha \circ F)_a$$.

$\xymatrix { G'(F a) \\ & F a \ar[ul]^{G'} \ar[dl]_{G} & a\ar[l]^F \\ G(F a) \ar[uu]_{\alpha_{F a}} }$

From the diagram we can see $$(\alpha \circ F)_a = \alpha_{F a}$$. Now let’s see another version of whiskering:

$\xymatrix { E & D \ar[l]^{G} & & C \ar@/_2pc/[ll]^{F'}="a" \ar@/^2pc/[ll]_{F}="b" \ar @2{->}_{\alpha} "b";"a" }$

Similarly, take $$a: C$$, let’s see what we get by composing $$(G \circ \alpha)_a$$.

$\xymatrix { G (F' a) & F' a \ar[dd]_{\alpha_a}\ar[l]^G & \\ & & a \ar[ul]^{F'}\ar[dl]^{F} \\ G (F a)\ar[uu]_{G \alpha_a} & F a \ar[l]^G & \\ }$

Thus $$(G\circ \alpha)_a = G \alpha_a$$, not exactly symmetric to the left whiskering version.

In the rest of the articles, I’ll using the result from this sections a lot and won’t get into the details.

Given two categories $$C$$ and $$D$$, two morphisms that goes between them $$L: D\to C$$, $$R: C\to D$$. We say $$L$$ is left adjoint to $$R$$ when the following condition holds for all $$a:C$$, $$b:D$$.

$C(L b, a) \simeq D(b, R a)$

By replacing $$a$$ with $$L b$$, we get

$C(L b, L b) \simeq D(b, R(L b))$

On the left we have $$id_{L b}$$, by the isomorphism of hom-set, this morphism will select a morphism on the right: $$b \to R (L b)$$. This is an natural transformation called a unit, denoted as $$\eta: 1_D \to R\circ L$$.

Similarly by replacing $$b$$ with $$R a$$, we can get the dual of unit – the counit – on the left of the hom-set isomorphism: $$\epsilon: L \circ R \to 1_C$$.

An adjunction defined by unit and counit has to satisfy the triangle identities, namely:

$\xymatrix { L \ar[r]^{L\circ \eta} \ar@2{-}[rd]^{} & LRL \ar[d]^{\epsilon \circ L} \\ & L \\ }$

and:

$\xymatrix { R \ar[r]^{\eta \circ R} \ar@2{-}[rd]^{} & RLR \ar[d]^{R\circ\epsilon} \\ & R \\ }$

Adjunction defines a very loose equivalence relation between functors $$L$$ and $$R$$. Where one can think of $$L$$ as to introduce some structures, and $$R$$ to remove the structures. A typical example for adjunction is the free-forgetful adjunction.

In last post I mentioned an adjunction can give rise to a monad, here’s how.

Given an adjunction $$L \dashv R$$, where $$L: D\to C$$ and $$R: C\to D$$, we define a functor $$T = R \circ L$$ be the underlying functor of the monad. Let $$\mu = R \circ \epsilon \circ L$$ be the monad multiplication and the monad unit - $$\eta$$ - be the same as the unit for the adjunction.

We first check the types. $$\mu: RLRL \to RL = T^2 \to T$$, check. $$\eta: 1 \to RL = 1 \to T$$, also check. Then we need to check if $$\mu$$ and $$\eta$$ works subjecting to the monad laws.

First the unit laws:

$\xymatrix { T \ar[d]_{T\circ\eta} \ar[r]^{\eta\circ T} & T^2 \ar[d]^{\mu} \\ T^2 \ar[r]^{\mu} & T }$

This law can be derived from triangle identities by left composing the first identity with an $$R$$ and right composing the second identity with an $$L$$. The following diagram will automatically communites thanks to the triangle identities.

$\xymatrix { RL \ar[d]_{RL \circ \eta} \ar[r]^{\eta \circ RL} \ar@2{-}[rd]^{} & RLRL \ar[d]^{R\circ\epsilon\circ L} \\ RLRL \ar[r]_{R\circ\epsilon\circ L} & RL \\ }$

Now the multiplication law (or associativity law):

$\xymatrix { T^3 \ar[r]^{\mu \circ T} \ar[d]_{T\circ\mu} & T^2\ar[d]^\mu \\ T^2 \ar[r]^\mu & T }$

Or,

$\xymatrix { RLRLRL \ar[rr]^{R\circ\epsilon\circ L \circ RL} \ar[dd]_{RL\circ R\circ\epsilon\circ L} & & RLRL\ar[dd]^{R\circ\epsilon\circ L} \\\ & \\ RLRL \ar[rr]^{R\circ\epsilon\circ L} & & RL }$

This is the naturality square of $$\epsilon$$ left composed with $$R$$! Let’s remove the $$R$$ on the left and see what we get:

$\xymatrix { LRLRL \ar[rr]^{\epsilon_{LRL}} \ar[dd]_{LR \circ f} & & LRL\ar[dd]^{f} \\\ & \\ LRL \ar[rr]^{\epsilon_L} & & RL }$

This is exactly the naturality square of $$\epsilon: LR\to1$$. Thus we proved that the monad associativity law holds naturally just because $$\epsilon$$ is a natural transform.

In fact, an adjunction also gives rise to a comonad on $$RL$$, in a very similar fashion, by defining the counit (extract) to be $$\epsilon$$ and $$\delta$$ (duplication) to be $$L\circ\eta\circ R$$.

Now let’s get back to monad algebra which we discussed extensively in the last post. Last time we proved that an algebra compatible with a list monad is a monoid, it’s a rather surprising finding.

Let’s now revisit the definition of monad compatible algebra. Given a monad $$(T: C \to C, \eta: 1 \to T, \mu: T^2 \to T)$$ and an algebra $$(a: C, \sigma: T a \to a)$$, we define the coherence conditions as follows:

• $$\sigma \circ \eta_a = 1_a$$
• $$\sigma \circ \mu_a = \sigma \circ T \sigma$$

Algebras that satisfy these conditions are compatible with the given monad, and we call them monad algebras.

Not very surprisingly, monad algebras for a monad $$(T, \tau, \mu)$$ do form a category. The objects are $$(a:C, \sigma:T a\to a)$$, and the morphisms are the same morphisms in $$C$$. This category is called monad algebra category, or Eilenberg-Moore category, denoted as $$\textbf{mAlg}_T$$, or $$C^T$$.

Identity morphism on $$(a,\sigma)$$ in $$C^T$$ is just the identity morphism on $$a$$ in $$C$$. Morphism compositions also work the same way as they’re in $$C$$.

I just missed one thing. Before we can claim $$(T a, \mu_a)$$ is a monad algebra, we need to check if this algebra meets the coherence conditions.

First, $$\mu \circ \eta_{T a} = 1_{T a}$$. This one is just the right identity law for monad, so it automatically holds. Then we check $$\mu\circ \mu_{T a}=\mu\circ T \mu$$. It’s just the monad associativity (multiplication) law! See how these all fits so perfectly. Just because of monad laws, $$\mu_a$$ will always be a compatible algebra on $$T a$$.

The cannonical functor from $$C^T$$ to $$C$$ is the forgetful functor that “forget” about the algebra part, i.e. $$U: (a,\sigma) \mapsto a$$. In addition, $$U: f \mapsto f$$ for morphisms.

It’s much more tricker to define the free functor $$F: C\to C^T$$. We need to find a valid algebra for every $$a$$. Fortunately, it turns out we already have a very good candidate – $$\mu_a: T (T a) \to T a$$ from the monad. $$\mu$$ is a natural transformation so it works on any $$a$$, for every $$a$$ we have an algebra from $$T (T a)$$ to $$T a$$.

Now we can define the free functor $$F: C \to C^T$$ as $$a \mapsto (T a, \mu_a)$$, which is kind of neat. Of course, $$F$$ should also maps $$f: a \to b$$ to $$F f: T a \to T b$$, which is just $$T f$$.

Now we have got a pair of free and forgetful functors, it’s time to prove they are really adjoint. We say $$F$$ is left adjoint to $$U$$, or $$F \dashv U$$.

To play with adjunction, we need to first define our pair of natural transformations $$\eta: 1_C \to U\circ F$$ and $$\epsilon: F\circ U \to 1_{C^T}$$.

Let’s write down $$\eta$$ in its components form: $$\eta_a: a \to U (F a)$$, and we know $$U (F a) = U (T a, \sigma) = T a$$. We can just use the unit $$\eta$$ from the monad!

What about $$\epsilon$$? $$\epsilon_{(a,\sigma)}: F (U (a,\sigma)) \to (a,\sigma)$$. Where $$F (U (a, \sigma)) = F a = (T a, \mu_a)$$. We need to find a map from $$(T a, \mu_a)$$ to $$(a, \sigma)$$. We can just use the forgotten evaluator $$\sigma: T a\to a$$.

In order for the unit and counit to form an adjunction, we need to check the triangle laws.

$\xymatrix { (T a, \mu_a) \ar[r]^{F\circ \eta_a} \ar@2{-}[rd]^{} & (T(T a), \mu_{T a}) \ar[d]^{\mu_{a}} \\ & (T a, \mu_a) \\ }$

We can check the algebras’ carrier types.

$\xymatrix { T a \ar[r]^\eta & T (T a) \ar[r]^\mu & T a }$

This is essentially just $$\mu \circ \eta$$, which is equal to the identity by the right unit law on monad. The evaluator follows automatically, because they’re just regular morphisms in $$C$$. Then we check another triangle identity:

$\xymatrix { a \ar[r]^{\eta_{U (a, \sigma_a)}} \ar@2{-}[rd]^{} & T a \ar[d]^{U\circ\sigma_a} \\ & a \\ }$

Omitting the unimportant part, we get:

$\xymatrix { a \ar[r]^{\eta_a} & T a \ar[r]^{\sigma_a} & a }$

Looking familiar? Yes, $$\sigma \circ \eta = 1$$ must hold by one of the coherence conditions for $$\sigma$$ to be compatible with our monad.

Therefore we have shown the Eilenberg-Moore category $$C^T$$ is left adjoint to a monad category $$C$$. I’m not sure if it’s valid to say a category is left adjoint to another category. But anyway, we have discovered another free-forgetful functor pair that are adjoint to each other, and what makes it so fascinating is that it’s an adjunction we can get from ANY monad.

## References

Posted on November 15, 2018
Tags: explanation Categories: category theory

I’m currently watching Dr. Bartosz Milewski’s video lecture series on category theory on YouTube. In this lecture Category Theory III 4.2, Monad algebras part 3, he stated an interesting fact that in an algebra that is compatible with the list monad is a monoid.

In his video lecture he explained it very briefly and drawn the conclusion quickly before I can follow to convince myself on the fact. After that, in comment, I saw someone else had the similar questions at the ambiguous notation Dr. Milewski uses. So I derived the theorem myself to clarify my understanding. I think the outcome is kind of interesting that worths a post about it.

I want to write this post in a very beginner-friendly manner, to explain the concepts to people whom knew only some basic category theory. Hopefully it’s gonna also help me to clear things out.

## Monoid

Monoid captures the generalized idea of multiplication. A monoid on a set $$S$$ is made of an element $$\eta\in S$$ called unit and binary operation $$\mu: S \times S \to S$$ called multiplication that satisfies these laws:

• left identity law: $$\mu(\eta, a) = a$$, for $$a \in S$$
• right identity law: $$\mu(a, \eta) = a$$, for $$a \in S$$
• associativity law: $$\mu(a,\mu(b,c)) = \mu(\mu(a,b),c)$$, for $$a,b,c\in S$$

Here are some common examples of monoids:

• list monoid on list, where $$\eta$$ is empty list and $$\mu$$ is the append operator (++ in Haskell)
• additive monoid on integer, where $$\eta$$ is $$0$$ and $$\mu$$ is $$+$$
• multiplicative monoid on integer, where $$\eta$$ is $$1$$ and $$\mu$$ is $$\times$$

A monad is defined as an endofunctor $$T$$ along with two natural transformations $$\eta: a \to T a$$ called unit and $$\mu: T^2 a\to T a$$ called multiplication that satisified these laws:

• identity law:

$\begin{CD} T a @>\eta>> T^2 a \\ @VVT\mu V @V\mu VV \\ T^2 a @>\mu >> T a \end{CD}$

where the $$T a$$ at top-left is equal to the $$T a$$ at bottom right.

• mutiplication law:

$\begin{CD} T^3 a @>T \mu>> T^2 a \\ @VV\mu V @VV\mu V \\ T^2 a @>\mu >> T a \end{CD}$

These laws are essentially just monoid laws (left/right identity law and associativity law) on the category of endofunctors.

The list functor is a monad with $$\eta$$ and $$\mu$$ defined as following:

η x = [x]
μ xs = concat xs

where $$\eta$$ sends a value to a singleton list containing that value, and $$\mu$$ is concatenation function of a list of lists.

It’s easy show the monad laws for this list monad hold, since it’s not today’s focus, I’ll skip it.

## Algebra

An algebra on an endofunctor $$F: C\to D$$ is given by a tuple $$(a, \sigma)$$, where $$a$$ is an object in $$C$$ and $$\sigma$$ is an endofunction $$F a \to a$$. It’s worth noting that an algebra is not a natural transformation as it seems.

A natural transformation has no knowledge on its component, therefore must be a polymorphic function. This restriction is, however, not required for an algebra. In an algebra, $$\sigma$$ is bound to a specific object $$a: C$$, thus it can do transformations on $$a$$ or generate an $$a$$ from nowhere.

An algebra can be viewed as a map to evaluate a functor on values (e.g. algebraic expression) into an single value. Here are some examples of algebras:

• sum on list of additive numbers
• length on polymorphic list
• foo (x:_) = x; foo [] = 1 on list of integers
• eval: ExprF a -> a on an expression of type a

In an algebra the functor plays the role to form an expression, and the $$\sigma$$ function evaluates it.

## Category of algebras

Algebras on an given endofunctor $$F:C\to D$$ can form a category, where the objects are the algebras $$(a, \sigma)$$, and the morphisms from $$(a,\sigma)$$ to $$(b,\tau)$$ can be defined as morphisms in $$C(a,b)$$. We now show that the morphisms are composible:

$\begin{CD} F a @>F f>> F b \\ @VV\sigma V @VV\tau V \\ a @>f>> b \end{CD}$

Since $$F$$ is a functor, this diagram automatically commutes.

Given an endofunctor $$T$$, A monad algebra on $$T$$ is a monad on $$T$$ along with an compatible algebra on $$T$$. A monad algebra contains all the operations from its monad part and its algebra part:

• $$\eta: a \to T a$$
• $$\mu: T^2 a \to T a$$
• $$\sigma: T a \to a$$

Be noted that a specific algebra can have a specific $$a$$.

To make the algebra compatible with the monad, we need to impose these two conditions:

• with unit, $$(\sigma \circ \eta) a = a$$
• with multiplication, the diagram below should commute

$\begin{CD} T^2 a @>\mu>> T a \\ @VV T\sigma V @VV\sigma V \\ T a @>\sigma>> a \end{CD}$

These two conditions are strong. Not all algebras on $$T$$ are compatible with a given monad on $$T$$. For example, in the list monad of integers, the condition requires η [x] = x; this eliminates all other algebras that don’t satisfy this property, like the length algebra.

Now we finally get to the interesting one. There are many monad-compatible algebras on list, for example: sum, product, concat etc. These algebras do various of operations but there’s one thing in common: they all seems to related to some monoid. In fact they indeed do. We will now prove it.

First we see what properties do algebras on list monad hold. By the compatibility we discussed eariler, we always have:

• η [x] = x and,
• (σ∘Tσ) x = (σ∘μ) x, where $$\mu$$ is the concat operator for list

Let σ [] = e and σ [x,y] = x <> y, we now show e is an unit and x <> y is the multiplication operator in a monoid.

We now prove the left identity law for the monoid. We prove this by evaluting (σ∘Tσ) [[], [x]] in two ways. On the left we got (σ∘Tσ) [[], [x]] = σ [e, x] = e <> x, on the right we got (σ∘Tσ) [[], [x]] = (σ∘μ) [[], [x]] = σ [x] = x. This shows e <> x = x. The right identity law can be proved in a similar fashion.

Now the associativity law, first we get (σ∘Tσ) [[x,y],z] = [x <> y, z] = (x <> y) <> z, and (σ∘Tσ) [x,[y,z]] = [x, y<>z] = x <> (y <> z). We also no that they both equal to (σ∘μ) [[x,y],z] = (σ∘μ) [x,[y,z]] = σ [x,y,z]. For consistency, this means σ [x,y,z] must be defined as (x <> y) <> z or x <> (y <> z), and they are equal.

Now we have proved that the algebra must gives rise to a monoid, and $$\sigma$$ is the mconcat function.

## References

• 一篇面向初學者的簡短而又不失趣味(但願)的 Rust futures 入門指南
Posted on November 24, 2017
Tags: translation Categories: rust

原文《Rust futures: an uneducated, short and hopefully not boring tutorial》由 Francesco Cogno 發佈 於其博客。本文是一篇系列教程，原文已更新至第四部分，目前譯文只完成了前三部分。

## 第一部分

### 引言

如果你喜歡 Rust，你可能會注意到整個 Rust 社區正在流行使用 future。很多知名的 crate 開始徹底擁抱 future（譬如說 Hyper），我們也得學會用才行。如果你覺得自己是小白程序員，可能會覺得很難理解 future 的原理。當然原作者 Crichton 的教程 是很好的教材，雖然講得很通透，但我覺得這個教材有點難理解，不適合上手。

我想我肯定不是唯一這麼想的人，所以我就把自己的發現和理解分享給大家，幫大家熟悉 future 的用法。

### Future 簡述

Future 可以被理解為一種不會立即執行的古怪函數，相反，它們在未來才會執行（所以才叫做 future）。使用 future 而非普通函數的原因很多，譬如說為了性能，為了優雅，為了可組合性，等等。Future 的缺點在於寫起來有點難，好吧，是難。如果你都不知道一個函數何時會執行，你怎麼知道它的前因後果是什麼？

因此，不同的編程語言會用不同的語言特徵來拯救我們這些可憐又無助的程序員。

### Rust 的 Future

Rust 社區的發展是迅速的，Rust 中 future 的實現也是。所以，一如繼往要聲明一下，你從這裡學到的知識可能會在一段時間後顯得過時，所以要注意一下。

Rust 的 futures 其實就是 Results：也就是說你需要指定預期返回類型和錯誤類型。

讓我們把普通函數轉換成 future 吧。在本例中的函數返回 u32 或者 Box 的 Error trait 對象：

fn my_fn() -> Result<u32, Box<Error>> {
Ok(100)
}

很簡單對吧，現在看看它對應的 future 實現：

fn my_fut() -> impl Future<Item = u32, Error = Box<Error>> {
ok(100)
}

我們來看看一下這兩種實現的區別。首先，返回值不再是 Result 類型，而是 implFuture. 這個語法（目前還只能在 Rust nightly 版本上用）意味著我們會返回實現 Future trait 的類型。其中的 <Item = u32, Error = Box<Error>> 其實指定了返回類型和錯誤類型，只是語法比 Result 囉嗦一點。

注意這種語法需要啟用 conservative_impl_trait nightly feature。當然你也可以返回 Box<Future<...>>，但我個人覺得後者比較笨拙。

還應該注意一點的是作為返回值的 Ok(100)。Result 風格的函數我們會用大寫的 Ok，因為它是一個 enum；而在 future 中我們使用的是小寫的 ok 方法。

首條規則：在 future 中記得使用小寫的函數返回方法。

還不錯，對吧？現在的問題是怎麼執行這種函數？Result 版本的函數可以直接調用，哦注意我們返回的是 Result 所以我們得 unwrap() 掉之才能訪問裡面的值。

let retval = my_fn().unwrap();
println!("{:?}", retval);

Future 則會在實際執行前就返回了（或者更準確地講，我們先返回了準備以後執行的代碼），所以我們得有個方法執行它。對此我們可以用 Reactor，創建個 Reactor 並調用其 run 方法就能執行 future 了。對於我們上面的例子，可以這樣：

let mut reactor = Core::new().unwrap();

let retval = reactor.run(my_fut()).unwrap();
println!("{:?}", retval);

注意這裡我們 unwrap 的是 run 的返回值，不是 my_fut() 自身的。

真是小菜一碟。

### 鏈式方法

我們能把多個 future 鏈起來按順序執行，這正是 future 強大的原因之一。設想一下邀父母一起吃晚餐的場景。首先給他們發送短信，等待他們回應；收到回應後就著手準備晚餐（不想自己動手的話，可以裝病逃過幹活）。鏈式方法就有點像這樣子。讓我們看看下面的例子吧。

首先我們再寫個函數，叫做 squared，這裡我們同時寫出標準版本和 future 版本：

fn my_fn_squared(i: u32) -> Result<u32, Box<Error>> {
Ok(i * i)
}

fn my_fut_squared(i: u32) -> impl Future<Item = u32, Error = Box<Error>> {
ok(i * i)
}

我們可以這樣調用標準版的函數：

let retval = my_fn().unwrap();
println!("{:?}", retval);

let retval2 = my_fn_squared(retval).unwrap();
println!("{:?}", retval2);

我們也可以用同樣的流程多次調用 Reactor 來執行 future 版的函數：

let mut reactor = Core::new().unwrap();

let retval = reactor.run(my_fut()).unwrap();
println!("{:?}", retval);

let retval2 = reactor.run(my_fut_squared(retval)).unwrap();
println!("{:?}", retval2);

但其實有種更好的方法。Future 作為一個 trait，其實有很多方法可以調用（我們只會講到一小部分），其中 and_then 做的就是我們上面做的事情，但用它我們可以省去調兩次 Reactor.run(...)。來看看：

let chained_future = my_fut().and_then(|retval| my_fn_squared(retval));
let retval2 = reactor.run(chained_future).unwrap();
println!("{:?}", retval2);

看第一行，我們創造了一個新未來 future，叫做 chained_future，由 my_futmy_fut_squared 組合而成。

把一個 future 的返回值傳給下一個 future 的部分有點棘手，在 Rust 中，我們使用閉包參數來捕獲之（|...| 中間的部分）。這個過程是這樣的：

1. 預定執行 my_fut()
2. my_fut() 執行完畢並返回一個叫做 retval 的變量，把它存入 my_fut() 的執行結果中。
3. 在那之後預訂執行 my_fn_squared(i: u32)，將 retval 作為參數傳進去。
4. 把這個 指令流程 打包成一個 future 函數，叫做 chained_future

接下來就一如既往了，我們調用 Reactorrun 方法執行 chained_future 所打包的整個 指令流程 來得到執行結果。

當然，我們其實可以無限這樣把方法鏈起來，不要擔心這樣做會有性能損失：future 鏈是零開銷的（除非你選擇使用 Box<Future> 之類的手段）。

在寫 future 鏈的時候，Rust 的 borrow 檢查器可能跳出來報錯。這時你可以試試用 move 關鍵字把這些被捕獲的變量移開。

### Future 和普通函數的混合寫法

我們還可以把 future 和普通函數鏈到一起，這樣就不用要求每個函數都是 future。有時我們可能會用到外部提供的，無法修改的函數，那麼就有必要這樣做了。

如果這個普通函數不返回 Result，我們可以簡單地在一個閉包中直接調用。譬如說這個普通函數：

fn fn_plain(i: u32) -> u32 {
i - 50
}

我們的鏈式 future 可以這樣寫：

let chained_future = my_fut().and_then(|retval| {
let retval2 = fn_plain(retval);
my_fut_squared(retval2)
});
let retval3 = reactor.run(chained_future).unwrap();
println!("{:?}", retval3);

如果這個函數返回 Result，那麼就有更好的做法了。讓我們試試把 my_fn_squared(i: u32) -> Result<u32, Box<Error>> 鏈起來吧。

雖然你無法對著 future 的 and_then 方法調用返回 Result 的函數，但是 future 的設計者已經考慮過這種情況了！Future 中的 done 方法的作用正是把 Result 轉換為 impl Future

這是什麼意思呢？也就是說，我們可以把普通函數包在 done 方法中，進而當成一個 future 來用！

我們來試試：

let chained_future = my_fut().and_then(|retval| {
done(my_fn_squared(retval)).and_then(|retval2| my_fut_squared(retval2))
});
let retval3 = reactor.run(chained_future).unwrap();
println!("{:?}", retval3);

注意第二行中的 done(my_fn_squared(retval)) ，這樣我們就把普通函數當成 future 來鏈起來用了。再看看如果沒有 done 會怎樣：

let chained_future = my_fut().and_then(|retval| {
my_fn_squared(retval).and_then(|retval2| my_fut_squared(retval2))
});
let retval3 = reactor.run(chained_future).unwrap();
println!("{:?}", retval3);

編譯器會報錯：

   Compiling tst_fut2 v0.1.0 (file:///home/MINDFLAVOR/mindflavor/src/rust/tst_future_2)
error[E0308]: mismatched types
--> src/main.rs:136:50
|
136 |         my_fn_squared(retval).and_then(|retval2| my_fut_squared(retval2))
|                                                  ^^^^^^^^^^^^^^^^^^^^^^^ expected enum std::result::Result, found anonymized type
|
= note: expected type std::result::Result<_, std::boxed::Box<std::error::Error>>
found type impl futures::Future

error: aborting due to previous error

error: Could not compile tst_fut2.

其中 expected type std::result::Result<_, std::boxed::Box<std::error::Error>> found type impl futures::Future 的錯誤信息有點誤導。其實這個錯誤是因為我們在該傳入 impl Future 的地方傳入了 Result（錯誤信息中反過來了）。編譯器的這個誤導會讓很多初學者困惑（見 https://github.com/alexcrichton/futures-rs/issues/402），我們後面再回顧這個問題。

### 泛型

我們再看看 Rust 中的泛型怎麼玩。看這個例子：

fn fut_generic_own<A>(a1: A, a2: A) -> impl Future<Item = A, Error = Box<Error>>
where
A: std::cmp::PartialOrd,
{
if a1 < a2 {
ok(a1)
} else {
ok(a2)
}
}

這個函數版回兩個參數中的較小值。注意，無論我們的函數會不會返回錯誤，我們都得給這個 future 指定一個錯誤類型，還有就是這裡返回值中的 ok 是全小寫的函數，而非那個 enum。

然後我們可以這樣執行這個 future：

let future = fut_generic_own("Sampdoria", "Juventus");
let retval = reactor.run(future).unwrap();
println!("fut_generic_own == {}", retval);

相信你已經領悟到要旨了 :)。現在這種代碼應該看起來很合理多了。你可能注意到在這裡我避免使用引用，只用了 owned 的值，這是因為 impl Future 對 lifetime 的處理方法不太一樣，在後面的章節會講到怎麼搞定 lifetime 的問題。

### 註釋

如果想要運行上面的這些代碼片段，要在 Cargo.toml 文件中加上這幾行：

[dependencies]
futures="*"
tokio-core="*"
futures-await = { git = 'https://github.com/alexcrichton/futures-await' }

然後在 src/main.rs 最上面加上這幾行：

#![feature(conservative_impl_trait, proc_macro, generators)]

extern crate futures_await as futures;
extern crate tokio_core;

use futures::done;
use futures::prelude::*;
use futures::future::{err, ok};
use tokio_core::reactor::Core;
use std::error::Error;

上面的內容並不需要引入 futures-await crate，但後面我們講到的內容會用到它。

(第一部分完)

##第二部分

###引言

第一部分的內容中我們學習了如何使用 Rust 中的 futures。如果你掌握到訣竅，會覺得非常非常簡單。在第二部分我們會著重於學習如何避開常見的陷阱。

### 麻煩的 Error

把 future 鏈起來並不難，我們已經學過 and_then() 方法的用法了。但是之前我們刻意避開了一個坑的地方，使用了 Box<Error> 來表示異常返回值。為何我們不用更具體的錯誤類型呢？因為把 future 鏈起來的時候需要 把它們的錯誤類型都匹配上 才行。

鏈式 futures 的錯誤類型必須統一。

來看演示吧。假如說我們有兩個類型 ErrorAErrorB，分別實現為 error::Error trait 的實例，雖然說並不必要，但我覺得這是個好習慣。類型需要實現 std::fmt::Display 才能被實現為 Error trait，所以我們也得同時實現這個 Display。為了突出重點，我會儘可能舉簡單例子。

#[derive(Debug, Default)]
pub struct ErrorA {}

impl fmt::Display for ErrorA {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "ErrorA!")
}
}

impl error::Error for ErrorA {
fn description(&self) -> &str {
"Description for ErrorA"
}

fn cause(&self) -> Option<&error::Error> {
None
}
}

ErrorB 也一樣：

#[derive(Debug, Default)]
pub struct ErrorB {}

impl fmt::Display for ErrorB {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "ErrorB!")
}
}

impl error::Error for ErrorB {
fn description(&self) -> &str {
"Description for ErrorB"
}

fn cause(&self) -> Option<&error::Error> {
None
}
}

接下來就可以開始用這些錯誤類型了。我們來寫幾個返回錯誤的 future，再提醒一下，future 只是一種返回 Result<A, B> 的函數，只是語法有點不一樣而已。

fn fut_error_a() -> impl Future<Item = (), Error = ErrorA> {
err(ErrorA {})
}

fn fut_error_b() -> impl Future<Item = (), Error = ErrorB> {
err(ErrorB {})
}

現在我們在 main 函數中用一下這兩個 future：

let retval = reactor.run(fut_error_a()).unwrap_err();
println!("fut_error_a == {:?}", retval);

let retval = reactor.run(fut_error_b()).unwrap_err();
println!("fut_error_b == {:?}", retval);

結果一點都不意外：

fut_error_a == ErrorA
fut_error_b == ErrorB

還不錯，現在我們來把這些 future 鏈起來：

let future = fut_error_a().and_then(|_| fut_error_b());

我們這裡調用了 fut_error_a 函數，然後進一步調用 fut_error_b，我們暫時不關心 fut_error_a 的返回值，所以用 _ 表示把這個值丟掉了。

更具體的描述是，我們在試圖把一個 impl Future<Item=(), Error=ErrorA> 和一個 impl Future<Item=(), Error=ErrorB> 鏈起來。

我們來試試編譯一下：

Compiling tst_fut2 v0.1.0 (file:///home/MINDFLAVOR/mindflavor/src/rust/tst_future_2)
error[E0271]: type mismatch resolving <impl futures::Future as futures::IntoFuture>::Error == errors::ErrorA
--> src/main.rs:166:32
|
166 |     let future = fut_error_a().and_then(|_| fut_error_b());
|                                ^^^^^^^^ expected struct errors::ErrorB, found struct errors::ErrorA
|
= note: expected type errors::ErrorB
found type errors::ErrorA

錯誤信息很清楚，我們在本該有 ErrorB 的地方得到一個 ErrorA。通俗來講：

在把兩個 future 鏈起來的時候，第一個函數的錯誤類型應該和第二個一樣。

這正是 rustc 告訴我們的：fut_error_b() 返回了 ErrorB，那麼 fut_error_a() 也必須返回 ErrorB，但實際上它返回了 ErrorA，編譯就失敗了。

那怎麼解決這個問題呢？所幸我們可以用一個叫作 map_err 的方法。在此例中我們想要把 ErrorA 轉成 ErrorB，所以我們要在其中插入一個 map_err 的調用：

let future = fut_error_a()
.map_err(|e| {
println!("mapping {:?} into ErrorB", e);
ErrorB::default()
})
.and_then(|_| fut_error_b());

let retval = reactor.run(future).unwrap_err();
println!("error chain == {:?}", retval);

現在這個例子能編過也能跑起來了，輸出正如所料：

mapping ErrorA into ErrorB
error chain == ErrorB

我們來進一步探索這個例子。假如說我們想要把 ErrorAErrorB 鏈起來，然後再鏈上 ErrorA，像這樣：

let future = fut_error_a()
.and_then(|_| fut_error_b())
.and_then(|_| fut_error_a());

和上面的規則是一樣的，這樣組合 future 是不合法的。所以我們要把 fut_error_afut_error_b 中間的錯誤類型轉成 ErrorB。然後再在 fut_error_bfut_error_a 之間把錯誤類型轉回 ErrorA。下面的代碼有點醜但是跑得起來：

let future = fut_error_a()
.map_err(|_| ErrorB::default())
.and_then(|_| fut_error_b())
.map_err(|_| ErrorA::default())
.and_then(|_| fut_error_a());

### From 來相救

簡化上面代碼的一種方法是利用 std::convert::From trait。簡單來說，使用 From trait 我們可以告訴 Rust 該怎麼全自動從源類型轉換到目標類型。雖然這個 trait 會消耗掉源錯誤類型的所有權，但對我們的例子而言這沒什麼關係。另外一點是，這個 trait 會假設轉換從不失敗。最後，我們只能對我們寫的類型實現這個 trait，所以這種方法並不是一直能用的。

我們來實現一下 From<ErrorA> for ErrorBFromInto<ErrorB> for ErrorA 吧：

impl From<ErrorB> for ErrorA {
fn from(e: ErrorB) -> ErrorA {
ErrorA::default()
}
}

impl From<ErrorA> for ErrorB {
fn from(e: ErrorA) -> ErrorB {
ErrorB::default()
}
}

這樣一來，上面例子中的代碼就可以被簡化了：只要用 from_err() 取代 map_err() 函數就可以。Rust 很聰明，能自己找到對應的轉換函數：

let future = fut_error_a()
.from_err()
.and_then(|_| fut_error_b())
.from_err()
.and_then(|_| fut_error_a());

這裡依然混合著各種錯誤類型轉換，但是好在錯誤類型轉換的部分不用在這裡具體寫出來了，這樣代碼看起來好讀多了。

Future crate 很聰明，from_err 的代碼只會在出錯的情況下才會被調用到，所以這一切也是沒有任何運行時開銷的。

fn my_fn_ref<'a>(s: &'a str) -> Result<&'a str, Box<Error>> {
Ok(s)
}

留意一下 <'a> 這部分，這是聲明 lifetime 的語法，接下來的 s: &'a str 是表示參數 s 是字符串引用類型，它將在 'a 有效的期間保持有效。返回類型 Result<&' str, Box<Error>> 意味著返回值會包含字符串引用，而它也必須在 'a 有效期間保證有效。換句話說，輸入的字符串和輸出的對象必須要有相同的 lifetime。

fn my_fn_ref(s: &str) -> Result<&str, Box<Error>> {
Ok(s)
}

不過… 至少時至如今，我們還不能省略 future 中的 lifetime 標註。如果照著前面的代碼寫這樣一個 impl Future 的話：

fn my_fut_ref_implicit(s: &str) -> impl Future<Item = &str, Error = Box<Error>> {
ok(s)
}

這樣就會出錯。上面的代碼在我的電腦上（rustc 1.23.0-nightly (2be4cc040 2017-11-01)），引起了編譯錯誤：

   Compiling tst_fut2 v0.1.0 (file:///home/MINDFLAVOR/mindflavor/src/rust/tst_future_2)
error: internal compiler error: /checkout/src/librustc_typeck/check/mod.rs:633: escaping regions in predicate Obligation(predicate=Binder(ProjectionPredicate(ProjectionTy { substs: Slice([_]), item_def_id: DefId { krate: CrateNum(15), index: DefIndex(0:330) => futures[59aa]::future::Future::Item } }, &str)),depth=0)
--> src/main.rs:39:36
|
39 | fn my_fut_ref_implicit(s: &str) -> impl Future<Item = &str, Error = Box<Error>> {
|                                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

note: the compiler unexpectedly panicked. this is a bug.

note: we would appreciate a bug report: https://github.com/rust-lang/rust/blob/master/CONTRIBUTING.md#bug-reports

note: rustc 1.23.0-nightly (2be4cc040 2017-11-01) running on x86_64-unknown-linux-gnu

thread 'rustc' panicked at 'Box<Any>', /checkout/src/librustc_errors/lib.rs:450:8
note: Run with RUST_BACKTRACE=1 for a backtrace.

別灰心，記得 impl Future 還只是試驗特性。要解決這個問題，我們要把所有的 lifetime 顯式標註出來：

fn my_fut_ref<'a>(s: &'a str) -> impl Future<Item = &'a str, Error = Box<Error>> {
ok(s)
}

這樣就一切正常了。

### 帶 lifetime 的 impl Future

我們不僅僅要在參數上顯示標註 lifetime，就算只是想要返回隱含 lifetime 的 impl Future，那麼也得把它標註上。舉例來說，假如我們這次想寫個接受 &str 參數並返回 String 的 future，那麼我們必須把參數的 lifetime 也顯式標注上，所以可能會寫成這樣：

fn my_fut_ref_chained<'a>(s: &'a str) -> impl Future<Item = String, Error = Box<Error>> {
}

但實際上這樣也是不行的，因為返回的類型並沒有隱含 'a，錯誤信息如下：

error[E0564]: only named lifetimes are allowed in impl Trait, but  was found in the type futures::AndThen<impl futures::Future, futures::FutureResult<std::string::String, std::boxed::Box<std::error::Error + 'static>>, [closure@src/main.rs:44:28: 44:64]>
--> src/main.rs:43:42
|
43 | fn my_fut_ref_chained<'a>(s: &'a str) -> impl Future<Item = String, Error = Box<Error>> {
|                                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

要解決這個問題，我們只需要把 'a 加到 impl Future 聲明後面就可以了，像這樣：

fn my_fut_ref_chained<'a>(s: &'a str) -> impl Future<Item = String, Error = Box<Error>> + 'a {
}

這樣你就可以一如既往使用 reactor 執行這個函數了：

let retval = reactor
.unwrap();
println!("my_fut_ref_chained == {}", retval);

結果也如預期一樣：

my_fut_ref_chained == received == str with lifetime

### 小結

後面我們會具體聊聊 reactor，我們也會從頭開始自己寫一個實現 future 的類型。

(第二部分完)

## 第三部分

### 引言

本文中我們會試著解釋 reactor 的原理。前幾篇我們已經在大量使用 reactor 了，但我們只是將之當作一個黑盒來用的。現在是時候打開這個盒子，看看裡面是怎樣的了！

### Reactor？循環？

Reactor 簡單來講就是一個循環。要解釋之，我想到一個類比：假如說你發了郵件邀請了一位女生/男生約會（好吧我知道這樣有點老套），你 想要 收到答覆，所以你不斷，不斷，不斷去檢查有沒有新郵件，直到你終於得到了答覆。

Rust 的 reactor 就有點像這樣子。給它一個 future，它會不斷檢查這個 future 的狀態，直到這個 future 完成或者出錯為止。它通過一個叫 poll （輪詢）的函數來實現這樣的功能，一點也不奇怪。Future 類型的實現者自己必須實現 poll 函數才行，他們要做的就是返回一個類行為 Poll<T, E> 的值（詳參 Poll 文檔）。好吧事實上 reactor 並不會不斷去調用你寫的輪詢函數，但暫時我們先別深究細節。我們來從這個例子開始看吧。

### 從頭開始實現一個 Future

為了測試我們學得怎樣，我們現在來從頭實現個 future。換句話說，我們要來手動實現一個滿足 Future trait 的類型。我們來實現最小可用的 future，這個 future 在過一段時間後才會返回預先設定的值。

我們將我們的這個 struct 類型命名為 WaitForIt

#[derive(Debug)]
struct WaitForIt {
message: String,
until: DateTime<Utc>,
polls: u64,
}

我們的這個類型會在裡面保存一條自定義的消息，等待超時的的時間，以及它被輪詢過的次數。為了讓我們的代碼看起來乾淨一點，我們來實現一下這個類型的 new 函數：

impl WaitForIt {
pub fn new(message: String, delay: Duration) -> WaitForIt {
WaitForIt {
polls: 0,
message: message,
until: Utc::now() + delay,
}
}
}

我們這裡寫的 new 函數會創建一個 WaitForIt 實例，然後初始化之。

現在我們來實現 Future trait，我們唯一要做的就是實現好 poll 方法：

impl Future for WaitForIt {
type Item = String;
type Error = Box<Error>;

fn poll(&mut self) -> Poll<Self::Item, Self::Error> {
let now = Utc::now();
if self.until < now {
format!("{} after {} polls!", self.message, self.polls),
))
} else {
self.polls += 1;

println!("not ready yet --> {:?}", self);
}
}
}

讓我們一步一步來看看。下面的這兩行有點難搞：

    type Item = String;
type Error = Box<Error>;

它們叫做關聯類型（associated types）。在這裡它們用於指示這個 future 返回什麼類型，還有出錯時會返回什麼錯誤類型。所以我們可以說：這個 future 會在將來返回要麼一個 String，要麼一個 Box<Error>

下面這一行定義了 poll 函數：

    fn poll(&mut self) -> Poll<Self::Item, Self::Error> {

其中 Self::ItemSelf::Error 部分引用的是上面我們定義的關聯類型。在本例中，這個方法等價於這樣寫：fn poll(&mut self) -> Poll<String, Box<Error>>

然後就是邏輯部分了：

let now = Utc::now();
if self.until < now {
// Tell reactor we are ready!
} else {
// Tell reactor we are not ready! Come back later!
}

我們怎麼通知 reactor 這個 future 還沒完成呢？返回 Ok<Async::NotReady> 就可以了。如果這個 future 已經完成了，我們就返回 Ok<Async::Ready(T)>。所以這個函數就這樣實現：

impl Future for WaitForIt {
type Item = String;
type Error = Box<Error>;

fn poll(&mut self) -> Poll<Self::Item, Self::Error> {
let now = Utc::now();
if self.until < now {
format!("{} after {} polls!", self.message, self.polls),
))
} else {
self.polls += 1;

println!("not ready yet --> {:?}", self);
}
}
}

要執行這個 future，我們要在 main 函數裡創建一個 reactor，然後用它來跑我們剛實現的 future 類型。

fn main() {
let mut reactor = Core::new().unwrap();

let wfi_1 = WaitForIt::new("I'm done:".to_owned(), Duration::seconds(1));
println!("wfi_1 == {:?}", wfi_1);

let ret = reactor.run(wfi_1).unwrap();
println!("ret == {:?}", ret);
}

如果運行一下上面的程序，你應該以為這個 future 會等一秒鐘，然後正常返回。我們運行一下看看：

Running target/debug/tst_fut_create
wfi_1 == WaitForIt { message: "I\'m done:", until: 2017-11-07T16:07:06.382232234Z, polls: 0 }
not ready yet --> WaitForIt { message: "I\'m done:", until: 2017-11-07T16:07:06.382232234Z, polls: 1 }

然….而並不是這樣，在這些輸出之後，代碼就卡住了。另外值得注意的是該進程一點 CPU 都沒有佔用：

為什麼會這樣呢？這就是 reactor 神奇的地方了：reactor 並不會輪詢 駐留函數（parked function），除非被明確指示去那樣做。在本例中，reactor 一開始就立刻調用了我們的函數，我們返回了 Async::NotReady，所以 reactor 就把我們的函數 駐留 在一邊了。除非有東西取消這個函數的 駐留 狀態，否則 reactor 就不會再調用它了。在等待的時候 reactor 處於空閑狀態，自然也不會佔用 CPU 了。這樣的機制意味著 reactor 能有更高的 CPU 利用效率，不會浪費 CPU 去不斷輪詢 future 的結果完成與否。在前面查郵件的例子中，這相當於我們不用不斷手動刷新郵件頁面，而只需靜候郵件通知就好了，有空的時候我們還可以玩玩 守望屁股。

另一個更有意義的例子是接收從網絡來的數據。我們可以阻塞線程，等待網絡封包到來，也可以在等待的時候做些別的事情。你可能會好奇為什麼這樣做會比開個線程更好，這裡我們不涉及具體細節，只要記住一般來說這樣比線程效率高就好了。

### 取消駐留

那該怎麼修正上面的代碼呢？我們要找個方法把 future 的駐留狀態取消掉。理想情況下，外部事件會取消駐留 future 的狀態（譬如說收到網絡封包、按下按鍵），但是我們的例子中我們就用下面這行手動取消駐留：

futures::task::current().notify();

所以現在我們的 future 實現變成了：

impl Future for WaitForIt {
type Item = String;
type Error = Box<Error>;

fn poll(&mut self) -> Poll<Self::Item, Self::Error> {
let now = Utc::now();
if self.until < now {
format!("{} after {} polls!", self.message, self.polls),
))
} else {
self.polls += 1;

println!("not ready yet --> {:?}", self);
}
}
}

現在運行一下代碼吧：

現在代碼成功執行完了，注意在這個例子中，該函數在一秒內被調用了 50k 次。真是浪費資源，這也就說明了為什麼只該在發生事件時取消駐留。關於這點，我們可以看看進程的 CPU 佔用率：

留意一下這裡的輪詢只用了一個線程，這裡本來就是這樣設計的，以實現更高的效率。當然，你也可以使用多線程就是了。

### Joining

Reactor 的一個實用特性是可以併發執行多個 future。我們在單線程中達到高效併發的方法是這樣的，一個 future 駐留時，其他 future 就可以趁機執行了。

我們繼續用 WaitForIt 類型來講這個例子，這次我們同時調用它兩次。首先我們要創建兩個 future

let wfi_1 = WaitForIt::new("I'm done:".to_owned(), Duration::seconds(1));
println!("wfi_1 == {:?}", wfi_1);
let wfi_2 = WaitForIt::new("I'm done too:".to_owned(), Duration::seconds(1));
println!("wfi_2 == {:?}", wfi_2);

接下來我們調用 futures::future::join_all 函數，這個函數的參數是一個包含多個 future 的迭代器，我們就用一個簡單的 vector 吧：

let v = vec![wfi_1, wfi_2];

簡單來說 join_all 函數會返回一個新 future，輪詢這個 future 會不斷交替地返回輸入的 future。

現在的完整代碼如下：

fn main() {
let mut reactor = Core::new().unwrap();

let wfi_1 = WaitForIt::new("I'm done:".to_owned(), Duration::seconds(1));
println!("wfi_1 == {:?}", wfi_1);
let wfi_2 = WaitForIt::new("I'm done too:".to_owned(), Duration::seconds(1));
println!("wfi_2 == {:?}", wfi_2);

let v = vec![wfi_1, wfi_2];

let sel = join_all(v);

let ret = reactor.run(sel).unwrap();
println!("ret == {:?}", ret);
}

我們來跑一下，輸出應該是類似下面的效果：

注意這裡我們可以看到 reactor 在交替請求我們的 future，第一個被調用，然後第二個，然後又是第一個，如此反覆，直到兩個 future 都完成為止。從圖中你可以看到第一個 future 比第二個先完成了，第二個 future 在完成前被單獨調用了兩次。

### Select

future 中還有很多其他函數，另一個有趣的函數叫 select。Select 函數會同時執行兩個 future，並且會返回最先執行完成的那個。這個函數很適合用來實現超時，這裡是我們的例子：

fn main() {
let mut reactor = Core::new().unwrap();

let wfi_1 = WaitForIt::new("I'm done:".to_owned(), Duration::seconds(1));
println!("wfi_1 == {:?}", wfi_1);
let wfi_2 = WaitForIt::new("I'm done too:".to_owned(), Duration::seconds(2));
println!("wfi_2 == {:?}", wfi_2);

let v = vec![wfi_1, wfi_2];

let sel = select_all(v);

let ret = reactor.run(sel).unwrap();
println!("ret == {:?}", ret);
}

### 結語

下一篇我們會探索令人興奮的 await! 宏，祝玩得開心！

## 第四部分

待翻譯⋯⋯

聲明：此文章的翻譯及發佈已經經過原文作者的許可。此譯文版權歸譯者所有，並在 CC BY-NC-SA 4.0 下發佈。

Find out more in archives.