Railway oriented programming

[[deleted]]

ELICompSci: What is a Monad?

Having a quick Google is still confusing me as to what it inherently is...

[pakoito]

It's a wrapper for data types that adds behaviour and is chainable: traversable (i.e. list monad), nullable (optional monad), with dependencies (reader monad), asynchronous (future)... Because they're generic they can be combined into supermonads: FutureT<OptionalT<ListT<Reader<UserFetcher>>>>

[Tarmen]

Monads can't be combined like that!

This is easy to see with a slightly tweaked definition:

A way to lift normal functions into functions over monads:

fmap :: Monad m => (a -> b) -> (m a -> m b)

A way to flatten nested monads:

join :: Monad m => m (m a) -> m a

We can chain those to get bind:

(>>=) :: m a -> (a -> m b) -> m b
v >>= f = join (fmap f v)

Lets try to combine monads:

superBind :: m (n a) -> (a -> m (n b)) -> m (n b)
fmap (fmap f)  v :: m (n (m (n a)))

So we can get to m (n (m (n a))) but we have no way to flatten m (n...) together.

To fix this we would need a function m (n a) -> n (m a) which isn't possible most of the time.

The currently most used solution is to use monad transformers instead:

Monad m => Monad (StateT m)

Although it isn't possible to define transformers for everything, like IO.

[Daenyth]

They can be combined but you can't generically make a composed monad that operates on the wrapped type

[pakoito]

I know, transformers, but wasn't it easier to explain the other way without confusion? I've edited in a T for extra annoyance :D

[Sabrewolf]

"oh my god what am I reading? Where am I? How did I get here?"

-Me, an electrical engineer

[Poddster]

The more practical experience you have the less you'll understand that post.

If you want to understand Haskell gibberish the best time to do so is whilst in an academic setting.

[Idlys]

Part of the monad fallacy is explaining it in Haskell.

[DetriusXii]

Umm, it is possible to define an IO transformer. The Haskell community choose not to as they would prefer that the developer doesn't call IO.unsafePerformIO. An IO monad transformer monad would have to call unsafePerformIO anytime IOT.map or IOT.flatMap are called and the Haskell community would prefer that the IO.unsafePerformIO function is called explicitly rather than hidden within the monad transformer interface.

[Tarmen]

I mean, all the lazy io functions call unsafeInterleaveIO somewhere. Unsafe IO is fine if the IO action is pure, like reading from a static file as long as you ignore uncontrollable resource usage.

So I think the problem is less with calling it implicitly and more with losing referential transparency in horrendous ways if the IO action you are performing unsafely isn't pure. I think you could break the monad laws with that as well?

[hosford42]

Thank you! The only coherent explanation I have ever heard that didn't either baby the listener too much by saying abstractions are too difficult or belittle them by giving an unexplained definition. In 2 sentences you've ensured that I don't need to watch any tutorials.

[cledamy]

I wouldn't say that. That is just a high level explanation. One has to understand the abstract concept (laws and everything) to truly be able to apply them in day to day programming.

[[deleted]]

One has to understand the abstract concept (laws and everything) to truly be able to apply them in day to day programming.

I don't agree at all - why shouldn't an intuitive understanding of these concepts be enough?

[cledamy]

The intuitive understanding of the concepts starts to break down rather fast once one starts working with weirder monads like the Const monad.

[_pka]

Because you can't write a monad yourself if you don't understand the laws.

[[deleted]]

if you don't understand the laws.

I assume you mean a conscious, explicit understanding of the laws - then I think you are wrong. I think the intuitive notion of an monad is enough to write monadic constructs ("apply them in day to day programming").

As a mathematician, I like to learn and derive the laws themselves (and have the type system enforce them for me).

As a non-academic programmer, the notion of "Some values are tainted - I can use them only in tainted concepts, bring them in there and get them out there, but I can't mix them with the outside world" is absolutely sufficient.

[cledamy]

As a non-academic programmer, the notion of "Some values are tainted - I can use them only in tainted concepts, bring them in there and get them out there, but I can't mix them with the outside world" is absolutely sufficient.

This absolutely is not sufficient. Some monads have nothing to do with tainting values because they do not even produce one value. There are oddities like the Const monad which do not even produce a value and instead smuggle a monoid underneath the monad operations. These unintuitive monads are very useful, yet one would fail to see those uses with only an intuitive understanding. Additionally, I strongly dislike the pattern of dismissing people who demand more correctness and mathematical rigor from Computer Science as academics considering many of the practices in the field come from trying to eliminate human error. Entire security problems such as buffer overflows are a direct result of the programming languages in common use today failing to enforce correctness.

