Of Algebirds, Monoids, Monads, and Other Bestiary for Large-Scale Data (2013) | Hacker News Reader

Of Algebirds, Monoids, Monads, and Other Bestiary for Large-Scale Data (2013)

michael-noll.com

66 pointsadamnemecek25 comments

I find that monads are easier to explain in the context of programming that in category theory.

First, start with a functor. In terms of programming, a functor is container with an associated function (often called map or fmap -- I'll call it map since fmap simply stands for "functor map"). map takes the contents out of the container, applies a function (which you pass to map) and puts the results back into the container again.

It's important to understand that the function may change the type, so while you have the same kind of container, the type of data inside may change. For example, imagine your functor (container) is an array of integers and your function takes an integer and returns a char. The result of running map on your functor is an array of chars. This may seem trivial, but it is important later.

One other thing to realise is that anything that can "hold on" to a value and for which you can implement map is a functor. So arrays, lists, tuples, hashes/dictionaries/objects etc are all examples of functors. Even a function that has a closure over a parameter can be a functor -- as long as you have a way of implementing map (left as an exercise for the reader).

Monoids are usually not explicitly identified in most programming languages. You can make functors that can contain anything (i.e. the set that represents the values it can contain is allowed to be empty). So basically, you can contain a functor that contains only nothing. A monoid is a functor in which the set that represents the values it can contain can not be empty. In other words, it must be able to contain a value. Also it must have an "identity" value for a given operation. The identity value is one for which when you perform the operation, you get the same value back. For addition and integers the identity value is 0 (n + 0 = n). For multiplication and integers, the identity value is 1 (n * 1 = n). For concatenation and strings, the identity value is "" (s.concat("") = s). Most functors (remember, just a fancy word for container in the context or programming) are monoids for a given operation.

An endofunctor is just a functor (container that you can implement map on) for which the type you start with is exactly the same as the type you end up with. For example, if you have an array of integers, apply a function to the contents with map, and you end up with an array of integers again, then you have an endofunctor ("endo" just means that it's the same on both ends). If you ended up with an array of strings, then it's not an endofunctor because an array of integers is different than an array of strings, even though they are both arrays.

A monad is just a monoid (container that can hold at least 1 element and for which there is an identity element for the function you will be applying) in the category of endofunctors (you'll get exactly the same type after you apply the function).

Usually instead of map (which automatically puts the transformed values into the container) you use a function called bind with monads. bind works pretty much the same as map, except that the function you pass to bind needs to put the transformed value into the container. You would think that this is a PITA, but it's very necessary in many situations (easiest way to see this that I know of is to try to implement an "either monad" with only map -- you'll see right away that it's not possible).

And that's it, really. I find it really interesting to understand how category theory works, but it is not at all necessary for understanding how to use functors and monads while programming.

Edit: I forgot the most important part! Why do a want a monad? Since it always returns the same type from bind as what you started with, it means you can chain functions. I've found that it's also really helpful in non-type checking languages for reasoning about the type of things. If you are using bind on a monad, you know that chaining will work every time -- you never need to check for null, etc.

It's interesting to me that the explanation you give is one that I would call a category-theoretic one, but you see it "in the context of programming". There are so many different views on monads and their ilk. (FWIW, for a programming based explanation I would talk about sequencing operations.)

Yeah... I really just wanted to translate "monoid in the category of endofunctors" into vocabulary that the average programmer would understand. IMHO the article jumped through a bunch of unnecessary hoops even if you wanted to know what that sentence meant.

There are some people that can intuitively understand "monoid in the category of endofunctors", but there are many that don't.

I find it much easier to understand a monad as a general implementation of the interpreter pattern, a monoid as a generalization of things that can be concatenated, and an endofunctor as a generalization of a container. That a monad is a monoid in the category of endofunctors then become an interesting property, not some ab-initio definition.

> In terms of programming, a functor is container with an associated function

A functor could also be a computation whose output can be mapped. So although these concepts can be explained by examples from programming, one has to keep in mind that these are examples and not definitions. For definitions, better to use category theory.

I wish there would be a glossary with such a less arcane and more human-friendly explanation of every term the way you did; wonder why aren't there 'awesome category theory' repo on github yet.

I saw some Bartosz Milewski's video where he spit exactly yours definition of a monad but commented something like "but you have to be twice PhD to understand that".

Not category theory, per se, but this link on functional programming was trending on hn a few months back: https://github.com/hemanth/functional-programming-jargon

Some people have noted that not all definitions are complete or accurate, with many missing altogether. Despite that, it is a pretty good starting point.

I think a lot of people view monads as these esoteric things that provide some kind of FP enlightenment once you understand them when in reality, they're just another layer in the list of abstractions one needs to understand to do "useful stuff" in a language like Haskell.

Without deep diving into a bunch of monad laws, etc, I think you can bring someone around to what a monad is at a basic level pretty quickly by explaining a few basic things.

1) There are values that can have multiple states. Example: a value of type Maybe could be represented as a "box" holding an underlying value (Just 3 or Just "Hello"), or it can be represented as the absence of a value (Nothing).

2) In OOP parlance, you can think of a functor as an interface with a single method (called fmap). Fmap takes two arguments: a normal function that takes a single value and returns a result and secondly a "boxed value". Fmap simply unwraps the boxed value, applies the function to the underlying result and then re-wraps the value and returns that wrapped value as the result. Fmap is smart enough that if you give it a value like (Nothing) it will simply return Nothing.

3) Monads take the functor mechanics a little further by applying a function that returns a "boxed" value to a "boxed" value. The same types of guarantees that a functor provides regarding handling states appropriately (give me Nothing, I will return Nothing) are baked in for you, which allows you to safely chain one call to the next without having to manually check for invalid data. This is done by a function called "bind" which is represented as the >>= operator in Haskell.

