From Design Patterns to Category Theory (2017)
blog.ploeh.dk
blog.ploeh.dk
For context, when I first became aware of the Mark Seemann, he was very deep into the object-oriented way of doing things. I discovered him because he was the author of (the excellent) Dependency Injection in .NET. A while after writing that book, he started getting into F#, and eventually Haskell, and blogged about it all the while. The upshot being, his blog archive now tells a fascinating story of the evolution of one person from being a an extremely accomplished object-oriented programmer toward being a serious functional programming advocate.
He's also done a very good job of explaining what FP has to offer to an object-oriented programmer, or at least one who likes a certain style of OOP. For example, see https://blog.ploeh.dk/2017/01/27/from-dependency-injection-t...
He's on a couple of episodes of .NET Rocks podcast too, definetly worth a listen.
I think I remember seeing Seemann write on his blog that the new version is a much better reflection of his current thoughts on how to do DI, and object-oriented design in general, than the first edition was. In particular, the 2nd edition is much less focused on heavyweight tools, and takes an overall cleaner approach to things. Nowhere near as much Castle (the .NET equivalent of Spring) type stuff.
[1]: https://www.manning.com/books/dependency-injection-principle...
I would say category theory is the wrong title for this, though. Category theory is occupied with the algebras that emerge when you put algebras into the same space and look at mappings among them. It emerged in algebraic topology where you would construct a family of algebras that describe aspects of a geometric structure and then establish connections among them to talk about the effects of operations on those geometric structures. Categories gave you one algebra, functors gave you families of algebras, and natural transformations gave you operations on the underlying spaces.
Many of the algebras described here and others that I have found useful emerged earlier in abstract algebra or universal algebra (monoids, lattices) or in parallel in combinatorics (magmas).
The category theoretic view is often an inconvenient setting. Lattices, for example, are best dealt with simply as a set with some operations that obey specific axioms. You get theorems from the axioms, and if you need one of those theorems to apply to your system, you make sure you implement it in such a way that it obeys those axioms.
Or if you have an algebra near to what you need, you may be able to modify it in the abstract setting to keep properties that you want. I ended up doing this with lattices to describe tagging regions of genomes.
So I disagree, I think the title is right. If you don't go as far as category then you've stopped short of the biggest pay-off.
That is an interesting description of design patterns, and not one I've heard before.
As it happens, today I was thinking about semirings, and how to apply them to discrete event systems[1][2], and was fascinated to see that both algebraic geometers (Alexander Grothendieck) and computer scientists (Robin Milner) were doing[3] some of the same[4] sorts of tricks to transfer algebraic structures (like rings) over to settings lacking an inverse (like semirings)--rather than take the direct approach (as you mentioned in your lattice example):
There are many times in mathematics where some class of objects has a nice additive structure, except that one can’t always invert elements. One approach is to say, “oh well,” and develop the theory of monoids; another,which we’ll discuss today, adds in formal inverses, in effect pretending that they exist, and uses them to recover something useful.
[1] https://www.cl.cam.ac.uk/%7Esd601/papers/semirings.pdf
[2] http://r6.ca/blog/20110808T035622Z.html
[3] https://web.ma.utexas.edu/users/a.debray/lecture_notes/sophe...
[4] https://old.reddit.com/r/haskell/comments/2d8q24/additivemul...
The agreement part is that the algebraic structures that naturally arise in my programming experience are indeed ultra-basic: monoids, lattices, semirings, partial orders, and so on. (When I need elementary linear algebra things are getting fancy!)
The disagreement arises from the fact that the right home for these basic concepts is often surprisingly exotic. For example, it's often the case that what you need is not a monoid in the category of sets, but in the category of sets and relations or partial orders and monotone functions.
Another example is when you want to represent syntax trees with scoped binding structure. Now a syntax tree is the dumbest possible algebraic structure (it's a free algebra with all generators and no relations), but when you have binding you need a free algebra in the category of presheaves over finite sets and injections.
Rest assured, you absolutely do not need any category theory to be an effective functional programmer. Everything is a category because category theory is the most general formulation of algebra. But you don't need to know categories for any of it. Not even for monads.
It's like trying to use calculus of variationsnto find the area of a triangle. You can so it, but it's pointlessly overcomplicated overengineering. Chasing after ever-higher abstractions when you only have one concrete case to abstract over, is the functional programmer's version of OO architecture astronautry.
Certainly most of the "category theory for programmers" tutorials I've seen have the flavor of an undergrad algebra course: starting out with a long introduction about why you should care about abstract structures, then giving a few definitions.
The only difference is that for some reason they dive right into esoteric definitions like "monoids" and "magmas" and "monads" instead of the bedrock useful things from algebra like "groups", "rings", "fields", etc.
By the way, "monoid" and "magma" are no more categorical concepts than "groups" or "vector spaces" or anything else, reinforcing my suspicion that categories are not the fundamental thing people care about here.
> Notice that there's more than one way to combine numbers. You can add them together, but you can also multiply them. Could there be a common abstraction for that? What about objects that can somehow be combined, even if they aren't 'number-like'? The generalisation of such operations is a branch of mathematics called category theory,
You would think the author was about to introduce the concept of a "group" here. Literally if you replace "category theory" with "group theory" here, the entire paragraph still makes sense. What in the world is the point of talking about categories here? Again, when people say "category theory" do they really just mean "algebra"?
It's weird. I really don't get how this caught on, and to be honest it feels a bit like cargo culting. As someone who studied math, it seems ludicrous to me that someone should care about category theory without having studied algebra first. It's like memorizing the C++ standard without ever having written a real program. The whole point of categories is to generalize algebraic structures; how can you appreciate the point of them without actually having seen any concrete algebraic structures?
A remark: from a programming perspective, monoids are not esoteric, and are indeed more important than any of the intro abstract algebra structures. This is because free monoids are ordered lists, the most fundamental data structure in all of programming.
You can have a long and productive career as a C programmer knowing nothing but how to create and iterate over arrays! Monoids are so important that every single modern language (from C++ and Java all the way to Haskell and Scala) devotes a HUGE amount of language and standard library surface area to render data structures as sequences.
They are so important that even a language like Haskell is willing to accept utterly nonsensical semantics (hello, Traversable) to better support sequences.
I've mostly ignored Haskell for the past decade. What happened with Traversable?
True.
> Monoids are so important that every single modern language (from C++ and Java all the way to Haskell and Scala) devotes a HUGE amount of language and standard library surface area to render data structures as sequences.
Yes and no. Yes, they devote a huge amount of language and standard library surface area to sequences. No, nobody in C cares about that being a monoid, or is thinking about monoids when they use sequences, just like no NBA players think about general relativity when they're shooting a basketball. With C++... maybe a few think about it that way.
Well, I think unsigned integers are even more fundamental than ordered lists, and those behave as the ring of integers mod 2^bit_width .
So aren't rings even more important in programming than monoids?
My answer would be that neither really is.
You're confusing a few examples of important things happening to be X, with the concept of X being an important concept.
When people use ordered lists, they are not thinking of them as monoids, or using any interesting theorems from monoid theory.
If mathematicians had never come up with the definition of monoids, C and C++ would have been designed in exactly the same way as they are now.
In French, the situation is even worse: number theory is also called “arithmetic”. According to legend, sometimes innumerate peasants wanting to learn how to do basic sums would pick up a book called “arithmetic” in a bookstore that turned out to be a dense theoretical monograph on number theory.
Maybe that's going to be added later, but so far I'm not seeing any practical benefit.
I got this same impression while delving into type theory [0], but even moreso with category theory. It seems the chaos of the information explosion is being organized and how we presently do software and data may go the way of the dinosaur "overnight".
EDIT: For example, my MSc was on the topic of a category equipped with a functor into it. This allows one to construct (parts of, e.g. I haven't done subobject classifiers) a self dual set theory.
One way I'm thinking is to extract "patterns" automatically from their code. Then, it enables to write code review, give advises, pointers, find pattern duplication, common ground vocabulary... I'm sure structuring automatically the code from CT point of view can be helpful.
Disclaimer: Few years ago, I felt in love with theory category and more precisely the sketches (from Ehresmann). I linked Machine Learning and Category Theory [1] by automatically mapping data structure and algorithm definitions together (input/output and operations between) in order to be able to run any algorithm on any set of data. Then I introduced an heuristic based on Kolmogorov complexity to find the best model (algorithm output) to summarize the input data. Loved it !
[1] https://link.springer.com/content/pdf/10.1007/978-3-540-7497...
For example, reading category theory introductions meant for programmers to me is confusing, even though I know the mathematics already! I still need to get around to Milewski's book which looks to be dually useful as "functional programming for category theorists".
Just wondering since most of the examples are in C#, why no Monads? It seems it's pretty straightforward to express the idea in LinQ expressions.
SelectMany is similar to a monadic bind, with an extra selector parameter in its signature, you can achieve the following expression:
from one in Maybe.Of(1)
from two in MaybeAddOne(one)
Select two
Another thing is async/await is pretty much similar to LinQ expressions, but it's hardcoded with the type Task.
Here's a way of doing ad-hoc polymorphism to implement a more general monad in C#. It's limited in that the return type for Bind can be any monad (although it still type checks). There are a few other issues (not least it's ugly as hell). But, it does allow for building of very general monadic operations (along with other ad-hoc polymorphic types).
// Typeclass (ish)
public interface Monad<MA, A>
{
MA Return(A x);
MA Fail(object error = null);
MB Bind<MonadB, MB, B>(MA ma, Func<A, MB> f)
where MonadB : struct, Monad<MB, B>;
}
// Class instance of Monad for Option
public struct MOption<A> : Monad<Option<A>, A>
{
public MB Bind<MonadB, MB, B>(Option<A> ma, Func<A, MB> f)
where MonadB : struct, Monad<MB, B> =>
ma is Some<A> x
? f(x.Value)
: default(MonadB).Fail();
public Option<A> Return(A x) =>
new Some<A>(x);
public Option<A> Fail(object error = null) =>
new None<A>();
}
// Option 'discriminated union'
public interface Option<A>
{
}
public class Some<A> : Option<A>
{
public readonly A Value;
public Some(A value) => Value = value;
}
public class None<A> : Option<A>
{
public None() { }
}
// Testing adding any two M<int> types together. Doesn't need to just work with
// ints, it's just a simple example.
public class Test
{
public void Test1()
{
// Some 200
var r1 = AddAnyMonads<MOption<int>, Option<int>>(new Some<int>(100), new Some<int>(100));
// None
var r2 = AddAnyMonads<MOption<int>, Option<int>>(new Some<int>(100), new None<int>());
}
public MInt AddAnyMonads<MonadInt, MInt>(MInt ma, MInt mb)
where MonadInt : struct, Monad<MInt, int> =>
default(MonadInt).Bind<MonadInt, MInt, int>(ma, x =>
default(MonadInt).Bind<MonadInt, MInt, int>(mb, y =>
default(MonadInt).Return(x + y)));
}
[1] https://github.com/louthy/language-ext/blob/master/LanguageE...
Arr<A>, Lst<A>, Seq<A>, Set<A>, HashSet<A>, Que<A>, Stck<A>, Option<A>, OptionAsync<A>, Either<A>, EitherAsync<A>, Try<A>, TryAsync<A>, TryOption<A>, TryOptionAsync<A>, Reader<Env, A>, Resource<A>, Writer<MonoidW, W, T>, State<S, A>, Task<T> (extensions), Nullable<T> (extensions), Validation<Fail, Success>, Validation<MonoidFail, Fail, Success> + Monad transformer stack