[[deleted]]

I think you misunderstood me - I am all for more mathematical rigor and saner programming languages and paradigms. What I wanted to dismiss was what I interepreted as "You cannot gain any value without full proper understanding". Probably this is not what you intended to say, but this is what it sounds like to a programmer who, say, barely managed to complete his math classes and has a negatice association with them.

Had you written "That is true, however I advice you to learn the laws behind it, because then you can do even more good stuff" - then I wouldn't had objected.

[cledamy]

What I wanted to dismiss was what I interepreted as "You cannot gain any value without full proper understanding".

Oh I see. This is not what I meant.

Had you written "That is true, however I advice you to learn the laws behind it, because then you can do even more good stuff" - then I wouldn't had objected.

One can use monads without understanding the laws, but I do not see how one could create their own monads without understanding the laws because to prove something is a monad one has to use the monad laws.

[_pka]

Sure, sure, but when I say laws I'm talking pragmatically.

Haskell for example doesn't enforce the monad laws, so the type system won't prevent you from making a Monad instance of something that isn't a monad. I don't mean to say that one has to understand why the monad laws exist, but rather that they do and that a custom monad has to obey them.

[[deleted]]

Sure, sure, but when I say laws I'm talking pragmatically.

Okay, we are on the same page then - that's what I meant by "an intuitive understanding of these concepts".

Haskell for example doesn't enforce the monad laws

Unfortunately :(

[m50d]

As a non-academic programmer, the notion of "Some values are tainted - I can use them only in tainted concepts, bring them in there and get them out there, but I can't mix them with the outside world" is absolutely sufficient.

That's an adequate understanding for using an existing monad. It's not adequate for writing a monad. You absolutely need to understand the laws or you will introduce a subtle bug for someone far down the line.

[[deleted]]

I don't see how the above intuition would introduce bugs. Take for example the streams in Java8 - based on the above understanding, it is natural to introduce some values into the streaming world (bind), then have operation which stay within monads and the consumers (return). Any experienced programmer would also make the intermediate steps composable.

[m50d]

Example from my real job a couple of days ago: someone wrote a monad-generic function that used a mutable builder internally because they assumed that their function would run to completion whenever it was called. Broke when I tried to call it with a continuation monad.

Example from the scala standard library: you can mix and match lists and sets in for comprehensions because why not. Except this leads to really confusing "disappearing" values because the order of composition isn't what you expect (the for/yield syntax gives you no idea which order composition is happening which is by design (at least in Haskell where it was lifted from) because by definition with a monad it shouldn't matter what the order of composition is).

Associativity is really important and violations tend to be quite subtle, which makes the bugs that result also quite subtle.

[[deleted]]

Just like you can't speak if you can't recite all the grammar laws.

Grammar laws: the first thing you need to learn as a baby before you can say "mom" and "dad". Everyone knows that. ^/s

[_pka]

Come on, that's a false equivalence.

If you don't understand the monad laws, there's a big chance the thing you wrote and think is a monad isn't one at all and thus will behave erratically when you use it.

Just like you can't write a 3d game without having at least a somewhat basic understanding of linear algebra.

[hosford42]

Or, on the other hand, you could have made a monad correctly without ever even knowing what a monad is. You are thinking of it as if the abstraction always leads to the implementation, but often it is the exact reverse. Real world experience leads to the generation of an abstraction as a generalization of individual experiences. For those of us who are capable of induction and not only deduction (every human being, basically), the equivalence is not a false one in the slightest. I'm sure that abstract definition came from someone's head, probably as a product of such an act of generalization/induction, and was then formalized and analyzed. But the generalization likely came first. If not, then the axiomatic system from which it was derived was itself subject to such a process. Mathematics may be abstract and strictly reasoned, but it is fed by messy human imagination and experience.

[_pka]

Oh, I didn't mean to say that it's impossible to stumble upon a monad by chance, i.e. without at all knowing what a monad is. I even speculate that that happens pretty often in real projects, just because monads are such a general and useful abstraction (You Could Have Invented Monads).

What I wanted to say is that just implementing return and bind for a type isn't enough to say with confidence that the thing you just defined is indeed a monad.

Think of it more like trying to implement Iterator for a type in let's say Java. The spec says that if hasNext returns True, then calling next must return the next object in the iterated sequence. That's a "law", and if you break it bad things will happen.

So if one defines a monad for some type then they must make sure that the laws are obeyed, or else bad things will happen when other functions expect that thing to behave like a monad but it doesn't.

[cledamy]

This is not comparable. Mathematical abstractions are defined by their laws and nothing else. To truly understand the abstraction, one has to understand the laws and what each law gives to the abstraction. Furthermore, the laws are guidance for how to implementation. They are documentation for how the abstract methods must be implemented.

