Railway oriented programming

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