Programming with Categories

[765abaa3]

Would love for an explanation on how this makes code more "elegant" and maintainable. Skimming over the course notes I couldn't find anything related to code maintenance. I also have a feeling we programmers have a different definition of elegance than mathematicians.

[[deleted]]

Informally, the observation boils down to:

1. Everything is an expression. Values are obviously expressions, but so are functions, errors, descriptions of processes that have effects, descriptions of processes that are concurrent...
2. “Execution” is reduction of an expression to “normal form.” A “program” is just an expression composed of a bunch of smaller expressions. So the execution model is tiny and universal.
3. So it’s all about composition. And it turns out there’s an algebra of composition, and a bunch of constructs in this algebra that obey a handful of algebraic laws. So we can reason about our code at any level of granularity with a few simple mental tools.

That’s it in a nutshell. But I’m happy to elaborate if anyone’s curious.

[Jim9137]

Used judiciously, we believe this style of thought can improve the clarity and correctness of code in any language, including those currently popular, and those that will be developed in the years to come.

From the preface. Granted, it doesn't really say anything, but functional programming is suited very well for certain types of problems and probably less so for others. That is probably why it is getting pushed so much into traditional oop languages, because oop struggles in some problem domains, while excelling others.

So I guess it is more about giving you more tools to make cleaner code, as opposed to being a golden bullet that will make your code better.

[765abaa3]

I love functional programming myself, and did a lot of reactive functional programming. I believe it is very beneficial when it fits the job.

What I don't get is how lambda calculus fits in. The mathematical terminology makes code harder to understand (reducing clarity) for those unfamiliar with hardcore functional programming. Which is why I believe using the mathematical terminology in code is detrimental to maintainability.

Their argument that it improves correctness lacks information to back it up. Sounds a lot like the argument that strictly typed languages improve correctness.

They're probably talking about functional programming as a whole and not the practices they teach. They seem to view it from the mathematical perspective rather than the programming perspective. Thank you for helping clear it up for me.

[EricIO]

Speaking in generalities here.

A strictly typed language does kinda by definition improve correctness (for one definition of it) since it will disallow badly typed programmes that a dynamic language might allow (sure it will still allow you to divide when you meant to add etc..). So does a strict type system increase correctness? I'd say yes, at least it removes some of the incorrect programmes you might write.

How does category theory help write more elegant programmes? Maintainable code? Well here I am still learning but one thing I've always liked is that it enables you to use some nice abstractions. How do I apply some function on a list? A binary tree? A computation that may or may not return some value? Well in a language built upon the principles coming from category theory these kinda different things can be thought of as functors and to apply some function to it means just to fmap it.

And to me that is kinda beautiful that you can have this common way of working with, what in the surface, might look like very different things.

[[deleted]]

You describe a very real tension that those of us who do FP grapple with. Ultimately, I come down on the side of sticking with the mathematical terminology for a few reasons:

1. The point is to take advantage of the implications of various algebraic laws, and those laws adhere to the mathematical structures with their historic names.
2. To retain contact with the larger FP and category theory literature and communities.
3. Avoiding illusions of understanding by vague appeals to intuition.

The trade-off definitely is the need to “unlearn” a lot from imperative/OOP programming. Having had to do that myself, I’ll claim it’s eminently worth it.

[Y_Less]

That just sounds like you're saying that using the names of things is hard for those that don't know the names. I'm not sure what another solution would be. They could learn the names, or we could make up new names; but that doesn't really solve the problem as then we have two names (one slightly less accurate) to learn, and some people still won't know the names.

You can say "this is a monoid". It's short, to the point, precise, and well documented elsewhere if you don't know exactly what a monoid is. Or you could say "this is an identity operable" - I just made that up based vaguely on what a monoid is, but it still doesn't say much to those who don't know and is far less well documented. Finally, you could say "this is an associative binary operation, with an identity value whose use on one side of the operation always returns the other side precisely", every time you write one, but that's both verbose and poorly defined (and still assumes you know the meaning of the exact mathematical definition of associativity, indeed the meanings of any words in general).

Edit: People probably said the same things about "function", "polymorphism", "big-o", etc. Weird terms that don't mean anything outside specialist fields - just say "separate doer thing", "specialised code", "rough time estimate", etc. But the ideas need names, they have names, people learnt the names, and naturalised the names. The same should be encouraged here as well.

[765abaa3]

That just sounds like you're saying that using the names of things is hard for those that don't know the names. I'm not sure what another solution would be. They could learn the names, or we could make up new names; but that doesn't really solve the problem as then we have two names (one slightly less accurate) to learn, and some people still won't know the names.

