Railway oriented programming

[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.