Take a contrived function "half" that returns its argument (x) divided by two if the argument is even or returns Nothing otherwise. A "boxed" value is returned in either circumstance.

    half x = if even x then Just (x `div` 2) else Nothing

From here, you can chain calls to half without worrying about whether a previous computation failed.

    Just 20 >>= half >>= half
    (returns Just 5)

    Just 5 >>= half
    (returns Nothing)

    Just 5 >>= half >>= half >>= ...
    (also returns Nothing)

The Maybe instance of bind looks like this:

    instance Monad Maybe where

        Nothing >>= func  = Nothing

        Just val >>= func = func val

As-in, Nothing fed into a function, gives you Nothing back. Just <something> fed into a function gives you the result of the function applied to that value. IMPORTANT: the function returns a "boxed" value because that's what any subsequent call the bind (aka >>=) would expect.

Now imagine that this "off the books" computation can work with all sorts of "boxed" types beyond just Maybe. The additional work being done by each bind call happens independently of the function being provided to bind, so you can do things like logging how a result was calculated, build up stateful data structures, etc... having only written the code to do so one time.

There's clearly quite a bit more to know about monads and their applications, but I think the above is enough to get someone to understand some of the value they provide (at a very high level).

i don't know why you're getting downvoted because spelling out the pragmatics of monads using Maybe is exactly the right way to teach people about monads and gp is committing monad fallacy (though doing a nice job regardless of explaining to people like myself who already know a little)

https://byorgey.wordpress.com/2009/01/12/abstraction-intuiti...

Agreed, in fact, I hesitated to even chime in because there's already so much "dust" around monads that I question the value in adding to the storm. That said, I think Steve Diehl has some great advice regarding understanding monads in his "What I Wish I Knew When Learning Haskell" document.

    Eightfold Path to Monad Satori

    Much ink has been spilled waxing lyrical about the supposed mystique of monads. Instead, I suggest a path to 
    enlightenment:

    Don't read the monad tutorials.
    No really, don't read the monad tutorials.
    Learn about Haskell types.
    Learn what a typeclass is.
    Read the Typeclassopedia.
    Read the monad definitions.
    Use monads in real code.
    Don't write monad-analogy tutorials.

    In other words, the only path to understanding monads is to read the fine source, fire up GHC, and write some code. Analogies and metaphors will not lead to understanding.