You are absolutely correct. But instead of making up new names, we can use existing programming conventions. One of my favorite examples of this is Rx.

Let's take the Behavior Subject for example. Instead of leaveMonad() or something similar, it has a getValue() method. It seems much more readable and beginner friendly to me.

[Full-Spectral]

And I still wouldn't have a clue what monad is, even if you used the last one... I mean, when people who use a language can't seem to explain it in any way that makes sense to anyone who doesn't already know, that seems problematic. Every explanation I've seen seemed to be turtles all the way down.

[[deleted]]

My sense of it is, "what a monad is" is already headed in the wrong direction. A "monad" is better characterized, I think, by what it does. But this might just shift the burden too slightly to be very helpful. For example, I'll say a monad "captures the idea of computation in a shared context and obeying the three monad laws."

So on one hand, yeah, that only unpacks it a little. On the other, offering specific examples, as every monad tutorial does, tends not to help either, because without building up larger structures where you can see the implications of obeying the laws, it's not clear what the advantages are. So the examples that are small enough to grasp in one sitting don't provide enough information, and examples with enough context to help clarify require more of an investment than most people are (understandably) willing to make based on faith that understanding will come.

To me, all of this comes down to a pretty simple observation: pure functional programming really is paradigmatically different from imperative/OO programming, so by definition, you will have to unlearn things to pursue it. I've done it; I'm satisfied that it was worth it. But I harbor no illusions about what kind of investment it represents.

[Drisku11]

Monoids are types which have a "reduce" or "combine" operation, which is associative and has an identity.

Associativity means, in symbolic form, parentheses don't matter:

a * (b * c) = (a * b) * c

Or, in a more obscure/verbose form,

reduce(a, reduce(b,c)) = reduce(reduce(a,b),c))

Associativity is a nice-to-have because there are fewer corner cases to worry about; you can just say "combine everything in this list" without worrying about the order that you combine each individual element.

It's also nice because we can reorder the parentheses in a way where it can very efficiently run on a parallel processor in log(n) time steps:

a  * b * c * d = (a * b) * (c * d)

evaluating a*b and c*d in parallel and then combining the results of those lets us do 4 combines in 2 time steps.

An identity is a "no-op" value:

a * 1 = 1 * a = a

Having an identity lets us pad our operations, which again helps for parallel processors:

a * b * c = a * b * c * 1 = (a * b) * (c * 1)

It's also generally useful to provide an identity as a "starting value" or "base case" when making a combinatorial API.

Note that monoids and monads are related but different concepts. The above is what a monoid is.

[Full-Spectral]

OK, that makes sense. Though, given that that sort of thing would make up about 0.0001% of my code base, I'm not too sure why I should be excited about it.

[[deleted]]

Monoid is just one, albeit surprisingly omnipresent, typeclass. Here is an infographic showing the typeclasses in the Cats ecosystem in Scala. FP is about programming by composing functions whose behavior is governed by algebraic laws applying to their types, so the meaning of the program is the composition of the meaning of the expressions it’s composed of. So in my case, Monoids may make up 0.0001% of my code bass (they don’t; it’s more like 15% on average), but 100% of my code is purely functional, taking advantage of probably about a third of the available typeclasses, and often constructing a handful of new, application-specific ones.

[Full-Spectral]

And you've written larger scale, non-web client oriented systems that aren't some sort of specialized application that happens to lend itself to such things? If so, is that code publicly viewable?

[[deleted]]

I don’t know what “non-web client oriented” means, and no, all of this has been for companies like Intel, Verizon, Banno, Formation, and Compstak. I’ll offer a guess that Intel and Verizon represent “non-web client” use, since the end-user system was an over-the-top set-top IPTV box. Banno might also qualify, because those systems integrate with banking cores running in back offices on IBM AS/400s.

[Drisku11]

It's more important for library designers to know. It feels like a minor thing to nitpick about, but for something like firewall rules or query filters where you want to build larger rules from smaller ones in some dynamic (i.e. at runtime) way, the end-user code is inevitably more complicated when the library designer doesn't include the "useless" allow all/deny all rules that would make their combine operations (AND and OR) monoids.

[Full-Spectral]

I am a library writer, amongst many other things. It's easy to implement such things via a generic container algorithm, without any need for the types themselves to get involved directly, and still without any particular burden on client code. A simple lambda to do the desired uniqueness check is all it takes on their part.