What Monoids teach us about software
deque.blog
deque.blog
Conceptually, a monoid is anything that:
- Has a "zero-value" (mempty, e.g., 0)
- Can be "appended" together (mappend, e.g., +)
- Has an identity with the zero-value: x + 0 == x, 0 + x == x
- Is associative: x + y + z == (x + y) + z == x + (y + z)
This isn't limited to just arithmetic with operators like +. You can define whole new types as monoids if they have these characteristics. For example, we can merge together configuration files by using monoid operators (in pseudo-code):
-- Zero Value
mempty == {}
-- Append
{"color": "Blue"} `mappend` {"fontSize": 12} == {"color": "Blue", "fontSize": 12}
-- Identity
{"color": "Blue"} `mappend` {} == {"color": "Blue"}
{} `mappend` {"fontSize": 12} == {"fontSize": 12}
-- Associativity
{} `mappend` {"a": "b"} `mappend` {"c": "d"}
== ({} `mappend` {"a": "b"}) `mappend` {"c": "d"}
== {} `mappend` ({"a": "b"} `mappend` {"c": "d"})
Borrowing from mathematics is beneficial because we can work with structures that have simple but useful guarantees. In Haskell, you can expect all the above to be true for correct type instances of Monoid, without the implementation details at hand. It's a core tenet of functional programming to disarm complexity with simplicity.
> A Monoid can be defined a tuple (M, op, e)
This definition lost me completely because I'm not even sure what "defining it as a tuple" is meant to imply. Based on your explanation it sounds like that is fancy talk for saying it is defined by having three properties.
> In a statically typed language, we can translate the notion of set into the notion of type.
The second definition again completely lost me because I'm not even sure what "set" and "type" mean in this context and being able to "translate the notion of set" is unhelpful when the definition using a set is the one I didn't understand in the first place.
I'm a programmer with over a decade of professional experience. I don't understand the article because I have no formal education in higher math nor in anything beyond basic computer science. Your explanation proves it's possible to explain these concepts with practical examples rather than academic jargon.
Defining stuff as tuples makes sense, because then you can define the set of all such tuples (e.g. the set of all monoids for a given set M or the set of all graphs for the given vertices V) and formally reason about it :)
Yeah, in a computer science situation it's needlessly obfuscatory. It's literally just an interface with a "plus" method and an identity value.
You learn both languages. You do it because the vast majority of human invention and ingenuity consists if acts of translation. Anyone serious about working with computers should understand that.
I'm not arguing the underlying math isn't beautiful. I took grad level algebra and logic classes, so believe me when I say I know the math is awesome. But it just doesn't have any practical utility in programming, and more often than not just makes things more confusing.
edit: Also, since I majored in math, with a focus on logic, I don't think I'll have any trouble with losing sight of the foundations :)
But I'm a professional, not a CS student. I'm already spending my free time honing my craft and looking into new techniques and developments in software engineering. I can't afford spending yet more time on mostly orthogonal higher mathematics based on the hearsay of some guy on the Internet arguing it will allow me to understand a point somewhere down the line that might make me a better developer.
This is exactly the same thing people say who come to programming from playing jazz music or artistic painting or figure skating. They all claim what they did before makes them a better programmer and they're probably even right. But that doesn't mean I should pick up figure skating as a hobby at this point.
There are many different fields related to software development that can directly improve your performance as a developer. Not all of them are equally to all tasks a software developer might have to perform. I think it helps to have a mix of them, especially at the level of teams. There are times where the UX zealot can save the day and there are times where it's the one with the Master's degree in Metamathemagics. I wouldn't want to miss either of them, even they're mostly oblivious to each other's specialisation.
"I get paid, I don't learn."
You want to get paid, get paid. I won't care if you fail.
I suppose Alan Turing and Charles Babbage are just shit programmers next to you.
Eventually I figured out it is a generalisation of "couple", "triple", "quadruple", etc. It's one of those things, but we don't want to say the number.
(I just tried googling it, and the definitions I get are very maths-y and hard to understand)
Vector spaces have addition over vectors and multiplication of vectors by scalars. Considering vector spaces and addition only, that is a monoid. It also happens to be further along this hierarchy as you have commutativity, inverses, and other properties.
A bit like the statement: all squares are rectangles, not all rectangles are squares. We can say that all vector spaces are monoids (under addition), but not all monoids are vector spaces.
In the case of configurations, "right bias" (aka Last) is probably a good choice. I don't like that Haskell chose it for the general Map instance.
reducers has a UnionWith newtype which gives you the better Map monoid. But I think it uses a lazy unionWith, which will cause your Map to leak space when used in a foldMap over many elements :(
[1] https://www.youtube.com/watch?v=WsA7GtUQeB8 [2] http://notes.asaleh.net/posts/monoid-pattern-in-python/ [3] http://notes.asaleh.net/posts/monoid-for-specifying-configur...
So all you need to do is to create the null object and the add and sub function on the type? And I can use an implementation of that type as the state for something?
How can I guarantee the order? Would I need to use something like a blockchain or is a distributed database enough, as long as only I need the data and trust myself? In a cluster would it make sense to use etcd
I think, even better would be a commutative monoid, that doesn't depend on the order. It should be possible to scale the global state in a distributed system very concurrent, because of the commutativity.
I would have to store a log (easiest part) and the current state. To sync state between the nodes in a distributed system, they would have to send update messages to each other. They're able to batch process multiple messages to improve throughput.
Had the shapes example be modified to describe (say) a topological space via open sets, you may have a point.
http://repository.upenn.edu/cgi/viewcontent.cgi?article=1773...
"Abstract algebra is too simple to bother writing programming blogs about!"
It's just generally quite amusing to be caught in the middle of all this.
No, that's a strategy to achieve a goal of programming. Programming is about using machines that accept well defined instructions to automate processes for people. A complex and poorly understood program that still ends up reducing the overall amount of work required for individuals is still worthwhile, even if not reduced to being boringly simple.
It's sort of like saying the goal of owning a store is to match inventory to sales as closely as possible. That's a strategy or sub-goal towards reaching the real goal at best, which is to make enough money that the store pays for itself and hopefully supports the owner. Some stores don't even have inventory, so that strategy doesn't even apply to them. Similarly, that programming strategy may not apply well to some problems (and some problems cannot be proven formally correct, at least in whole).
My original reply was really just meant to point out that what they viewed as the goal of programming, is really just one of many competing strategies for producing software, and many others don't care about that at all.
That's irrelevant, because we are not naming them to use them in abstract algebra, but as abstract constructs in a different domain with its own complexity (programming).
You'd be surprised. A pointer (as in C) is an even simpler notion, but the complexity it represents to new programmers is big.
Complexity in a programming element from the interplay it has with everything else -- not from it isolated.
* Under my Foo API you are able to combine Bars monoidally
* Under my Foo API you are able to combine Bars using baz such that `baz (baz bar1 bar2) bar3 == baz bar1 (baz bar2 bar3)` for all `bar1, bar2, bar3 :: Bar`, and also `baz == Bar quux baz == Bar baz quux` for all `baz :: Bar`.
But seriously, the use of Bar/Baz etc. in this example makes it more convoluted, rather than less, precisely because the names offer no hint for how to understand the nature of each thingy.
No. Firstly, Bars may not be commutative. Secondly, would you really say that taking the unions of sets is "just like adding numbers"?
Every time `instance Monoid Foo` occurs in the Haddock documentation of a Haskell datatype which is pretty often!
> Does the frequency with which this occurs justify introducing new terminology?
"Justify" according to what set of criteria? Personally I prefer it.
> you artificially inflated the wording to make "x is associative and has a neutral element y" look more complicated than it actually is
So your suggestion is
* baz is associative and quux is a neutral element for it
Really, if you're going to go that far you may as well go all the way and just say
* Foo is a Monoid under baz and quux
> while not even naming in your "short" case what the operation and neutral element are.
Well, in the Haskell world they're implied by the typeclass instance, but I take your point.
It's incredibly useful, since you can just go into Hoogle or some similar tool and query a function that:
Monoid m => (a -> m) -> [a] -> m
1 - Well, the autodoc write those comments for you.
Associativity is a boring word, because high-schoolers have seen it.
Eh. Your patience here is admirable.
(Though normally the latter would be more like "`quux` is a noop", "`quux` is an empty set", or whatever domain-specific term you need, and the associativity claim would be a brief parenthetical inside meaningful documentation.)
I think jQuery satisfies monoids most of the time, and it worked and could be explained just fine without saying the word "monoidally" even once.
[1] From Jabberwocky, of course
"Under my Foo API, Bars are combined associatively".
Associativity is a word. It's also a word that is taught to people in high schools. So use that.
Also, the elements are still combined associatively. With closure and and identity properties, the set forms a monoid under this operation. "Monoidness" is not a property of operation (in a way that the language is usually used, at least in math).
For that matter, "combine monoidally" is a phrase that has 2 Google hits at the moment, which indicates to me that in real life, you still have to resort to less-shiny words to describe things.
There doesn't seems anything hugely objectionable to me in saying "Bars combine monoidally". But if you prefer, one can say "Bar forms a monoid under baz and quux".
It may not be obvious to you that it increases simplicity merely to combine two words into one but across an ecosystem of perhaps a thousand Monoid instances it indeed is.
The argument as I see it written is only that naming them reduces cognitive load. I don't see anyone suggesting that the specific name they happen to have carries any special power.
My original argument (in this thread above) is that identifying patterns like monoids (and monads) gives more power through better abstractions.
Not that it's simpler than not knowing those abstractions (obviously assembler which ditches all abstractions is as simple as it gets conceptually).
>What aspects of associative operations with a neutral element are so central to teaching programming that naming such a construct "monoid" gives us a stepping stone towards better understanding programming?
It's about unifying similar usage patterns and having a mechanism to treat things like optionals (Maybe), errors, IO etc in a uniform way.
As a simplified no-monady example, consider languages with a string distinction between primitives (ints, etc) and objects (like Java, at least before generics/auto-boxing). A language that comes and treats both of these things (primitives and objects) as the same -- all objects, is an eye opener, and allows for more kinds of expressions than a language that treats them as distinct kinds of variables does.
fold :: (Monoid m, Foldable t) => t m -> m
I actually did a count recently; something like 30% of our modules import Data.Monoid. Many of them were just using the (<>) operator, but that's useful in and of itself: no need to define a distinct operator for each of our types that wants one.
It's a simple, incredibly general abstraction that pulls its weight—partly because it doesn't have much to pull.
This is a judgment to be made on a case-by-case basis. For example, when writing programs, I don't think the word "monoid" is useful enough to be worth explaining, so I would avoid using it in API's or documentation and see if I can get the point across in some clearer way.
sum (map sum xs) == sum (concat xs)
Applying an operation to a total workload is identical to:
1) Split the total workload into smaller workloads.
2) Apply the operation to each smaller workload.
3) Apply the operation to the results from step 2.
Each smaller workload in step 2 can be run in parallel.
While that may seem obvious for adding numbers or money it may be less obvious when you have different operations for example a method in an OO class hierarchy.
The JVM can do similar optimizations because it knows the class hierarchy at runtime and therefore declares every method as final until it finds a class with a method that overrides the previous definition. It's also capable inlining dynamic dispatch by profiling the type of the object it's dispatching on. If 99% of all calls go to class X then it can inline the method of class X and catch the remaining 1% with a fallback clause. Of course this comes at a cost. You need to retain the bytecode, class metadata, profiling information and duplicated code that is generated from inlining in memory.
I've recently preferred to be reluctant about this and just tell them I really don't like these words (OOD / Design Patterns)... One interview was over really quick, while at another place, I've actually signed now. Any thoughts?
He also later wrote a foreword for a book by Richard P. Gabriel, "Patterns of Software", with this gem of a quote: (the book itself I really recommend for anyone interested in design patterns)
...
In my life as an architect, I find that the single thing which inhibits young professionals, new students most severely, is their acceptance of standards that are too low. If I ask a student whether her design is as good as Chartres, she often smiles tolerantly at me as if to say, “Of course not, that isn’t what I am trying to do. . . . I could never do that.”
Then, I express my disagreement, and tell her: “That standard must be our standard. If you are going to be a builder, no other standard is worthwhile. That is what I expect of myself in my own buildings, and it is what I expect of my students.” Gradually, I show the students that they have a right to ask this of themselves, and must ask this of themselves. Once that level of standard is in their minds, they will be able to figure out, for themselves, how to do better, how to make something that is as profound as that.
Two things emanate from this changed standard. First, the work becomes more fun. It is deeper, it never gets tiresome or boring, because one can never really attain this standard. One’s work becomes a lifelong work, and one keeps trying and trying. So it becomes very fulfilling, to live in the light of a goal like this. But secondly, it does change what people are trying to do. It takes away from them the everyday, lower-level aspiration that is purely technical in nature, (and which we have come to accept) and replaces it with something deep, which will make a real difference to all of us that inhabit the earth.
I would like, in the spirit of Richard Gabriel’s searching questions, to ask the same of the software people who read this book. But at once I run into a problem. For a programmer, what is a comparable goal? What is the Chartres of programming? What task is at a high enough level to inspire people writing programs, to reach for the stars? Can you write a computer program on the same level as Fermat’s last theorem? Can you write a program which has the enabling power of Dr. Johnson’s dictionary? Can you write a program which has the productive power of Watt’s steam engine? Can you write a program which overcomes the gulf between the technical culture of our civilization, and which inserts itself into our human life as deeply as Eliot’s poems of the wasteland or Virginia Woolf’s "The Waves"?
That being said, they are useful abstractions and in Haskell, for example, open up all of Control.Monad[0] and Data.Monoid[1] to your code for free.
[0]: https://hackage.haskell.org/package/base-4.10.0.0/docs/Contr...
[1]: https://hackage.haskell.org/package/base-4.10.0.0/docs/Data-...
That was has happening in the last 50+ years.
>and one can use all their power with no attention given to algebraic axioms that define a monoid.
Not really. When you can actually identify a pattern, and treat different instances of the same phenomenon as a single concept, you get much more power over simple using those individual instances as different cases.
It's the very reason why we create and use abstractions.
For example, an Army field manual [1]: "Any use of force generates a series of reactions."
Like, duh, right? But if you read on, the manual makes a highly cogent, precise point (one that's especially relevant to a military that all-too-recently used "body count" as a success metric).
"There will be times when an overwhelming effort is necessary to destroy or intimidate an opponent and reassure the populace. However, counterinsurgency forces should calculate carefully the type and amount of force to be applied and who wields it for any operation."
If you fail to generalize from tanks, rifles, missiles, etc. to "force", it's a lot harder to think about how to apply force to get the outcome that you want.
The same is true of programming. For small programs, you don't need abstractions or patterns. But if you want to build large, resilient, performant systems, you'll need formal definitions for those terms, and formal definitions of components you can use to build them, and so on.
Re-reading, it sounds like you're saying that the concept of a monoid isn't useful by itself, and I guess that's fair. But I didn't know anything about them before, and now that I read this article I do. I've got a long way to go!
While I haven't articulated this particularly well in my original comment, what I despair is the singular obsession with Monoids. It is popular because it is easy for people to wrap their minds around, they convince themselves that they've learned deep math and Something Very Important(tm), and it has a cool sounding name.
It's like you've given someone a book about the origins of the French Revolution and because they've heard the word "french", keep repeating "but the Eiffel Tower though amirite?" and keep writing blog posts and articles about the Eiffel Tower and nothing else.
In some ways I suppose my criticism is unfair and has an elitist / snobby vibe to it. It is common for people to find some 'sexy' hooks to initially get attracted to an area, and one shouldn't judge too much newbies. After all no one is forcing me to hang out at forums :)
That's not the case (though it might be for some).
The "singular obsession with Monoids"/monads is because we have a popular-ish language that has them as an abstraction. For many people that's a new abstraction they weren't aware of -- in the same way that in 2000 or so everybody talked about GoF Design Patterns.
If linear types where used in some other popular(ish) language and enabled new things and abstractions people would talk about that concept all the time (which is even simpler as a notion than monoids).
There's this whole discussion about "theorems for free" and why these formalisms are quite useful and relevant to languages like Haskell.
Any decent programming language will let you write code that uses an abstraction, limiting your interaction with some of its input values to only operations defined in the abstraction.
Then the question becomes "how interesting is this abstraction free of concrete details?" It turns out monoids allow you to write general code that gives you incredible flexibility when you later choose a concrete instance of the abstraction to work in. See http://www.soi.city.ac.uk/~ross/papers/FingerTree.html for an example of how you can specialize a general data structure to do a number of specific functions based on a choice of monoid.
The best abstractions are the ones that introduce a lot of flexibility based on choices that code doesn't depend on. A lot of the deepest abstractions in that sense come from math. This isn't an accident. Math is about searching for good abstractions. When one of them is found to be applicable to programming, that should be celebrated.
Don't mock the ones who are celebrating.
I don't at all get what the hype is about from this article, the concept of "you can combine two things and get a thing" isn't novel or radical.
I get a feeling that the kicker is about associativity, which is to say "when combining a bunch of things in a row, you can combine them any way as long as you only combine the adjacent ones". The kicker being that if you have that, you can parallelize.
So, seeing associativity allows one to identify parallelizable problems.
This is a much deeper debate, but through my subjective experience programming for two decades, stand-alone as PhD, and also leading a 200-person engineering team, I thing flexibility is by and large the last thing to optimize for, and almost always a sign of a novice engineer.
You don't know the future. You don't know what will work with the end users of your software, or where your research will take you. The best thing you can do is to accomplish the task in front of you in the simplest, most directly performant way possible, and put it to use - in front of customers, or in doing your research.
True flexibility is not having to wait for every iteration so engineers can program in every iteration of the future.
There is a huge cost you pay today for 'flexibility', most things advertised as such are not in fact flexible, and the trend in designing complex real world systems is in fact for each project to do exactly ONE thing and do it very well.
Btw you're assuming I've rejected algebra, and I've done so immediately. I have no objections to using abstract algebra or category theory in designing and thinking about programming languages, and none of my opinions are a jerk-reaction to anything.
sometimes 'paying' for flexibility has high ROI.
More concretely, "monoid" seems both too general and too specific to be useful. Things that commute and things that don't commute are lumped together as monoids, and that seems to be a much more useful distinction.
Consider the monoids described in the article. For concatenation and file paths, order is important. On the other hand, multiplication, addition, maps, sets, and the shape examples all commute, so the ordering a monoid gives you is irrelevant. How does it help to consider both concatenation and addition as monoids?
(I'm honestly trying to see the relevance of monoids.)
> 'Perhaps the purpose of categorical algebra is to show that which is trivial is trivially trivial.'
"This can be taken to mean that one thing category theory does is help make the softer bits seem utterly natural and obvious, so as to quickly get to the heart of the matter, isolating the hard nuggets, which one may then attack with abandon. This is an invaluable service category theory performs for mathematics; therefore, category theory is plain good pragmatics."
https://ncatlab.org/nlab/show/nPOV
I would say equally "This is an invaluable service category theory performs for programming; therefore, category theory is plain good pragmatics."
Have you heard of applicative functors and monads? These are part of an edifice of concepts that builds on monoids that we do indeed have in computer science.
To give another example. "Strength reduction" as a compiler optimization relies basically on the fact that the distributive laws apply to rings. Yet you won't find a mention of rings in compiler textbooks that explain the technique. It's unnecessary to convey the idea and confuses more than it explains, unless you're one of the few people who already are familiar with rings as algebraic structures.
I linked to a paper about composing monoids to build a graphics library. For me that particular paper was, years ago, one of the most interesting things I'd seen on how to structure programs.
Maybe this whole experiment with using algebraic concepts in programming is a dead end, and maybe it is even just a way for a bunch of nerds to feel smart. But it seems like a pretty valuable tradition to me.
There probably wouldn't be "computation expressions" in F# if it hadn't been for Moggi and the Haskell gang. Sure it's great that we can take these concepts and rebrand them to make them nice and cuddly (although "computation expression" is no paragon of simple english).
Blah blah blah. I'm kinda tired of the programming forum dialectics...
OK, great! And what did F# call monoids, profunctors, semigroups, free constructions, adjoints ... ? The fact is that there are a lot of concepts we use in computer science (maybe not your corner, but yes in computer science) that already have names and history in the mathematical world. If you can suggest better names that we can use in computer science then that's great! Please tell me. Otherwise it seems reasonable to stick with the existing names.
If this is interesting to you Dan Piponi goes into significantly more detail (http://blog.sigfpe.com/2009/01/haskell-monoids-and-their-use...).
http://repository.upenn.edu/cgi/viewcontent.cgi?article=1773...
For me it gets interesting when you compose monoids, and that article has several elegant examples.
Otherwise I think the monoid structure is not super interesting in itself, but it's a really useful building block when thinking of software "algebraically", which to me is the most interesting aspect of Haskell as a programming tradition.
As for commutativity, I'm not sure how to answer. The monoid notion is useful in both commutative and noncommutative settings. When composing monoids one might be commutative and others noncommutative (like, say, a tuple of int and list of strings, the int being a total size and the strings being file names).
https://blogs.ncl.ac.uk/andreymokhov/an-algebra-of-graphs/
Representing graphs is a bit of a problem in Haskell, due to the difficulty of creating/working with cyclical structures, and the previous solutions were not really convincing. So in some ways this might be seen as a problem immutable data purists created for themselves. (Not my opinion)
But, either way, the ability to reason about and derive algebraic models for some problem domain is worth pursuing in general. Mathematically structured software is a fast track to robust, reliable, verified solutions to problems. That's propaganda but there's a fair amount of support for it.
An idea that comes up in functional programming that has a similar algebraic quality to monoids etc. is the notion of a type which contains only one value (usually called "Unit") and a type which contains no values ("Bottom" or _|_). The latter is described as "uninhabited" and is used, among other things, to usefully describe the type of a function which never returns. https://en.wikipedia.org/wiki/Bottom_type
Unit represents a value which is like a point in a space which contains only one point. It gets used to send signals with no content. For example, in predecessors of Go, there's the pattern of sending on a "channel of unit" as a way to essentially indicate an event to the receiver. Obviously in that use case, a type with any distinguishable values would be superfluous.
struct Unit {};
class Bottom { private: Bottom(){} };
As far as the connection with monoids goes, Bottom is a subtype of all types in the same way that the empty element of a monoid is a "zero" of the elements of the monoid. I don't know if that helps, but the similarity is that the types form a lattice, and so do the elements of the monoid. AIUI lattices (in the mathematical sense) have top and bottom elements, and in between they look like a DAG...
A lack of experience using abstract concepts - the experience which can only be gained by learning much more of, let's say, abstract algebra, than just the definition of monoid - will inevitably lead to wasting one's time or, worse yet, to the finished product being an over-engineered monstrosity.
(It is unfortunate that monoids sound like monad's more complicated brother, when in fact it is exactly the opposite way around. Monoids are so simple that a common reaction once you actually get it is to go "Seriously? That's it?")
The other useful thing about monoids is that because of the associativity, they provide a useful, yet easy, way of breaking up a task for multiprocessing. If you can prove that your data type and the operations you desire to use on it are monoidal (and by "prove" I mean the informal sort of things programmers do all the time, not grabbing a proof system and going at it), then you have some really easy options, and it's really easy to write a system that very cleanly breaks up "the strategy of how I'm going to multiprocess this" from "what it is I want to multiprocess".
Because of this, it is likely that you're going to continue hearing more about these things over time, rather than less. Monoids are just about the simplest non-trivial example of such things, and the more sophisticated steps up (lattices, CRDTs [1]) are probably also things you're going to hear more about in the future.
Personally, I think in a lot of ways we are still have collectively done next to nothing as a community to address the multicore world we live in. Right now we're taking advantage of some things like Go's green threads or "asynchronous" programming to deal with the common case where we have some problem where a single core is adequate to solve it, but we need some complicated scheduling or we have huge numbers of these relatively small problems coming at us at once, but we still have made very little progress in doing complex tasks truly in parallel. It is very likely that those solutions are going to involve coming to understand these mathematical abstractions and why they are important. Monoid is going to be the first of them you'll encounter, because it is, as I said, probably the simplest non-trivial one. But on its own it won't get you all that far in general.
[1]: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...
As a result, I currently use languages with decent type systems - Rust, recently F# - but I've still never come across a reason to know that something is a monoid, and I don't regularly come across duplicated code, so I'm not exactly sure what problem knowing something is a monoid is supposed to solve in my domain.
The CRDTs linked by the parent are a great example. If you're working on an eventually consistent system, and you see a structure that doesn't form a monoid, it's most likely the case that there's going to be some sort of race condition. That isn't to say that any given monoid is going to solve the problem, but it can definitely help to pinpoint possible problems in otherwise complicated code.
It definitely doesn't come up in every discipline, but studying these structures has improved my engineering a ton. If design patterns are about class and object composition, then I'd argue that algebraic structures are the equivalent for function composition.
Full disclosure: I write mostly functional Erlang code for a living
The easy cases are already covered by things like OpenMP and the difficult problems also usually benefit from being written in a language that allows you to tweak your memory layout and allocation patterns manually.
I just wish that higher level languages would give me this freedom without sacrificing productiviy or safety. I'm not even asking for completely unreasonable things. At the bare minimum all I really need are off gc heap allocation (with reasonable safety via reference counting or whatever rust does), value types and a way to launch threads that bypass the garbage collector stop the world pause. It's just a checkbox of features and the latter is not that important because you already can sort of do that by calling into C and launching an OS thread. For some reason though nobody is checking those boxes.
I still stick to C++ and C but it gets old to spend hours fixing memory leaks and other possibly security related bugs from other developers.
I feel like I'm writing too much semi-offtopic things just because I have no other place to express them.
You can then make sure to expose the monoid interface for users of your Haskell libraries and they'll be happier because your values will cleanly fit with the rest of the ecosystem.
If you don't code Haskell then it's not like monoids are crucial learning for a successful career. Maybe you could approach them with some curiosity and find something interesting and useful about basic algebraic structures.
But probably all these monoid nerds are just puttin' you on...
I'd say no to your question. I've linked an article elsewhere in the thread that to me shows pretty clearly that monoid is a useful and generative concept.
On a more basic level, I personally really enjoy taking inspiration from math and logic into programming. You mentioned composing programs in a way that is safe and correct; I think the algebraic approach to programming is a really excellent and deeply fascinating way to approach that goal.
The extreme example of the same nature is the notion of "magma" that finds some use in algebra. Would you use this word to describe a function with two arguments (that have the same type)? There's nothing to be gained by doing this outside algebra.
I happen to find that view really fascinating and generative, but I don't blame others if they aren't interested.
I also wouldn't insert the monoid concept into a codebase that isn't Haskell or doesn't already have some alignment with algebra, because it would seem weird... and Haskell has features (typeclasses and purity) that make monoids really nice to use.
I also don't generally do language advocacy, and I have a great respect for the diversity of ways of thinking and learning. But I also wish people wouldn't dismiss concepts that other people find useful and good just because they don't immediately see the point.
[0] "haskell vs. ada vs. c++ vs awk vs ... an experiment in software prototyping productivity" - http://www.cs.yale.edu/publications/techreports/tr1049.pdf
Could be an interesting tutorial to see a raytracer explained in terms of monoids.
https://clojuredocs.org/clojure.core.reducers/monoid & https://github.com/clojure/clojure/blob/f572a60262852af68cdb...
For the idea, I think https://en.wikibooks.org/wiki/Haskell/Monoids is better than this post.
so basically, for the cost of implementing two operations you can reuse dijkstra or bellman-ford to do crazy stuff like belief propagation etc
http://www.morganclaypool.com/doi/abs/10.2200/S00245ED1V01Y2...
I find that most of these fp examples tend to focus on simple things like shapes which tend to already have monoid properties built in. I'd be interested in seeing examples of how they help your kind of run of the mill business coding.
I've just stumbled upon an article that describes this:
http://blog.plasmaconduit.com/the-composite-pattern-and-mono...
The concepts are actually very simple but their effects are complex. This is great introduction though I think a little high level for beginners.
I can't tell why monoids are supposed to be more directly applicable to programming than any other concept from algebra.
[Edit] On the other hand, it is important to realize that even though these structures look (and indeed are) related, each focuses on a completely different aspect of reality. Monoids are useful in describing composability (where associativity is essential); groups are instrumental in analyzing all kinds of symmetries; vector spaces form a scene on which one deals with linear independence, subspaces, and linear transformations. (All this finds its application in computational algorithms, but it would be interesting to see if the program structure also could be understood using the notion of symmetry and/or linearity.)
> Why not groups?
Because many things you would want to combine don't have inverses. Does the list [1,2,3] have an inverse? No. That's why lists form a monoid and not a group.
> Why not vector spaces?
Because all finite dimensional real vector spaces are isomorphic to R^n so we tend just to use the concrete instances of tuples of floating point numbers.
There is nothing you can comcatenate to a list to get the empty list, nothing you can OR with True to get False, and nothing you can union with a set to get the empty set.
But yes, a good grounding in algebra will help anyway. It’s not an exclusive set ;)
Semirings are interesting for the same reason. "Fun with Semirings"[1] has some great examples, if you're curious.
[1]: https://pdfs.semanticscholar.org/702d/348c32133997e992db362a...
http://sarabander.github.io/sicp/html/2_002e2.xhtml#g_t2_002...
I think the authors of SICP didn't describe the picture language as such because it just isn't a very useful concept, not because they didn't know the word.
This has been gutted out of the group so that the category theorists can then see monoids in situations where they would otherwise have to rack their brains to come up with the inverse operation.
https://en.wikipedia.org/wiki/Group_(mathematics)#Definition
For instance, the set of character strings and the catenate operation are almost a group. The identity element is the empty string.
Closure holds: if a and b are strings, (cat a b) is a string.
Associativity holds : (cat a (cat b c)) is (cat (cat a b) c). (Which is then just (cat a b c) to a Lisp programmer, (cat a) is a, and (cat) produces the empty string.)
Identity element: empty string. (cat a "") -> a
Inverse element: oops!
We would have to postulate some sort of "negative string" so that (cat "abc" -"abc") produces "".
Then we have the problem of what is (cat "abc" -"xyz"): the combination of a string and the inverse element of a different string.
Let's not bother; just drop this axiom and call it a "monoid".
You don't understand every single instance. You understand the concept, and then you begin to learn individual instances.
The shape and the use of monoids is really easy to grasp. Sometimes understanding how a thing is specifically is a monoid or how it's implemented can be obscure. They are similar to monads in this respect, although often less complicated.
In summary, understand that there is a beach and that the beach is made of many grains of sand. Each grain of sand may not be obvious from just staring at the beach.
Common examples are: strings which you're allowed to combine with concatenation (with the empty string being the "neutral" element). Integers with addition as the combiner is also a monoid that also has a few additional named properties (like commutativity and existence of inverses) but they're still monoids.
The concepts aren't tough, people are just pretty bad at putting themselves in the shoes of a learner, and throw bizarre over-complicated descriptions and examples into the mix when explaining them. The description I gave is someone's tongue-in-cheek stab at these which has stuck with me (unless I'm horrendously off and that is actually someone's legit attempt to describe monads)
You have another value of the same type.
If there exist a function (let's call it "combine") that combines those two values and emits a third value of the same type.
AND
There exists a value of this type that does nothing when used as argument to this "combine" function.
then your type is a monoid. (basically)
A monoid is just an operation you perform on things that are similar. The concat() function in JS is a monoid.
> Relative paths in a file system form a Monoid under appending
How can appending be associative?
associative: (a + b) + c = a + (b + c)
commutative: a + b = b + a
For example, appending strings is associative, but not commutative. Appending items to an unordered set is both associative and commutative.
missed a word: Able to tell.
I took a look at docs and found the function definition for a post request.
https://hackage.haskell.org/package/wreq-0.5.1.0/docs/Networ...
post :: Postable a => String -> a -> IO (Response ByteString)
The examples mention using a JSON value as a parameter
>>> r <- post "http://httpbin.org/post" (toJSON [1,2,3])
https://hackage.haskell.org/package/aeson-1.2.1.0/docs/Data-...
Just seeing a single example isn't enough for me to generalise though.
I proceed to go to the definition of the Postable typeclass.
https://hackage.haskell.org/package/wreq-0.5.1.0/docs/Networ...
Unfortunately it doesn't list the instances of the typeclass so I decide to use hoogle.
https://www.haskell.org/hoogle/?hoogle=Postable
No results found.
I then start looking at the source code of the library until I found this file which contains the Postable instance for json values.
https://hackage.haskell.org/package/wreq-0.5.1.0/docs/src/Ne...
import Data.Aeson (Value, encode)
instance Postable Value where
postPayload = putPayload
I don't care about category theory at all and you can have all the practical benefits of category theory without putting it on a pedestial. It's neat to write more generic functions and stuff but there is no need to glorify it.
From a practical standpoint monoid, monad and functor you can think of them as an interface. When your code accepts a specific implementation like ArrayList you can in some cases instead use the java interface List to make your code more generic. When your code accepts a specific implementation like Maybe or List then sometimes you can use the Monad typeclass to make your code more generic.
λ> :i Monoid
class Monoid a where
mempty :: a
mappend :: a -> a -> a
mconcat :: [a] -> a
{-# MINIMAL mempty, mappend #-}
-- Defined in ‘GHC.Base’
instance [safe] (Monoid a, Monoid b) => Monoid (a :<|> b)
-- Defined in ‘Servant.API.Alternative’
instance [safe] Applicative f => Monoid (Traversed a f)
-- Defined in ‘Control.Lens.Internal.Fold’
instance [safe] Monad m => Monoid (Sequenced a m)
-- Defined in ‘Control.Lens.Internal.Fold’
... etc ...Agreed. Here's part of a recent email correspondence between me and a fairly prominent functional programmer who's written at least one celebrated paper:
> > I didn't want anyone to get the impression that they had to understand "category theory" or "maths" in order to use Haskell. This is a misconception about Haskell that is sadly far too prevalent in my opinion.
> I agree.
That being said, I haven't seen anyone in this discussion glorifying category theory, unless I missed something?
imtringued has raised an important point here. His/her comment is quite long but the summary is:
Postable is exported here
https://hackage.haskell.org/package/wreq-0.5.1.0/docs/Networ...
but defined in some internal module. Its instances are technically orphans because they are defined directly in the module that Postable is reexported from. That means that the documentation for them is detached from the documentation for the class.
https://hackage.haskell.org/package/wreq-0.5.1.0/docs/Networ...
This is confusing and Haddock should be improved to address this.