I got it the second time, but then again I already knew the answer. A nit: "a value can have multiple states" seems a bit confusing when we're talking about immutable values? Perhaps start out saying something about union types instead?

Already locked for editing. For anyone reading this after the fact, I'd restate as follows.

There are types called Sum Types which are formed by combining other types. Each value associated with a Sum Type is associated with a constructor (label for the value) and zero or more values associated with that constructor.

As an example, a Maybe type could be defined to represent two states as follows:

    data Maybe a = Just a | Nothing

When a value is present, it can be represented as:

    Just 3, Just "Hello", Just [1,2,3], etc.

While missing values can be represented as:

    Nothing

And yeah to be clear, we are talking about immutable values. Boxes that carry around some value (or lack thereof) that never change.

>For example, if you have an array of integers, apply a function to the contents with map, and you end up with an array of integers again, then you have an endofunctor

sorry i'm confused. been learning haskell in parallel with cat theory. isn't the only category in haskell Hask? whose objects are types? in that sense aren't all of the `Functor`s in haskell endofunctors?

A category is just a grouping of mappings that have something in common. When we say "in the category of endofunctors" what we are saying is "consider the grouping of mappings where in the source set and the target set are the same". The "source set" is the set of possible values for the input of the fmap function -- in other words the type of the input parameter. The "target set" is the set of possible values for the output of the fmap function -- in other words the type of the return value. So if you have a container that contains a certain type of data and you can call fmap and it returns the same container with the same type of data, then it can be an endofunctor.

Remember that we are talking about the "category of endofunctors", so it's basically saying "We are talking about operations where you start with a certain type and you return values of the same type". In that way, any monoid is a monad when you return the same type as you started with. You can't use it as a monad in a different context. In Haskell the compiler forbids you from doing it, but it's easy to get it wrong in a langues without static type checking (to much hilarity).

Long story short, using a functor with bind is an endofunctor. Using a functor with map is an endofunctor if your transforming function doesn't change its type, but it's not guaranteed.

There are many many categories in Haskell. All you need for a category is to identify _something_ as the objects, _something_ as the arrows, and make sure your identifications result in something that matches the category laws.

As a simple example, every monoid is a category with a single object (hence the mono- prefix). Hence every monoid in Haskell is a category.

Now it is true that all `Functor`s in the sense of the Haskell typeclass are endofunctors in category theory, because a higher-kinded type can be thought of as a mapping between types in Haskell (e.g. `Maybe` maps `Int` to the new type `Maybe Int`) and `fmap` can be thought of as a mapping of functions between types to their remapped types (we take `a -> b` and replace it with `Maybe a -> Maybe b`), which results in a functor from Hask to Hask.

However, it is not true that the only functors (in the category theory sense) are instances of the `Functor` typeclass.

You are mostly right. Haskell Functors, when thought of as mathematical functors do go from Hask to Hask and thus are endofunctors.

But you also say that "Hask is the only category". That needs some qualification, since the type class Control.Category is also in common use and models mathematical categories. Notice that the standard Functor class doesn't use Control.Category to specify the domain and target, so what you said about Haskell Functors modelling functors Hask -> Hask is correct.

A function passed to a functor as you described it seems to take only a single argument, which is the value(s) from inside the container.

But then, a function passed to a monoid seems to take two values, as in your examples. (addition, multiplication, concatenation) How is this reconciled?

That's a great question. It's hard to visualise and the number of arguments becomes super important when you start moving on to applicative functors.

I'll write in JS just so it's a bit more accessible for people who aren't already doing FP every day.

As you say, the function passed to map, takes only a single parameter, which is the value in the container. So I might have the following code:

  myArray.map(x => x + 1)