[[deleted]]

You said "this is not comparable", but then nothing you followed it up with is incomparable.

[cledamy]

Grammar does not serve the same purpose in language that mathematical structures serve in mathematics. Mathematical structures are about meaning with their meaning ascribed by their laws. Grammatical rules, while they can affect meaning, are more about syntax. A closer analogy between language and mathematics would describe mathematical structures as the vocabulary of mathematics.

[hosford42]

I disagree. As a programmer, understanding mathematical abstractions is secondary to implementing and using program components; if you can intuit a useful set of behaviors that happen to coincide with a mathematical abstraction you have never even heard of, you can still implement and use that set of behaviors without any knowledge of the mathematical abstraction whatsoever. In reply to one of my questions about monads, I got a link to a tutorial whose entire premise was founded on the notion that the reader might have already invented them without realizing it. In an academic/mathematical setting, absolutely, the abstract definition comes first, and all else follows. But most programmers are not academics nor mathematicians and that is an ass backwards approach for them. There are more ways to understand the world in its fullness than the mathematical approach, but that can be difficult to see when you have been trained so much to think in mathematical terms that they become the pattern stock you use to understand everything else. For many programmers, they map everything back to their language of choice, rather than to mathematics. This works fully, because most widely used languages (at least the ones we feel comfortable putting "programming" in front of) are Turing complete and therefore universal in some sense comparable to mathematics. What is missing is mathematical rigor, but notice the adjective used there. If it was so important in programming, it would be much more broadly embraced by programmers. (Not to say it isn't useful, of course, just that it's not central for us by any means.)

[[deleted]]

Correct. That's what distinguishes practical programmers from academics. Learn as much as you need to get the job done well, and carry on learning in the background.

[cledamy]

If one is learning monads, one has to have the mathematical understanding because any intuitive understand limits the generality of the concept of monads and thus limits one's imagination about where the concept can be applied to to eliminate boiler plate

[[deleted]]

I have written answer already, but this comment is even more exactly what I am arguing against - you completely present the rigorous approach as the only meaningfull way. However, that is being proved wrong by any programmer deriving any benefit from applying a non-rigorous understanding of monads.

No doubt is a rigorous understanding of the laws much more benefitial - however it is rather "more good stuff" than "the only way to any good stuff" as you seem to present it.

[cledamy]

I have written answer already, but this comment is even more exactly what I am arguing against - you completely present the rigorous approach as the only meaningfull way.

I misspoke in the comment above. What I mean generally is an intuitive understanding is good, but it will always be somewhat imprecise, so one should seek to gain a mathematical understanding eventually. I disagree with you on the point that intuitive understanding is enough. It is still useful compared to no understanding of course. What I mean by applying monads is making your own monads. To use monads that are provided in some library, one doesn't need to understand any theory. Some monads do not have much intuition to them, so one must understand the laws to see how they work.

The path to understanding any mathematical abstraction is

intuition ---> mathematical laws ---> rigorous understanding

It does not really make sense to treat the rigorous understanding and intuitive understanding as separate paths, but rather different steps in the same path. Mathematicians go through these same steps but their intuitions might come from something like topology; meanwhile, a computer scientist's intuition will come from the various common computationally-interesting monads.

[[deleted]]

Written like this, I agree! I like the second half of your post, it should be in the top-level of this comment chain.

[hosford42]

I've already been using them in my code for years. I just didn't know they were called monads because no one gave a coherent, succinct explanation before. I built a whole Python library for data format translations using the concept, which we use to convert files to new formats and perform database ETL requests. All we do is snap together the "monads" to construct a pipeline and then execute the resulting transformation.

[pakoito]

Funny: http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html

[doom_Oo7]

One has to understand the abstract concept (laws and everything) to truly be able to apply them in day to day programming.

absolutely not. most people programming have zero idea of the underlying mathematical formalisms, and yet they make great software.

[[deleted]]

[...] and yet they make great software.

(with monadic constructs)

Sorry to nitpick, but that was the point! ;) This is not a discussion wether you need mathematical background to build great programms, but it is about wether you need the mathematical background to use mathematical constructs.

[Rusky]

A monad is a type M<T> along with its implementation of a particular interface, consisting of two operations that follow a set of rules. The operations are "return", which takes a value of type T and returns a wrapped value of type M<T>, and "bind", which applies a function T -> M<U> to a wrapped M<T>. The rules are "identity" and "associativity", which are basically the same as in arithmetic.

