Entries tagged with applicative functor

Entry tags:

Monads and Applicative Functors, part 2

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 )

Entry tags:

a Monad and an Applicative Functor

This has been dragging forever. Let me cover it, shedding light to the dark corners, ok?

Introduction

First, definitions. I'll try to use, as much as possible, Scala notation, and, basically, Scala terms.

A category consists of types and functions; a function is from one type to another; some functions can compose (if one starts where the other ends), composition is associative, and there's an identity function for each type.

There's more than one category in this (kind of) world. Given two categories, C and D, we can build a product category, C × D, consisting of pairs of types and pairs of functions.

Some categories have a special type called unit; every type has exactly one function to unit. Functions from unit to a type are called points or instances. Instead of writing a:1⇒A we use to write a shortcut, a:A This is just a syntactic sugar.

Another syntactic sugar is this: if we have a point a:A, its composition with a function f:A⇒B is usually thought of as an "application" of f to a, and is written as f(a):B; but remember, it is just a composition of two functions.

It is good to know what instances a type has, but, in general settings, not all properties of a type are defined by the "set" of its instances. If they are, the category is called well-pointed. Remember this word, it's important.

In the case of a well-pointed category a function f:A⇒B is fully defined by its "application" to points of A. It is important to remember that it is not always the same thing. Not every category is well-pointed.

A category may have cartesian product defined, for a couple of types, A and B, one defines A×B, with two projection functions, to A and B, such that having a function C ⇒ A×B is the same as having a pair of functions, C⇒A and C⇒B; projections provide this one-to-one correspondence.

Note, for instance, that having a couple of points, a:A and b:B is the same as having a point c=(a,b):A×B. So some people believe that a cartesian product is just a "set" of pairs.

A functor F is mapping of types from one category to types of another, and of functions of one category to functions of another, with clearly defined rules (f:A⇒B maps to F[f]:F[A]⇒F[B], composition and identity are preserved. The action of a functor on a function, F[f] is often denoted as map[F](f). Of course map[F](f) is a function from F[A] to F[B].

Note, not every category is a category of sets. For instance the category of all categories is not a category of sets. The category of monoids is not a category of sets. It is important to remember that not everything is a set. For instance, a category of sets is not (usually) a set.

Even if you think you are dealing with the category of sets, it is important to remember that there is no such thing. One can always ask "which one?", and learn that you cannot enumerate categories of sets. We know some, and many more are still hiding, nobody knows how many. We should thank Goedel for this interesting fact of life.

Also, in case you somehow did not know, axioms of any theory, including a theory of sets, are not Eternal Truths Known To The Scientists. They are just assumptions under which a theory is being developed and applied. The same is true about (a) category theory. We do not insist on associativity of functions composition. We just say that in a category, composition is associative.

All this sounds extremely trivial, so it is very frequently forgotten.

Monad

A monad is a any functor M from a category C to itself with two properties:

there is a unit aka "pure" function u[X]: X⇒M[X], for every X and this function behaves (commutes with other functions etc)

there is a monad multiplication aka flatten function flatten:M[M[X]]⇒M[X] for each X, with good properties: a) it is associative, b) unit is left and right unit for this multiplication

I'm not going into deeper details, you can find them everywhere. Just remember this funny thing, that both unit and flatten are defined for each type, and are defined naturally, so a function from A to B combines seamlessly with these.

Being a functor, a monad has map, but there's more.

def flatMap[F,A,B](f:A=>F[B]) = map[F](f).flatten

This function, flatMap, can be used to define flatten, and it satisfies the right rules, which are harder to formulate for flatMap than for flatten.

There's a belief, in Haskell circles, that each monad is also an applicative functor (defined below). This belief has just one foundation: it's based on the belief that every category is well-pointed.

Applicative Functor

There's more than one definition; I'll use the one that does not require anything else except what was defined above.

Applicative functor, aka lax monoidal functor is such a functor F that has

zip[A,B]: F[A]×F[B] ⇒ F[A×B] defined for all A and B, having natural properties and behaving consistently if we have three types, A, B and C;

pure[A]: A ⇒ F[A] that is natural and combines well with zip

There are variants of this definition, where functor strength is defined differently; this one is pretty popular in comp sci, so there.

How can it possibly be related to monads? Here is the way Haskell and Scala people define strength for any monad, just from the definition of monad:

Say we have a monad T, and a couple of types, A and B, there's a trick that produces T[A]×T[B] ⇒ T[A×B]. How? Here's the trick.

1. Define a coupler function, A ⇒ B ⇒ A×B, like


coupler: A ⇒ B ⇒ A×B = a ⇒ (b: B) ⇒ (a, b)

There’s something fishy in this definition. First, It is not a function in our category. We have a function from type A to what? To functions from B to A×B. Funny, the collection of these functions does not belong to our category. We could introduce such a type, X⇒Y, every instance of which is a function from X to Y, or we could, if possible, the sum of units indexed by functions from X to Y. In both cases we will have a type in our category, but remember, they may be distinct. Second, even if our types were covered with instances, like in a well-pointed category, it is still not always so that defining mappings on instances gives us a legitimate function (check out topological spaces, groups, etc).

We map with T, getting a function


couplerT: T[A] ⇒  T[B ⇒  A×B]

For each instance tb:T[B] we canb uild another function, lifter(tb), that takes any function B ⇒ A×B and produces an instance of T[B]:

lifter(tb): (B ⇒ A×B) => T[A×B]

lifter(tb) takes a function f from B to A×B and produces an instance tab:T[A×B] by applying map[T](f) to tb.

See, it's just a special case of map; if you are a Haskell programmer, you would think this is the same as map. Not so from categorical point of view, for a couple of reasons.

Again, this is fishy. We suddenly talk about instances of T[B] as if they are all that we need to define a function. They are not, in general settings where the category is not well-pointed. More, the mapping is from functions to a type; each function gives an instance of a type; it is not even a function in our category.

If we map lifter with map[T] (call it lifterT), we get a function from T[B ⇒ A×B] to T[T[A×B]].

Now, given a couple of instances, ta:T[A] and tb:T[B], from the first we get an instance of T[B⇒A×B], and from this instance and from tb we get an instance of T[T[A×B]]; flatten it, and voila, an instance of T[A×B].

See, we relied on well-pointedness of our category? So many times we relied on the fact that since an A can be covered by its instances, an A×B can be covered by B.

This trick does not work if our category is not well-pointed, as well as in many other occasions. E.g. it is a category of sets on which some group, or a monoid is acting. Or if we are dealing with sets that change in time. Or a category of topological spaces.

This was the first part. Next I'll write about some specific monads and non-monads.

If you want to see an example of a monad that is not strong (that is, not an applicative functor), see the bottom of this: http://mathoverflow.net/questions/85391/any-example-of-a-non-strong-monad/86914#86914

Entry tags:

an impediment

What prevents me from using applicative functors that return, after tensor product, a container of a tuple, is that, before calling some Constructor.tupled, I have to carefully work on the tuple.

E.g.

  getName <*> getDOB <*> getMemberID <*> flatMap (User.apply _).tupled

would be cool, but if User constructor takes first name and last name, and DOB should be converted from String to Date...

In short, I've almost convinced myself to write additional constructors.

But then another impediment. What if I need to check the values and complain if they are wrong. Like, no Sue can be less than 70 years old, right? Something like that. And no 70-year-old can be called Tasha or Brenda or Luanda, right? In short, constructors should be partial functions, then they can be lifted.

Or...?

Entry tags:

strong monads in cartesian-closed categories are applicative functors

Got it eventually. Thanks to

huzhepidarasa and "Applicative programming with effects" by McBride and Paterson.

So, let's see.

In Haskell, in Scala, and I don't know... in PHP? every monad is an applicative functor, with the help of lift2. But I could not figure out where does it come from?

Say we have a category C that has products a × b and power objects, b^a; an endofunctor T is called applicative if it is supplied with two natural transformations,
pure: a → T(a) and (*): T(b^a) → T(b)^T(a) that have obvious properties.

The statement is that every monad is an applicative functor.

Turned out not every monad, but a strong one.

A strong monad is a monad that has a natural transformation t_a,b: a × T(b) → T(a×b) with a bunch of good properties that could be found on wikipedia (are they called coherence? something like that - MacLane studied them eons ago).

Anyway, a strong monad is an applicative functor.

We already have pure; have to define (*).

The trick is this.

Given a binary operation f: a×b → c then we will lift this binary operation (since we deal with a function of two parameters, the operation is called lift2) to T(a)×T(b) → T(c)

Namely, we have

t_T(a),b: T(a)×T(b) → T(T(a)×b)
T(flip_T(a),b): T(T(a)×b) → T(b×T(a))
T(t_b,T(a)): T(b×T(a)) → T(T(b×a))
T(T(flip_b,a)): T(T(b×a)) → T(T(a×b))
T(T(f)):T(T(a×b)) → T(T(c))
m_c: T(T(c)) → T(c)

Composing them, we will have the lift2 we were looking for.

Now take eval_a,b: a × b^a → b, and apply lift2

We will have T(a) × T(b^a) → T(b); currying it, we get (*): T(b^a) → T(b)^T(a)

This may be obvious from the fp point of view, but I am a categorist, not a functional programmer (although you should have seen the rich loops I've been writing lately in Scala), so I needed a sound proof, not just a sound of a proof.

Thank you.

Questions and remarks greatly welcome.