This adds 1 to everything in the array. However, instead of just adding 1 (which may or may not be useful), I can close over a different value. Consider the following function.

  let arrayAdd = (array, y) =>
    array.map(x => x + y);

Or to be a bit more idiomatic with most FP languages, let's curry the params to arrayAdd:

  let arrayAdd = a => y =>
    a.map(x => x + y);

So now we have a functor, a, and an operation, arrayAdd, and a is a monoid over the operation arrayAdd. We can use it like:

  let addToArray = arrayAdd(myArray);
  let newArray = addToArray(42);

And obviously if we pass 0 to addToArray it will return us the same array as myArray, showing that 0 is the identity element.

Hope that makes sense!

Thanks. I've found a lot of category explanations that use Haskell types in their explanation, and then a lot of Haskell types that use the jargon in their definition. It's hard to find a foothold from which to build understanding. This is perfect.

This explanation is wrong on several fronts.

1. Your explanation of endofunctor is wrong! You say:

"An endofunctor is just a functor (container that you can implement map on) for which the type you start with is exactly the same as the type you end up with. For example, if you have an array of integers, apply a function to the contents with map, and you end up with an array of integers again, then you have an endofunctor ("endo" just means that it's the same on both ends). If you ended up with an array of strings, then it's not an endofunctor because an array of integers is different than an array of strings, even though they are both arrays."

This doesn't make any sense, you are calling types functors and are saying that what determines whether a functor is an endofunctor or not is what functions you decide to apply fmap to! For example List is functor, List Int is not a functor anymore, it is just a type. And you claim that if xs is of type List Int, and you type fmap (x -> x2) xs then you "have an endofunctor" but if you typed fmap toString xs then you wouldn't have an endofunctor! To repeat xs is just a value, a list, List Int is a type, neither values nor types are functors, and a functor either is an endofunctor or is not an endofunctor it doesn't magically switch allegiance depending on what you use fmap for.

Indeed, when Haskell functors are thought of as mathematical functors they are all endofunctors, functors Hask --> Hask (which makes them endofunctos since the domain and target categories are the same).

2. You misunderstood the sense in which a monad is a type of monoid!

The monoids you mention (strings under concat, integers under addition) are monoids "for products", that is, the domain of the monoid operation is a product type: concatenation is a function String x String --> String, and addition is a function Int x Int --> Int.

Monoids for products are the most important sort of monoids, but are not the only one and are not the sort meant when people say "a monad is a monoid in the monoidal category of endofunctors". There the domain of the monoid operation is not* a product of two types, but is rather the composition of a functor with itself. So a monad has a functor, say M, and comes with an operation M o M --> M (a natural transformation between the functors M o M and M). This natural transformation is the one called "join" in Haskell.

I like your enthusiasm for explaning things simply, but I cannot let these bad errors go uncorrected. If you want to understand these category theoretical terms from a programmer's perspective, I recommend Bartosz Milewski's writings.

Very nice blog post.

When we're at it, have a look at "Functors, Applicatives, And Monads In Pictures"[1]. No silly comparisons to burritos or something like that, only a few pictures that everybody can easily remember.

[1] http://adit.io/posts/2013-04-17-functors,_applicatives,_and_...

Shot in the dark here, but I vaguely remember a blog post that used birds in an explanation for monads and I can't seem to find it again. It had hand-drawn birds, and I think it started out with the identity monad, with the bird representing it only able to speak their own name.

Does anyone remember that post? I'd love to find it again, I got really excited when I saw the title, thinking that it had finally come around again.

Are you referring to the bird songs from Raymond Smullyan's "To Mock a Mockingbird?"

I found this breakdown after a cursory search http://dkeenan.com/Lambda/

Behind the link lies the most confusing explanation of lambda calculus I've ever seen.

Ah you know what, I think I am. I guess I was stuck thinking about Monads rather than the lambda calculus. Thank you so much!

Reply on news.ycombinator.com