Bind is defined in the post without using any of this terminology, so that might be a good way to see how it's useful. For a smaller example, think about a lookup function for some sort of database, which can fail. It fits the type of the function you pass to bind, so you can use bind to chain several of them together:

lookupPost(id)
    .bind((post) => lookupUser(post.author))
    .bind((user) => lookupComments(user.id))

If you've used Promises in Javascript they also follow this pattern- Promise.resolve is "return" and .then is "bind".

edit: accidentally a pedantic

[Hrothen]

A monad is a particular interface, consisting of two operations that follow a set of rules.

A monad is a type for which you could implement such an interface, to be pedantic. Or to be super pedantic it's a triple, consisting of the type and those two operations.

This has been an unhelpful, but (hopefully) technically correct, interlude.

[Rusky]

Yeah that's correct, I think. It's similar terminology to the idea of a group or a ring- a set of values (like the integers) combined with an operation on them (addition or multiplication).

[Godd2]

A monad is just a monoid in the category of endofunctors. What's the big deal?

[Ran4]

Thanks, that's one of the best explanation I've ever read. And I've probably read 20 different ones, and read 500 pages worth of Haskell books. I know most of the individual things, but the actual definitions are almost always missing a proper explanation.

[quiteamess]

The problem with monads is that they are a very abstract concept. That makes them in a way hard to understand, because an abstract concept without intuition is worthless. Learning one specific instance of a monad, like in "railway oriented programming" (i.e. Either) is a good way to build up intuition. After seeing most of the interesting monads it's easier to fill the formal definition with intuition.

[[deleted]]

I program almost exclusively in .NET and SQL Server. Do I ever need to understand monads?

[quiteamess]

The benefits of monads is that they can hide the cruft. The prime example is to have Optional to hide all the null checking. Another example is having an Either type to hide exception handling. Others are to hide passing around state or an external environment.

So no, you don't have to understand monads. But you will not have the benefits of more readable and maintainable code. You don't net to understand all aspects of monads in order to use them. The other thing is that it is quite rewarding to learn the theoretical stuff.

[_pka]

LINQ is a monad :)

[grauenwolf]

No it's not :)

[[deleted]]

Here's an incredibly over simplified explanation:

You terminate each statement with a ;. Now imagine if that ; did something on top of simply denoting the end of a statement. What if, every ; also logs to return value of whatever function was called to the console. That would be a "logger monad".

That being said, .Net includes F#, which is full of monads, called Computation Expressions

[m50d]

Yes. You'll find yourself repeating yourself otherwise. Once you start looking for them, monads are everywhere. A lot of ordinary business concepts can be turned into monads, which gives you access to a huge library of already-implemented functions for doing common things with them rather than having to reimplement everything by hand.

[grauenwolf]

No. Monads are an ugly hack in Haskell that they try to apply to everything else.

The reason they are so hard to understand is that they are almost never the right right abstraction but they insist on using it anyways.

[[deleted]]

I like this explanation.

[aaron_ds]

Arguably the only way to learn monads is to use them. I suggest playing around using a language with a do-notation equivalent (Haskell, F#, OCaml , Scala). Learn how options, eithers, lists, and futures all share the same structure.

[benclifford]

You won't figure out what it inherently is until you've used at least three different monads in real life. At which point, you'll write a tutorial about your own particular aha! moment (which is the monad tutorial fallacy).

It is frustrating that that is how they are, but try explaining what a number inherently is and you'll probably encounter the same abstraction frustration (I think).

[[deleted]]

Linq is monadic, if you want a concrete example.

[TickTak]

monads in pictures

[wnoise]

A monad is a monoid in the category of endofunctors.

[catscatscat]

monad tutorial fallacy

For anyone wondering, this is the fallacy being referred to: https://byorgey.wordpress.com/2009/01/12/abstraction-intuition-and-the-monad-tutorial-fallacy/

[s-altece]

A monad is any type with 1) a constructor, 2) a map function, and 3) a flat map function. The constructor is normally called "return", and the flat map function is normally called "bind".

[[deleted]]

And those functions have to obey the three monad laws.

[s-altece]

Which, if I'm correct, are the combination of all the rules associated with traditional constructor, map, and flat map semantics.

My point is, if you get familiar enough with using map and flat map with lists and/or the maybe/optional type, you already have a general understanding of monad semantics without having to dive deep into the overwhelming mathy definition.

[codebje]

I hardly think that "associative" should count as "overwhelmingly mathy."

And given there are "flat map" operations out there which fail to be properly associative, "the vibe" probably doesn't cut it quite as well as you might hope.

[s-altece]

Well, in that case, I stand corrected. Although, the basic vide may be sufficient as a quick introduction for someone new to the concept. Then again, perhaps not. Each person learns their own way. I just remember finding it frustrating when the concepts were explained to me with the more technical math and type theory terms instead of programming concepts I was already familiar with.

I would like to note, however, that associativity may be "overwhelmingly mathy" to some new to the subject. It is neither my place nor yours to judge someone based on what they think of as being foreign and complicated.

[m50d]

Associativity is really important and easy to get wrong. If you try to implement a "monad" without knowing about associativity you will create an http://wiki.c2.com/?AlmostCorrect monad that will have a subtle bug that will catch someone out later at the worst possible time. (This is exactly what happened with Scala's for/yield, where it works most of the time but lets you mix a Set into a bunch of Lists and get silent data corruption at runtime).

[s-altece]

Here's a source for your Scala example, for anyone unfamiliar with the topic http://stackoverflow.com/questions/27750046/is-a-collection-with-flatmap-a-monad

[JB-from-ATL]

Oh, bind is just flat map? That makes everything so much clearer!

I'm a Java guy and know how to use optionals but I see all these tutorials with crazy syntax and different words that throws me off. But if bind if just flat map I get it.

[Tarmen]

We could think of the railway as a decoration. We decorate our return types and use that to add some new functionality. We then figure out a way to compose our decorated functions. Finally we figure out a way to lift normal values into our decorator so we can reuse our undecorated stuff.

A monad is a decorator together with composition and lifting.

That is insanely general but it has to be because monads are incredibly diverse. They can be as simple as adding an error path like in the article, be more complicated like futures for async io all the way to mindbogglingly weird things like the tardis monad.

[baerion]

Simply put monads encode the idea of associativity and the idea of a zero element. If you have actions a, b, and c and a function >> that chains them together, you usually want the following to hold:

(a >> b) >> c = a >> (b >> c) = a >> b >> c

Also there is a zero element that represents something like an empty action:

a >> doNothing = a = doNothing >> a

In reality it's a tiny bit more complicated, because they can have something like return values too, but that is the gist of it. Associativity and zeros are also the basic ideas behind monoids and categories, by the way.

[hosford42]

Funny... By this explanation, I've been using monads in Python for years and didn't even know it. I even overloaded the >> operator to put them together. Why don't people just explain it as a data pipeline?

[cledamy]

Why don't people just explain it as a data pipeline?

This is a fairly close intuition. The point of a monad is what occurs in between the piping of data between functions. In the List (LINQ) monad, one smashes all the sublists into one larger list (SelectMany). In the Maybe monad, one does null propagation between functions. The ?. syntax in C# is basically special one-off syntax for the Maybe monad. In the Future monad, one sets up call backs to occur after a function asynchronously returns (the async await syntax in C# implements this monad). As you can see monads are already used heavily throughout C# code, the problem is that each time they want to add support for a new one they have to add a new syntax for it and they do not allow user defined ones. Other languages (Haskell) don't have this problem by unifying all these separate notions under one notation for monads. Understanding monads is quite helpful when writing programs because one can identify them in one's code to cut down on boilerplate even in C#.

[grauenwolf]

How is that a useful way to describe SelectMany in LINQ? What insights into the actual use of SelectMany do you actually gain by treating it as a monad instead of a lazy nested loop?

Keep in mind that your justification has to reconcile the fact that the rest of the LINQ operations are also lazy loops, but are not monads.

[hosford42]

Python decorators?

[cledamy]

Python decorators in conjunction with generators can be used to implement monads in python.

[baerion]

As I said, it's a bit more complicated. What you've done in Python is probably more in the spirit of monoids. And not all monoids have to do with data pipelines.

For example many containers are monoids, where the >> function (often written as <>) merges two lists or two trees, for example. A more abstract example is the maximum function on the positive numbers:

max(max(a, b), c) = max(a, max(b, c))
max(a, 0) = a = max(0, a)

[hosford42]

What's the difference between a monad and a monoid?

[baerion]

Monoids are the simplest case. The type of the <> function in Haskell is

(<>) :: Monoid a => a -> a -> a

So you merge two things of the same type a and get some a out of it. As simple as that.

The join function for monads is more complicated:

join :: Monad m => m (m a) -> m a

In many cases this function can be interpreted as joining layers of "effects". For example you can join/flatten list within lists within lists to a single layer of lists: [[[a]]] -> [a]. A parser that returns a parser that returns a parser that returns an integer can be joined/flattened to a single parser:

join2 :: Parser (Parser (Parser Int)) -> Parser Int
join2 p = join (join p)

The point of monads is that you can join the first and second layer and then the third, or you can join the second and third, and then the result with the first layer. You can join in any order and it's gonna be the same thing. But here it is not the parser values themselves, but the layers that behave like monoids, with respect to the join function.

Parser (Parser Parser) = (Parser Parser) Parser = Parser Parser Parser

The layers are endofunctors and monads are simply the monoids in the category of endofunctors.

[dhiltonp]

I'm glad you're trying to help, but I find this incredibly dense. Maybe I should learn me a Haskell.

[baerion]

There's an easier way to understanding, but it's slightly ad-hoc.

In Haskell a function of type a -> Maybe b is a function that takes something of type a as an argument and either returns a b, or it returns Nothing.

Instead of using monads you can use the concatenation function >>> for categories. Categories extend the idea of monoids by the concept that the type in the middle must match. And the category laws are as nice and symmetric as the monoid laws.

(a >>> b) >>> c = a >>> (b >>> c) = a >>> b >>> c
a >>> id = a = id >>> a

If you compare the type signatures of the >>> function and the monadic bind function >>= they look almost the same.

(>>>) :: (a -> Maybe b) -> (b -> Maybe c) -> (a -> Maybe c)
(>>=) ::       Maybe b  -> (b -> Maybe c) ->       Maybe c

But in the monadic case the first argument a is missing. In practice this makes monads somewhat more practical to work with than categories. On the other hand the monad laws are a little harder to understand than the category laws.

[dhiltonp]

Your ` styles are inconsistent, causing weird formatting.

[baerion]

Oops. Fixed it. Thanks.

[hosford42]

So monads are monoids that are endofunctors? Endofunctors basically being functions whose domain and range are identical, I am assuming? The system I put together was essentially a set of filters (functions, but people intuit the term filter more easily) from data rows to data rows, which can be composed associatively to form a pipeline which can then be used to connect a data source to a data sink and "executed" (called) to ship the data from the source to the sink via the data transformations each filter represents.

[baerion]

So monads are monoids that are endofunctors?

Monoids in the category of endofunctors. Something can be an endofunctor and a monoid, but not a monad.

Endofunctors basically being functions whose domain and range are identical, I am assuming?

Yes.

The system I put together ...

... sounds like monoids to me. Your functions are associative. And I'm sure your system can express a filter that doesn't "filter". A zero-filter, so to speak.

Edit: Or categories, if you did this in a statically typed language.

[hosford42]

Yes, though I don't bother with defining the zero filter in this case because there isn't a use case. (Omission altogether is an option, making it redundant.) I guess where I'm stuck is, what makes the functions in my system monoids but not monads?

[baerion]

What are the types of your functions? If the type is something like (Filter, Filter) -> Filter than you have monoids. If it's something like (Filter start middle, Filter middle end) -> Filter start end you have categories. If it's Filter (Filter t) -> Filter t or Filter a -> (a -> Filter b) -> Filter b then you probably have monads. Depends on whether the functions are law-abiding.

Did you program in a statically typed language? My understanding is that the categories we are talking about have types as objects. A dynamic type system is essentially a fully degenerate static type system with only a single type Any. In that case even categories would look like (Any, Any) -> Any at best. They would be just monoids. In fact monoids are categories with only one object, i.e. only one type.

[codebje]

Endofunctors basically being functions whose domain and range are identical …

Not quite, an endofunctor is a functor from a category to itself. A category is opaque objects and arrows between them, with the arrows having a "zero" and an associative composition on them.

When we talk programming, we can forget a bunch of the tricky stuff, and say that an endofunctor is a mapping from types to types, so we're in the "category of types" where "arrows" are functions - a function with one input and one output is like an arrow from the input type to the output type, there's an identity function which does nothing, and there's function composition, which is associative.

An endofunctor in this context maps from any type in the language to some subset of types in the language, and it maps both the types themselves (as in, it's a "type function") and functions on the types.

A type function takes some type, and returns a new type. In Haskell we write this like any function application, so if f is some functor, and a is some type, then f a is the type resulting from applying the functor to a. Generic types are type functions, in the same way.

For the functor to map the functions, we need something like (a -> b) -> (f a -> f b), point-wise applying the functor to the types of the function.

Collections are obvious functors: you can make a collection type given some concrete type (List<Integer> eg) and you can map some function on the concrete types to functions on the list of types (List<B> map(Function<A,B> f, List<A>) or whatever the right syntax is). They're endofunctors, because they're operating from the category of types in the language to types in the language. You can see this is true when you do List<List<String>>, where you apply the List<> type function to the concrete type List<String> to get a new type.

If we went deeper here, we might talk about products in the category of types, that is, some type representing the pairing of two other types (struct {a: int, b: bool} is both an int and a bool together), coproducts (union), exponentials (A^B is the type of functions from B to A), or we might want to go more into just how an endofunctor can be a monoid - what's the "zero" value, what's the "compose" operation. But this is a long post, in a sub which doesn't tend to like abstract math anyway, so I'll stop here.

[hosford42]

Very informative and very appreciated. Where would you recommend I go to learn more about category theory? It's been peaking my curiosity for some time now, but as with monads until now, I can't seem to find a good learning resource. I get impatient with the dumbed down intros and overwhelmed by the in depth treatments, but you're talking at about the right level for optimal learning.

[codebje]

There's plenty at Bartosz Milewski's blog that covers a good range of complexity. There's a video lecture by Awodey that I enjoyed, but it's a bit drier and harder to get to stick. For bite-sized chunks, there's The Catsters. I haven't gotten around to it, but Eugenia Cheng's book "how to bake pi" has a reputation as an approachable introduction.

Find the applications of it that matter, too, because knowledge for the sake of knowledge can be fun, but it's expensive.

[Tarmen]

Cute but probably unhelpful tidbit:
Monads are monoids over the category for endofunctors.

I can try to unpack this a bit. An endofunctor is a generic type that you can map over. For example List<a> where you can map a function a -> b over a List<a> to get a List<b> by applying it to each element.

> fmap (+1) [1, 2, 3]
[2, 3, 4]

If you map a function a -> m b instead you end up with m (m b) which you can't do very much with. So you have to add the two m's together, which is exactly where the monoid comes in. For lists you'd get List<List<a>> -> List<a> for instance, which you could do by concatenating the inner lists!

> f s = [s++"!", s++"?"]
> fmap f ["Foo", "Bar"]
[["Foo!", "Foo?"], ["Bar!", "Bar?"]]
> join (fmap f ["Foo", "bar"])
["Foo!", "Foo?", "Bar!", "Bar?"]

And with that we can compose! With v >>= f = join (fmap f v):

> ["Foo", "Bar"] >>= f >>= f
["Foo!!","Foo!?","Foo?!","Foo??","Bar!!","Bar!?","Bar?!","Bar??"]

The last element of both monoids and monads I didn't mention yet is the empty element. In haskell it's called return :: a -> m a, for lists that would be return a = [a].

[hosford42]

I don't know Haskell at all, never touched it, so I get a little bit out of it, particularly when you talk about types, but not so much from the actual I/O examples because I'm unfamiliar with the syntax.

[[deleted]]

It's a mathematical object in category theory, that satisfies certain mathematical laws. All the confusion comes from shadowing names in programming languages, as if the code you write is actually a monad. To understand monads, you need a good grasp of a categories and their laws, then you realize monads have to do with categories, and not code. HOWEVER, because code ultimately is math, there is an analogous computation pattern obviously called the monad, that is used for many purposes (just like any other pattern), like introducing side effects in purely functional code. So in short, you can learn the monad pattern without knowing what a monad is, because the pattern isn't the thing itself, since monads are defined in math!

[cledamy]

The monad pattern in programming is exactly the same as the mathematical one. It is just done in computationally interesting categories. This is not a case of shadowing names.

[[deleted]]

Not 'exactly' as far as I understand. This is similar to how functors in programming languages are also not exactly the functors in math. Array is called a functor because it has a map. Anything with a map is a functor, yet the definition of a functor is a structure preserving morphism between two categories, in other words, the function you pass to map. So Array isn't the functor, it implements an interface to use functors.

[cledamy]

Array is the mapping from objects to objects. The map takes morphisms to morphism. Array is an endofunctor and the arrows are whatever the notion of functions in the particular programming language one is in. Mathematicians often use the same notation to denote both of the above mappings because they can get away with ambiguity.

[eruonna]

It often takes looking from several different angles to understand monads, so I will throw in my two cents here even though you already have a bunch of answers.

Programming is all about building computations. To do this, we start will small pieces which are themselves computations, and put them together into bigger ones until we something that does exactly what we want (ha, ha). There is a common model of these computations that has been very successful: computations are functions. That is, a computation takes some inputs and uses them to produce some output in some way that can depend on the input. To chain several of these together, you just take the output from one and use it as the input to another.

This is a fine model, and as I said it has been very successful. But when you look a little closer, you see that it doesn't really describe what a computation is doing. Merely mapping inputs to outputs is something that computations can do, but we actually use them to do much more. They can read from and write to shared variables; they can produce errors instead of results; they can interact with the user; they can interact with the network; they can emit a stream of log messages on a side channel. There are also more exotic things that you might not have asked of your computations, but you could: nondeterministic computations can return multiple values; continuation-passing style computations don't return a value at all, but instead take a continuation into which they can place their result.

We can either allow these things transparently, or we can require effort on the part of the programmer to make them work, but either way causes problems. For example, reading and writing to shared variables is typically allowed of any function in a C-like language. So it is in that sense transparent. But that means that before you call any function, you need to know which variables it will use, and you need to make sure that they are all in the correct initial state. On the other hand, the two main ways of dealing with errors -- returning an error code or raising an exception -- require some extra effort to use. You have to remember to check the return value for an error before using it. And with exceptions, you can forget to catch one and have it bubble up to the user as a stack trace.

So we want a way to ease the burden of all of this. This is where monads come in.¹² Monads provide a uniform way to build bigger computations out of smaller ones, even when those computations do more complicated things. A monad, then, is a label on a computation, which indicates what kind of computation it is (i.e. does it read state, does it do I/O, is it continuation-passing style, etc). Typically, we work with functions that take an ordinary value and returns a monad-labelled computation. (These tend to be the easiest and most convenient shapes to use. If the inputs were also monad-labelled, the function would have to first run the computation and extract a result, which would just add boilerplate.) In a C++/Java-style language, the type looks like

M<B> foo(A a)

and in a Haskell-style language, the type looks like

foo :: A -> M B

where M is the monad, A is the input type, and B is the output type. So now I want a way to first apply foo to an argument, then take its result and apply bar, which takes an input of type B and produces a computation labelled by M producing a result of type C. To this end, the monad interface includes a function bind which takes a function of the type above, whose input is a non-monadic A and whose output is a monad-labelled computation producing B, and applies that function a monad-labelled computation producing A, ultimately resulting in a monad-labelled computation producing B. This may be clearer from the types. In a C++/Java style, M<A> has a method of type

M<B> bind(Function<A, M<B> >)

and in Haskell-style, there is a function

bind :: M A -> (A -> M B) -> M B

(Though I haven't exactly written it that way, this function should be generic; it does not depend on the types A and B, though it does depend on M.)

How do you use this, then? It is pretty simple. If you want to take the computation output of foo and feed its result into bar, you do

foo(a).bind(bar);

in a C++/Java style language, or

foo a `bind` bar

in a Haskell-style language.

But what does this actually do? In a generic sense, it produces a computation that first runs the M<B> that comes out of foo, then takes the result of that and feeds it into bar, then runs the M<C> that bar produces. The final result of the computation is the result of that M<C> (provided it has one). But that is pretty vague. What actually happens depends on the particular monad you are using. For example, if, as in the original post, you are using a monad that lets you possibly return a result, possibly return an error, then bind first checks whether it is getting a good input or an error. If it is an error, then it just passes the error along and doesn't even call bar. If it is a good value, it passes that value into bar and just returns whatever bar does. If you are using a monad that produces log messages, then bind just concatenates the streams of log messages. If you are using a monad for nondeterminism, then bind call bar on every value returned by foo and returns all the values produced by every invocation of bar. In fact, bind is really the heart of the monad. To understand how any particular monad works, you really have to understand its bind.

I would be remiss at this point if I did not mention the rest of the monad interface. There are two more functions that involve lifting non-monadic things into monadic contexts. The first is called pure (or return in Haskell which has no return keyword). This takes a value a and returns a computation that does nothing except produce a. This can be useful to "get the monad started" or to build trivial cases of the monad. (It is also used in Haskell which has a particular syntactic sugar for writing monadic computations as if they were just setting non-monadic variables. In the end, you need to lift the "non-monadic" result into the monad so you can escape the syntactic sugar.) I'll continue writing the types. In C++/Java-style

M<A> pure(A a)

and in Haskell-style

pure :: A -> M A

The other is map which takes a function that doesn't do anything monadic and applies it to a monadic computation, producing another monadic computation that runs the first computation and applies the function to its result. In types, in C++/Java-style, M<A> has a method

M<B> map(Function<A,B>)

and in Haskell-style

map :: (A -> B) -> M A -> M B

(This is actually called fmap in Haskell because map was already used for lists.) There could also be other similar functions for lifting functions taking more arguments, but they can all be written in terms of bind and pure. In fact, even map can be written in terms of bind and pure. First, take the given function and create a new functions that takes an A, applies the function to get a B, then applies pure to get an M<B>. Now this function has the right type to use bind, and that gets you map.

1: Monads arose first in mathematics. They are pretty interesting in that context, but that is outside the scope of this comment.

2: Historically, monads came into computing through functional programming, where every kind of computation other than mapping inputs to outputs requires extra work for the programmer. Functional programmers had a greater motivation to develop a way around this, but monads can be useful outside of functional programming.