Hacker News new | past | comments | ask | show | jobs | submit login

Can someone explain that in simple(r) terms?



The trouble is that, from a certain perspective, all of those terms are indeed very simple. What they are not, however, is familiar.

Everything I say below will be completely useless to you, because it starts abstract and gets worse from there. You won't be able to apply this to anything immediately. But perhaps it will help you see why these concepts apply to so many things.

A category is a world of two-sided widgets that can be fit together, with a rule that two things can be fit together only if the shapes at matching ends line up. We call the widgets "morphisms" and the shapes of their ends "objects".

A functor is a way of seeing a piece of a category in terms of another category. If we're relating a category to itself, it's an endofunctor. Endofunctors are funny in that, if you're looking at a piece of a category in terms of the whole category, you can find something that looks like that piece itself inside the piece -- it's kind of fractal.

Monads are endofunctors where the infinite regress doesn't really get you anywhere -- if you zoom in by two levels, you see basically the same picture as if you only zoomed in once.

An algebra on a monad is a particular object, and a way to go from the zoomed-in version under the monad back to the unzoomed object at the top. It doesn't work for just any object; only the particular one.

My favorite example of a monad is the Tree monad in the category of data structures. (If you're familiar with programming, imagine the universe of all primitive types and all structs or enums you could possibly define.) The Tree monad zooms in on just the data structures that are trees whose leaves are a particular other data structure, like a tree of ints or a tree of customer records.

Among these tree types is the type of trees of trees of ints; that is, trees whose leaves are themselves trees of ints. It's valid, but a bit silly; we can always just graft each subtree onto the main tree to obtain a tree of ints. The extra level of tree doesn't add anything to the data structure.

A tree algebra picks out a particular leaf type and tells us how to turn a tree over this type into a single value. I can, for instance, explain how to sum all of the integers in a tree of ints to get a single integer. If we have a tree of trees of ints, I need to make sure that summing the subtrees and then summing the main tree is the same as just splicing the subtrees in and evaluating the whole thing. (It is.)

Deep breath.

There are lots of algebras that could exist for any given monad; I just illustrated one for the Tree monad. It turns out that if you take all of the algebras for a monad together, they form a category of their own. Morphisms between algebras in this category are a pair of morphisms in the original category, one going between the types the algebras work over, and one doing the same but within the focus of the monad. They have to cohere in a specific sense.

If this category is complete, then certain general kinds of optimization problems can be solved in that category -- for instance, the kind where you have some algebras and you want to find an algebra compatible with all of them. If it's cocomplete, you can solve another class of problems. (Loosely speaking, one is a minimization problem and the other is a maximization problem.)


Sure. A monad is just a monoid in the category of endofunctors.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: