2015/08/18 07:37:45
Now I want to show several examples, just as an illustration for the previous talk.

Exception Monad



Given some fixed type E (just any), exception monad is defined as the functor that maps type X to type E+X. That's assuming we have union defined and working in our category.

Why is it a monad?
1. pure: X ⇒ E+X is defined naturally
2. flatten: E+(E+X) ⇒ E+X is defined naturally

These two are behaving, as you can check. Suppose we are in a category where we can build an applicative functor out of it; what can it be? First, what's its signature? It is (E+X) × (E+Y) ⇒ E + X×Y. It is kind of obvious it is enough (and necessary) to define E×E ⇒ E. And this operation should be associative.

So we will have a semigroup; and if we have a semigroup, we will have an applicative functor.

But what semigroup is given by our magic that provides (if possible) a default monadic strength for a given monad? If you look into the details of implementation, in the first part, the operation is just the first projection, p1: E×E ⇒ E.

In plain programmatic terms it behaves like this: if we throw an exception in the first component, we do not evaluate the second component. Namely, having (E+X) × (E+Y) = E×E + X×E + E×Y + X×Y, when we flatten it to E + X×Y, the first component returns "the first exception"; the second component returns "the second exception", the third component returns "the first exception", and the fourth component returns a pair (x,y).

Having just a type E (e.g. a set E), one may have more than one semigroup defined on it. And we can have a monad E+X with monadic strength defined separately. Is there a problem with it? None; each strength, derived from the semigroup, is just another monadic strength. It satisfies all the conditions.

List



With lists, one can easily see that the default strength exists, and the appropriate zip operation is the following: List[X]×List[Y] ⇒ List[X×Y] is the list of all combinations of elements of the first and the second list. zip(1::2::Nil, "ab") = List((1,'a'),(1,'b'),(2,'a'),(2'b')).

Are there other ways to zip two lists? There's an interesting belief that the known 'zip' operation serves this goal: zip(list1,list2) = list1.zip(list2); this applicative functor is called 'zipList'.

No. It does not preserve identity. pure(x) cannot be a singleton list; and repeatForever(x) is not a list.

You will need a very different structure, a stream. A stream is a function from Natural Numbers Object to a type; ℕ ⇒ T. We can define zip for streams, thus making the functor applicative. And this operation actually gives us a hint how to make a stream a monad.

See, a stream of streams can be represented as a map ℕ×ℕ ⇒ T; compose it with diag:ℕ ⇒ ℕ×ℕ, and you get a new stream. pure is defined as a constant function. It is obvious that pure is a monadic unit. All that is left to check is associativity of flatten.

And this amounts to the following property: given i1:(ℕ×ℕ)×ℕ ⇒ ℕ×ℕ×ℕ where i1((a,b),c) = (a,b,c), and i2:ℕ×(ℕ×ℕ) ⇒ ℕ×ℕ×ℕ where i2(a,(b,c)) = (a,b,c). What we have to prove is that i1((a,a),a) = i2(a,(a,a)), which is kind of obvious.

Conclusion, probably


So, here we are not only lucky, we can see that in lists and streams the monad and the strength are pretty much connected.

But it is not always so; it depends. As Tom Leinster pointed, "Something to bear in mind is that strength is not a property of a monad: it's extra structure on a monad. The same monad can admit no strengths, one strength, or many strengths. (At least, I believe this to be the case. I don't know an example.) So "monad that is not strong" is a phrase comparable to "set that is not a group"." (http://mathoverflow.net/questions/85391/any-example-of-a-non-strong-monad/86914#86914 )
83 посетителя, 9 комментариев, 44 ссылки, за 24 часа