Sorry I need to rant, that's just a too terrible article.
It makes no sense at all to try to explain that stuff in a language lacking higher kinded types. All you can do there (without awkward encodings) is creating instances of those abstractions. You can't create the abstraction as such!
A quite straight-forward explanation of the "monoid in the category of endofunctors" thing can be found here:
Even the linked explanation is a "quite 'simple' one for that topic" it's still way more involved than what was shown in the article we're discussing here. That Scala stuff is actually correct, this one here isn't even close.
Sorry for the quite negative comment but imho there isn't anything else to add. Before writing a blog post about something one should get at least some basics. Things like: I need HKTs to express functors and such…
As I didn't see the given link here I think my comment makes a useful contribution even it doesn't bring anything else to the table; besides some rage about "very wrongly explained math". :-)
This article is playing fast and loose and I think gives a false understanding of what functors and monads are.
In particular there is an unwarranted leap here. If `numToStr` is a functor, then `addOne` (the function that just adds one to an integer) should be an endofunctor. So what's the monad?
Yet all of a sudden the article jumps to talking about `Array` as an endofunctor! Which is most definitely not a function like `numToStr` or `addOne`.
So which is it?
In particular,
> Of course, as we saw above, Arrays support a map method which allow us to transform the values of the array but do so in a way that returns an Array (the same type as the starting type), making them endofunctors.
Makes no sense combined with `numToStr`. What exactly is the `map` function for `numToStr`?
It turns out you can unify both of these notions, but you need the language of category theory to do it. But that's overkill for FP. So generally in FP a functor is just a type constructor (a type that takes another type as an argument e.g. `List<A>` or `Option<A>` or `Future<A>`) with an associated `map` function that obeys the "law" that `map`ing the identity function does nothing.
The full category theory definition requires a bit more exposition than just thinking of things as sets and functions. In particular you need to talk about two levels of mappings: mappings between categories, which are functors, and mappings between functors themselves, which are natural transformations. A monad is then a functor from a category to itself with two associated natural transformations. If the functor and natural transformations are taken as objects and arrows/morphisms in a category itself, then it forms a monoid. This is why we can also think of a monad as a monoid.
This sort of "category-stacking" where mappings between categories are treated as categories themselves where we can then further discuss another level of mapping between them, is the core of category theory.
> This sort of "category-stacking" where mappings between categories are treated as categories themselves where we can then further discuss another level of mapping between them, is the core of category theory.
I've started to call it "fractal math". Not to be interpreted as the mathematics of fractals, but rather as mathematics which is itself structured as a fractal (metaphorically speaking, of course).
Array is a monad. Then what's the function that takes an array and returns another? Is it map? That can't be because map takes two parameters, not one: the array and a function that it will apply to every element. Something is missing in the explanation.
And why is Option a monad? What's the associative function that takes two options and returns another Option?
Practically, the additional function that monads support is usually called bind and looks like: Array a -> (a -> Array b) -> Array b
This is different from map which is: Array a -> (a -> b) -> Array b
Notice how in map, your function returns a value that isn't lifted in the monad. The bottom one is a functor, the top one is a monad. Functors let you visit an array at every element. Monads let you visit an array and produce a new array each time and they internally decide how they will recombine those values.
This is a bit silly for Array, you just concatenate the outputs. But is more interesting for Option.
map for Option looks like: Option a -> (a -> b) -> Option b
It says "If there's anything in my Option, apply this function to it, otherwise there's still nothing there"
bind for Option looks like: Option a -> (a -> Option b) -> Option b
It says "If there's anything in my Option, run this computation. This computation can also return an option". In this sense, it lets you string together computations that each produce optional values. The whole computation will fail if any part fails. Something that is very useful!
This post is very wrong. Being a monoid in the category of endofunctors means something very different from being a monoid in the normal sense (they're related in a category-theoretic way, but the similarity is at a very abstract level). Simple sequences have a lot of structure which mean they are a lot of different things; it is true that sequences are all of monads, functors, and monoids, but the latter structure is unrelated to the former.
Contrary to this post, merely being a functor and a monoid does not make something a monad; for example any arbitrary monoid (say, the integers) could be considered an applicative via Const, but is not a monad. Or many other applicative-but-not-monads have monoidal structure, e.g. ZipList.
Things could be headed off early where the blog defines a monoid. The definition given is roughly what the average mathematician would call a monoid, but a category theorist would complain saying that it only defines a monoid in the category of sets.
But monads are not monoids in the category of sets. They are monoids in the category of endofunctors! So the blog post is going off the rails from here on.
> means something very different from being a monoid in the normal sense
Yet you didn't say how exactly different. I understand I probably need to know category theory for that, yet nevertheless OP's post was useful, fulfilled some curiosity, but your comment didn't, besides leaving feeling "it's complex", sorry.
I'd really appreciate if someone one day wrote as clear explanation of monads as OP's, but at the same time staying correct.
I can't explain the "a monad is just a monoid in the category of endofunctors" thing simply; I barely understand it myself, and I'm actually sceptical that it's even true at all. I certainly don't think it's a useful way of learning anything.
If you're asking about monads in general, I think trying to understand the generic concept before understanding a bunch of concrete examples is the problem. https://m50d.github.io/2013/01/16/generic-contexts was my effort at explaining applicative functors (which are not quite monads, but monads are a fairly small extension of them) "from the bottom up", starting with some useful concrete things that happen to be applicative functors, and discovering that abstraction.
Let me give it a shot. Monads as in category theory are a bit more abstract than this explanation, but for the purposes of programming you can think like this:
A functor has a `map` mechanism, which takes a value A and a function B, and returns something that has the same type as A. A simplistic example of a "mappable" that isn't a functor is `const map = setTimeout`: it technically take a value A (the time) and a function B, but `map(fn1, map(fn2, 1))` is semantically nonsensical even though all the types technically align and the code runs (because the effective "type" of the return value does not use milliseconds as a unit of measurement, and effectively causes undefined behavior).
A monad, in addition to being a functor, must also not have extra funky semantics. A example of a functor that isn't a monad is `Promise`. Imagine we did this:
TimeSequence = Promise
TimeSequence.of = TimeSequence.resolve
TimeSequence.prototype.map = TimeSequence.prototype.then
t1 = TimeSequence.of(1) // t1 has type TimeSequence<number>
t2 = t1.map(v => v * 2) // t2 has type TimeSequence<number>
// BUT
t3 = t2.map(v => TimeSequence.of(v)) // t3 has type TimeSequence<number>, NOT TimeSequence<TimeSequence<number>>
The Array equivalent is:
SpaceSequence = Array
a1 = Array.of(1) // a1 has type SpaceSequence<number>
a2 = a1.map(v => v * 2) // a2 has type SpaceSequence<number>
a3 = a2.map(v => Array.of(v)) // a3 has type SpaceSequence<SpaceSequence<number>>
a4 = a3.flat() // this is a separate operation to get a SpaceSequence<number> out of a3
Here, Array is "monadic" because it has both map and flatMap as separate operations. Promise conflates the two, hence it's not monadic.
(Note: I say Array is "monadic" in quotes, because this is only true if we constrain its uses to patterns that conform to monadic laws. If you do `array.map(parseInt)`, that's valid JS, but as far as monads go, all bets are off!)
Also, note that I renamed a bunch of methods (resolve => of, then => map) and called things `Sequence`s. This is the value of functional orientation as it pertains to programming: when we say we've implemented monadic TimeSequence and SpaceSequence, in practical terms that means that I can write code for one type and reuse it for the other type because both follow the same semantics within one larger, common context. It's a lot easier to say "these implementations are not monadic" than it is to say "Promise-based logic is not compatible with Array-based logic because the method names are all different and the semantics of flattening Promises of Promises don't match the semantics of Arrays of Arrays (or Streams of Streams, etc)".
If this is still too abstract, here's an application: suppose I'm writing a task runner that takes tasks and runs them in parallel (but queues once we reach a parallelization limit). I can serialize this representation in space by turning a array of arrays into JSON. But I can also represent this as a grid of timings (meaning, for example, I can write shared code to iterate over both representations, rather than hard-coding different implementations for each type of grid)
Now, you could make an argument that in isolation and within some artificial constrainst, both Array and Promise are monadic (i.e. Promise<Array<number>> works just fine), but saying that's monadic is basically pedantic wankery, since for practical purposes, you can't arbitrarily write code against a specification to abstractly treat promises and arrays as an implementation of a common abstraction (e.g. a sequence of some sort)
> A monad, in addition to being a functor, must also not have extra funky semantics. A example of a functor that isn't a monad is `Promise`.
Not quite. You've come up with a great example of a problem with JavaScript Promise, but the problem is actually that it isn't a functor (it violates the composition law, for example).
Any of the standard functor-but-not-monad examples, e.g. multidimensional arrays (where you can implement map but can't implement map2 or flatMap, because the dimensions won't necessarily line up)?
For me when I was learning this the first problem was to grab what Mac Lane intended to say with "monoids" exactly (in monads are monoids such that blah) since the default notion from algebra didn't match (unital semigroup). It turns out that he is speaking of monoid objects, which is a technical term as in here [1]. There it describes monoid object in a monoidal category, which is an unfortunate clash of two monoid-sounding things that need to be thought independently. One clarifies first what is the monoidal category, and only then asks what a monoid-object in that category is. In our case one starts with an arbitrary category C. The category of endofunctors has as objects functors F:C->C, and as morphisms natural tranformations mu:F1->F2. Endofunctors always compose, and that gives the endofunctor category a monoidal category structure: The monoidal product, or in other words the tensor product is the composition of endofunctors. One checks that this monoidal product verify the monoidal category axioms. So then one has established what monoidal category we talk aboout. It is in that monoidal category where one consider monoid objects, and then notices that they correspond to monads.
Wait, a functor is just a pure unary function? And an endofunctor is just one of those where the argument type and return type are the same? This could have been explained to me years ago, in five minutes?
Sometimes it makes me mad that so much confusion (and as another commenter put it, gatekeeping) has been sown in FP circles through the invention of pointlessly-obfuscated terminology for everything (and through - among many in those circles - a lack of interest in connecting the very simple dots that would allow masses of people to understand these concepts). It's like when the medieval Catholic Church refused to print a bible in anything but Latin so that they'd remain the sole authority on its content.
Kudos to the OP for cutting through some of that, but shame on those who maintain this status quo.
Edit: assuming it really is (roughly) that simple. Some in the comments have suggested parts of the OP were wrong (assuming they aren't just being pedantic), so I'm curious to see discussion.
> Wait, a functor is just a pure unary function? And an endofunctor is just one of those where the argument type and return type are the same?
No. I don't know why the article talks about ordinary functions on values as if they're functors. They're not (or at least, not in a nontrivial way; you could come up with a silly, useless way in which they are, but that's not what anyone's talking about). Sorry, but it's the article that's misleading you here.
Roughly speaking, in the programming context, a functor is a generic type with a map operation. E.g., arrays; you can map a function over an array by applying it to each element.
Since there's only one category in play here, these functors are endofunctors of that category; one doesn't normally say "endofunctor" in this context since it doesn't convey any additional information. (As opposed to "a monad is a monoid in the category of endofunctors", where you want to specify that, because that statement is true beyond just the programming context.)
Mathematically the main thing stopping it from being a function is that categories are typically too big to be a set. Otherwise they're pretty much the same as a function.
The whole type thing is just something Haskell does, it's not something that's meaningful for general categories.
Not really, mathematically a functor is really two "functions," one mapping objects to objects and one mapping morphisms to morphisms, along with some conditions that make sure the functor is "structure preserving." It is fundamentally a type level construct because, as it is applied to programming, the category in question is the category of types (which is not technically a category due to the halting problem but we sort of hand-wave that away).
Sure a functor satisfies more conditions but that doesn't make it less of a function. Heck if you restrict it to mapping a single set of objects or a particular Homset it is a function, you just can't extend this to the whole category if the objects form a proper class (which happens fairly often).
The whole distinction between value-level or type-level is meaningless in general categories. Sure there's a distinction between morphisms between objects and functors between categories but you've also got the category of categories where the morphisms are functors between categories.
Edit: I'll have to concede that the article confuses them too much though, you can't just pick a random function and declare it to be a functor, especially when it's not clear between which categories.
> And an endofunctor is just one of those where the argument type and return type are the same?
Yes - "endo" means that in general. E.g. endomorphism.
> Sometimes it makes me mad that so much confusion (and as another commenter put it, gatekeeping) has been sown in FP circles through the invention of pointlessly-obfuscated terminology for everything (and through - among many in those circles - a lack of interest in connecting the very simple dots that would allow masses of people to understand these concepts). It's like when the medieval Catholic Church refused to print a bible in anything but Latin so that they'd remain the sole authority on its content.
> Kudos to the OP for cutting through some of that, but shame on those who maintain this status quo.
> Edit: assuming it really is that simple. Some in the comments have suggested parts of the OP were wrong, so I'm curious to see discussion.
The precise terminology is vital; it's how we avoid these errors when talking about this very abstract stuff. Given that the OP is very wrong, precisely because of the kind of attitude you've taken here, I hope you'll take this opportunity to reconsider your views.
> The precise terminology is vital; it's how we avoid these errors when talking about this very abstract stuff. Given that the OP is very wrong, precisely because of the kind of attitude you've taken here, I hope you'll take this opportunity to reconsider your views.
Your behavior is precisely the behavior that someone new to FP would see and say "Hard pass on that", which goes into the greater problem of FP being unapproachable to beginners because of the unnecessary gatekeeping. If you cannot communicate with a beginner in language they understand, A.) you don't really understand it either, B.) you're just pushing them away from whatever you're advocating.
> If you cannot communicate with a beginner in language they understand, A.) you don't really understand it either
This is true, but the problem is that people will always prefer the explanation that is, as the saying goes, "simple, neat, and wrong" over the explanation that is more complicated, especially if they (and possibly the person explaining) aren't aware that the simplified version is wrong. Even if one starts from an accessible viewpoint, any concept that is worth isolating as a concept will involve some difficult step in its exposition, and it is at that step that the person seeking to understand—not the explainer—has to decide whether to stick with the explanation despite the difficulty, or to be satisfied with an easy and wrong explanation.
You have to start with the 'simplified but not technically perfectly correct' and then add in the nuances to get to the real point. Starting with words like 'functors' that most software engineers today will not be able to define is not useful.
The article is likely aimed at intermediate-ish FP programmers, though, not people with no prior knowledge. (Although I suspect it is an example of "learning by teaching", since it is wrong on many counts.)
Learn You a Haskell mentions functors in chapter 8 and teaches them properly in chapter 11.
You don’t have to understand category theory to program in FP languages. But if we want to talk about the mathematical basis, you do need a common vocabulary at least to be able to communicate at all.
You could not really explain JIT compilation to someone not knowing anything about computers, could you?
If such a “definition” is sufficient, than I’m a rocket engineer as well because the rocket goes brr to the space..
I mean, it may as well refer to eagerness, which is something completely different from JIT compilation. You didn’t even say anything about what the compilation is about (which again, requires some knowledge on computers), nor about the reason for doing that.
Do you provide concrete "definitions" to people that don't/wouldn't understand? How would you handle a child asking you about something beyond their years? Would you just respond with a textbook definition and say "lol sucks to suck"? No, you'd use language they could understand, and you'd guide them as that language increased. This is the difference between "teaching" and "just saying things to sound smart".
It's actually insane how hard programmers want to gatekeep even basic concepts.
Well, no matter what you won’t be explaining multivariable calculus to a children. Concepts build on each other and for certain ones, you do have to build from something. You can start teaching math, and indeed for certain topics, taking shortcuts is allowable. But this is context-dependent and not universally true.
Like, you can talk about programming to a child, but still not about JIT compilation.
Communication is a two-way street. When someone is making an effort to learn, most FP advocates will happily make an effort to teach. But someone who comes in with guns blazing doesn't get to complain about being met with hostility, and if telling someone they're wrong when they're wrong is gatekeeping then it's a kind of gatekeeping that we need.
Being a teacher is a labor of love. There’s nothing wrong with a student coming in with any attitude.
This attitude justifying gatekeeping reminds me of Stack Overflow - mods tired of seeing the same wrong questions asked. But it’s a Q&A site and the purpose is for people to get answers to their questions.
> There’s nothing wrong with a student coming in with any attitude.
A student can definitely have an attitude that prevents them from learning effectively though. If anyone wants to see the use of correct terminology as "gatekeeping" then they are of course free to do so but the obstacles to learning the subject that such a mindset creates are then a logical consequence of their actions and entirely their own fault.
Yes, that goes for teachers. Not normal working programmers who choose to discuss FP in the terminology which has been commonplace for decades. They are under no such obligation.
A Q&A website needs both people who ask questions, and people who answer them. Perhaps the latter even more than the former. You can ask a question on stackexchange and have it answered by Peter Shor. Not having the platform inundadated by dumb repetitive questions and homework problems is the compromise you need to retain such talented people on your platform.
If you want an example of what happens to a Q&A site without any gatekeeping, look at Quora.
I would say the person you're responding to didn't come in "guns blazing". They seemed legitimately eager to learn, and expressed gratitude that the person that wrote the blog post used language they could understand.
Now, I would say you showing up and openly disparaging both the blog and the person you responded to qualifies as "guns blazing".
They said "It's like when the medieval Catholic Church refused to print a bible in anything but Latin so that they'd remain the sole authority on its content." and concluded with "shame on those who maintain this status quo." That's pretty "guns blazing" in my book.
> "It's like when the medieval Catholic Church refused to print a bible in anything but Latin so that they'd remain the sole authority on its content."
The debate is about using language as a gatekeeping mechanism. The analogy is spot on...
> "shame on those who maintain this status quo."
A person shows up eager to learn, expresses gratitude, feels scorned at all of the language-based gatekeeping that goes into this topic. You don't think it's fair to feel frustrated with the people doing the gatekeeping? (I don't think _you_ will, but only because I think you're one of the gatekeepers the original poster is (fairly) shaming).
> A person shows up eager to learn, expresses gratitude, feels scorned at all of the language-based gatekeeping that goes into this topic.
They expressed gratitude for those who told them easy falsehoods and scorn for those who told them harder truths, characterizing such honesty as "gatekeeping". That's not the action of someone eager to learn, it's someone who's eager to avoid learning, like those politicians who, rather than put in the effort to understand the economic implications of their policy, go shopping around economists until they find one who gives them the answer they want.
Can you paste me in your post where you did this? (Note: you can't). I'll even paste your response, so you can remember better:
>> Wait, a functor is just a pure unary function?
> No.
>> And an endofunctor is just one of those where the argument type and return type are the same?
> Yes - "endo" means that in general. E.g. endomorphism.
>> Sometimes it makes me mad that so much confusion (and as another commenter put it, gatekeeping) has been sown in FP circles through the invention of pointlessly-obfuscated terminology for everything (and through - among many in those circles - a lack of interest in connecting the very simple dots that would allow masses of people to understand these concepts). It's like when the medieval Catholic Church refused to print a bible in anything but Latin so that they'd remain the sole authority on its content.
>> Kudos to the OP for cutting through some of that, but shame on those who maintain this status quo.
>> Edit: assuming it really is that simple. Some in the comments have suggested parts of the OP were wrong, so I'm curious to see discussion.
> The precise terminology is vital; it's how we avoid these errors when talking about this very abstract stuff. Given that the OP is very wrong, precisely because of the kind of attitude you've taken here, I hope you'll take this opportunity to reconsider your views.
Where in this block did you give them "harder truths"? I see "No", "Yes", and then saying "reconsider your views". Again, the purpose of your post clearly wasn't to help, provide value, enable, but instead to disparage. Or, you know, gatekeep.
You'll notice that the post you quote was a reply to their post, where, as I said:
> They said "It's like when the medieval Catholic Church refused to print a bible in anything but Latin so that they'd remain the sole authority on its content." and concluded with "shame on those who maintain this status quo."
And as I said before that:
> someone who comes in with guns blazing doesn't get to complain about being met with hostility
It's not "gatekeeping" when there's no effort to engage productively in the first place.
I don't care to show you where I did something I never claimed to have done in the first place.
> So we're just saying things for the sake of it now, I guess.
As far as I can tell that's what you've been doing the whole time. It's the height of hypocrisy for you to complain that "the purpose of your post clearly wasn't to help, provide value, enable, but instead to disparage."
So you would say the same for programming in general then? Should programmers not use the word "function" because that word is foreign to non-programmers and might push them away?
Some terms are used for radically new concepts with no analogue, some terms refer almost exactly to concepts people already know, and some terms refer approximately to concepts people already know (and could be explained as "like X but with these differences")
For example: I might explain the programming concept of a function as "like the equations you remember from math class" (for pure functions) or "like a recipe" (for imperative functions).
I would also not, for example, make up a totally new term for a concept people already know about that just happens to be in the context of my new system of ideas. This actually comes up a lot in my day to day software engineering work: I avoid creating new abstractions in general, and when I do I strongly avoid introducing new terminology in the naming, and when I do I document and explain it to death in the comments, using analogies wherever possible.
There are lots of opportunities where I could come up with a whole new concept with a beautiful new name that nobody understands, and I explicitly choose not to.
I actually agree with this much. Explaining monads before explaining a lot of concrete examples of monads is putting the cart before the horse, and is where a lot of these tutorials go wrong (https://m50d.github.io/2013/01/16/generic-contexts is my own effort at taking the opposite approach). But calling something a functor when it isn't is extremely unhelpful; the whole point of using a special-purpose term like functor is to be very precise about what it is and isn't, and to avoid intuitions that would be misleading.
It often makes me very mad that so much gatekeeping has been sown into programming circles through the invention of pointlessly-obfuscated terminology for everything. Programmers are really arrogant most of the time, they dont want to teach beginners their craft so they just make everything difficult on purpose. They are like medieval priests yada yada.
Does what I write above bother you at all? Do you feel that it apply to you and programmers in general? Because that is the kind of generalization you are doing to another group of programmers.
I see a lot of functional programmers spending a lot of time trying to teach others. I also see a lot of people not wanting to spend any time learning so they just talk down on functional programmers, and I think its unnecessary.
Generalizations are always imperfect, and I felt I was explicit about the fact that there are exceptions (like the OP).
I'll admit my emotions got a little heated. I get really frustrated thinking about all the potential out there that gets wasted just because of gaps in communication (willful or otherwise), and not because of capacity for understanding. And this very comments section demonstrates the unwillingness by at least some members of the FP community to put things into terms that would help with that problem, so I do feel justified talking about the community as having an issue. Whether they represent a majority or a vocal minority is not something I can say with confidence, though I still feel like I qualified my original statements sufficiently.
I am a self taught programmer who first learned python and then learned Haskell. A lot of concepts in python were difficult when I was new and the same is true for Haskell. I found the Haskell community to be very welcoming and very willing to explain their terms and the reasoning behind them, and I dont find the negative characterizing from you and others about them to be true at all. That's why it really bothers me how you and others are so willing to slander a whole community based on what I perceive as not the truth at all. That's also why I wonder if you would be ok with non-programmers making the same generalization about programmers.
In my experience concepts like Functors, Monoids, Monads etc. are difficult, not because they are complicated, but because they are seemingly too simple. A Functor is pretty much something you can map, and every programmer knows list.map, so what's the point? The point is that when you have some infrastructure around using them, then you can see new ways of using them, and you can see that mapping makes sense over a lot more structures than lists. Even over something like a function "a -> b". The problem is that non-functional languages doesn't have this infrastructure around them, so they are not very useful, and so its difficult for people not using functional languages to understand what the point is. I dont really think there is any way to get past this unfortunately and the only way to get comfortable with the terms is to program in a functional language.
Good points. But I'd note that Haskell's infrastructure around Functor isn't typical of functional languages. Specifically in Haskell, I think it's pretty important to have an idea what functors, monoids and monads are, because these are typeclasses that you will almost certainly be using at some point. Not all functional languages have typeclasses or an alternative and convenient way to express these concepts, and in those, it's not so important to understand these notions abstractly.
I agree with your overall point, but I want to dig in on this bit:
> Not all functional languages have typeclasses or an alternative and convenient way to express these concepts, and in those, it's not so important to understand these notions abstractly.
This is true only in an especially strict sense. Haskell's typeclasses provide two basic mechanisms: one for associating a dictionary of data with a type, and one for automatically picking / deducing such a dictionary based on a given type. Only the latter is specific to Haskell (and Scala); the first can be performed even in Java, but you have to explicitly pass the desired dictionary (called a "trait") at all call sites. [0]
I legitimately use traits all the time in Java, and it even has some built-in ones, like Comparator. There's a great paper on the same fundamental technique at [1] (there called "object algebras").
It's certainly possible to express some of these ideas in other languages, but implementations are nowhere near as ubiquitous or idiomatic as in Haskell, where they pervade the standard library and most people's code. And I'd argue that's because the ergonomics of the solutions in other languages don't come close to those of Haskell's. Furthermore, there appear to be limits to how far you can take them.
For example, Java lacks higher-kinding which is needed to define a monad abstractly. This can be got cheated around using ideas from this paper (0), but it costs a cast which the compiler cannot prove safe. This is the basis for things like the arrow library in Kotlin, which while impressive, doesn't compare to the ergonomics of Haskell and still misses a bunch of standard abstractions such as Traversable, which are part of the mentioned infrastructure that makes monads (1) so useful to Haskellers.
It's tricky with functional programming. It's like reading SICP, and after a lot of effort, y-combinators and stuff, the outcome is like "See? Thanks to this invention, we can easily pass multiple parameters into a function". Which is fun, but not anything that will impress a non-functional programming user.
This is not an unusual thing to see around foundations of mathematics, either - where it could take dozens of pages filled with complicated argument and construction before one eventually can say, “We can multiply these integers now!”
I totally disagree with the spirit of your post. Taking things to this extreme means you end up in an arena where everything you discuss is completely opaque to outsiders and dissuades otherwise interested parties from ever being able to understand anything you're talking about.
No, although a pure unary function could be viewed as a functor, the other direction doesn't hold.
The common FP definition of a functor is anything that supports a notion of `map` (subject to the restriction that `map`ping the identity function does nothing, this is why a Functor is slightly more than just a Mappable). This is not a unary function although map takes a unary function as an argument.
The more general mathematical definition is a mapping between categories. Categories are sufficiently general that you can view almost anything as a category, which is why a unary function can be thought of as a functor (because a functor can be a mapping between categories that happen to be sets).
But a functor is both more general than a unary function and, in a certain sense, preserves more structure than a function, since it must preserve the structure of the underlying categories whereas functions generally only care about sets.
A Mappable would be anything that has a `map` function.
A `Functor` is a something that has a `map` function _AND_ obeys the rule that calling `map` with the identity function produces the same result.
ie: say I have some value `f` that is a functor. If I call `map identity f` I should always get back `f`. The mere existence of a `map` function doesn't imply this law holds.
The identity function always returns it's argument unmodified. (identity x = x)
(Now, in Haskell the type system does not encode that law, but not following it would be breaking the interface.)
If this explanation doesn't make sense or you need more examples I'm happy to expand
EDIT:
Both me and grandparent forgot another law for functors. They also need to preserve composition.
fmap (f . g) == fmap f . fmap g
In english, if I combine the functions f and g and map them, it should be the same as if I first map g and then map f
I didn't state this because this generally comes for free, assuming no shenanigans such as runtime type reflection/type-casing (but in that case all laws go out the window). In particular in Haskell (which is what I assume you're coming from given fmap and your ML-ish syntax) this is a superfluous law. If a type constructor's `fmap` obeys the identity law, it must obey the composition law.
> A Mappable would be anything that has a `map` function. A `Functor` is a something that has a `map` function _AND_ obeys the rule that calling `map` with the identity function produces the same result.
This sentence just taught me more about functional programming terminology than 4 years of university and 20 years of casual blog-post reading :O
Can you give an example where that doesn't follow from `map identity f == f`? Assuming of course `f` .. is what I think is called 'pure'? i.e. is deterministic on its input arguments.
Great question! There's a minority of them, but the ones I've run into the wild all usually boil down to having some internal book-keeping that is either triggered by function calls or can affect a function call.
For example, caches whose eviction calculation is triggered by function invocation aren't functors, even if you can map over the elements in the cache (since just calling any function on the cache can cause certain elements to be evicted). That's a bit of a weird one because caches also usually have some time-dependent behavior (which in general makes notions of things like equality a bit hard to pin down and so moots a lot of laws), but you can also have caches with eviction policies that are not based on time strictly, but rather deterministic heuristics that use the number of function calls as an input to the heuristic.
Another example is certain tree-based data structures that use function calls to rebalance themselves in a way where the rebalancing causes publicly observable changes. Again there just calling map by itself can trigger a rebalancing, regardless of whether identity is passed or not.
Another example is stuff like variants of `Iterator` where just iterating over something creates changes or function calls are logged.
FWIW all these cases of a mappable non-functor can be changed into a mappable functor, simply by "suspending" calling the function until you actually ask for a value (so the `map` call does nothing other than just squirrel the function away somewhere). So often the idea of a mappable non-functor isn't useful so much for truly distinguishing a functor from a non-functor, as it is for pointing out how you should implement `map` in a way that "makes sense."
To be honest with you, you're right in that you usually get that one without trying. Most of the things we think of as mappable obey the identity rules.
I think the confusion is calling anything that doesn't "obey the rules" a map function just because it is named "map".
For example, ruby's hash "map" returns an array instead of hash. That's not really a map, is it?
Making this useless distinction between "things with map function" and "functors" serves no purpose. It should be "things with real/fake map functions".
Sure, the name doesn't matter. The type does though.
`Functor f => a -> b -> f a -> f b` And it most type systems the law can't easily be captured in the type system.
interface Mappable<A> {
// Interfaces don't quite cut it here, because you want
// `map` to return a specific implementation of
// Mappable, not a general Mappable, but we'll let that
// slide for the purposes of exposition
map<B>(f: A => B): Mappable<B>
}
class MyWeirdMappable<A>(val myCounter: Int, val myValue: A) implements Mappable<A> {
// Notice the return type is MyWeirdMappable not
// Mappable, as mentioned earlier
map<B>(f: A => B): MyWeirdMappable<B> {
if (myCounter == 0) {
return this
} else {
return MyWeirdMappable(myCounter + 1, f(myValue))
}
}
}
Although this fulfills the contract of `Mappable`, it's not a `Functor`, because `map(identity)` doesn't always return the same (or equivalent) `MyWeirdMappable`.
Functors are type constructors, not functions (which map values). But you could be forgiven the misunderstanding, because it is easy to trip over this distinction given the identical syntax.
So, to make this absolutely clear, a monad is a type constructor in functional programming. This is why I personally prefer the more “creative” explanations of monads, because they attempt to explain what the monad is doing to the original type: adding context, or the possibility of a null value, or multiple values, or a probability distribution over values, etc.
A type constructor is something that takes a type and gives you a new type.
For example, in C, if you have any type Foo, the pointer operator * will give you a new type Foo*.
Another example: in Haskell, Maybe is a type constructor, since it takes a type parameter a (Maybe a). So 'Maybe' is a type constructor, but 'Maybe Int' is a type.
So a type constructor is like a function, but it operates on types, not on values.
So this is a perfect example of how things could be better-explained to the average developer via analogy:
"You can think of a type constructor like a generic type, particularly the way those work in languages like TypeScript"
Edit: The C example was added after my initial comment, and is better than nothing, though I'd tend to say the pointer example is a bit of a weird one to go with. Of course intuitiveness is relative and I'm not saying an example has to mention TypeScript or whatever to be valid. But I do think, like, C++ templates would be a somewhat clearer comparison to make for that audience.
The operator dereferences something - it certainly does not create a new type. And neither does the above - the concept of pointers to addressable types is innate to the C and C++ type systems - if you create a type Foo, you get pointers to Foo for free.
The fact that pointers to Foo are "free" doesn't invalidate the notion that the * is, in some sense, a semantic extension of whatever Foo is and thus a generic type. I know that this is not literally true in the "theory" of the C programming language and type system, but conceptually it matches up pretty well.
A function that take one type and gives you another type. So (in Java for example) you have a generic type such as List<T>. But that is not a really a type because you can't have a value of the generic type. It is actually a type constructor, you can give it another type (say String) and it will give you a type List<String> which can actually be instantiated to a value. So in the context of programming languages it is just a fancy word for a generic or parametric type.
Values are things. Concrete. Since we are manipulating computers, a value is really just some abstract symbols--1s and 0s occupying a slot in memory. The meaning of the symbols exists on a higher level, what we usually call semantics.
Types are a well-studied method to attach semantics to blocks of otherwise meaningless (but concrete!) symbols. By declaring a variable (which is just a pointer to a memory block containing arbitrary symbols) is of type Int, we are establishing that in the context of the program, the symbols occupying that memory block are to be interpreted as the encoding of an integer.
Functions are transformations of values. They manipulate concrete things to produce other concrete things. By specifying the input and output types, we ensure that the transformations applied by our functions are only used on the right kinds of things, and we also know what kind of thing we will get out of the function. Mind you, these things are still all just arbitrary symbols in blocks of memory, but now we know how to semantically interpret them based on the function's specification.
Type constructors are also transformations, but of types. That is, we use type constructors to modify or enhance the semantics of a basic type. Functors are essentially type constructors that extend function semantics as well: if F<-> is a functor, then you can "lift" any function from type A to type B into a function from type F<A> to type F<B>. (Note that I'm using the commonly recognized "generic type" angle bracket notation to deliberately avoid the confusion of Haskell's pedantically minimalist syntax.)
I think this description provides a much more intuitive path to the understanding of, say, a list as a functor. A "list" is a generic structure that can be applied to any semantics, evident in the phrase "list of X". The preposition "of" makes it clear that this is a semantic extension of whatever kind of thing that X is. Furthermore, there is an obvious way to lift functions: just apply the function to each element of the list, and collect the results in a list. Bam! There's a functor. This is starting to feel like blog post territory, but I'll forge ahead...
An important point here is that the "semantic structure" that type constructors add to a basic type has to come from some extra data that is used when defining the type constructor. In the case of functors, we have to actually describe an algorithm that implements the lifted function in terms of its basic version (as we just did for lists).
So a monoid is also a type constructor, and it must come along with a description of the monoidal product: For type M<A>, we need to describe a function (the monoidal product) which takes two A's and returns another A. We must also identify a specific value within type A that serves as the identity element. Now, to actually be a monoid, the monoidal product and identity element must satisfy some laws, but in general proving the laws are satisfied by a given constructor is outside of the capabilities of our type syntax. This is a step up from the functor type constructor, which needs only a valid implementation of the lifting function (called `fmap` in Haskell) in order to establish that we have actually created a functor.
In any case, to arrive at monads we don't actually combine the functor and monoid type constructors; instead we gently introduce monoid semantics on top of a functor. We do so by making the functor type constructor itself act like a monoidal product, so that repeated applications of the type constructor don't create "nested" versions of the semantics, they just stop at the first level instead. Lists are again a very straightforward example of this: List<A> is a list of things of type A, and List<List<A>> is a list of lists of As, and there is an obvious way to bring the list of lists back down to just a list: flatten it.
> Note that I'm using the commonly recognized "generic type" angle bracket notation to deliberately avoid the confusion of Haskell's pedantically minimalist syntax.
I really appreciate this. I know the Haskell syntax kindasorta, but my brain just doesn't grok it well. Vs anything along the lines of Generic[Type] or Generic<Type> is just far more familiar for most audiences, myself included.
The people whom Haskell type syntax makes sense for are largely not the ones trying to learn this stuff.
Is it? You claimed correctly a couple paragraphs back that a functor is a type constructor F bundled with the ability to "lift" functions into the context of F. So `List` is a functor in the usual way, and so on. But a monoid cannot be a type constructor, or else `String` could not be a monoid. A monoid is a concrete type M bundled with multiplication and unit on that type.
That was a really nice description. I've struggled to get traction with a lot of this stuff for a while (and not really needed to understand it, so my curiosity remained unstated) ... but this has really helped. Thank you!
Do you say "sigh" because the functor arrows typically go sideways in a diagram? I'm taking a classroom course in category theory right now, but it's my first exposure to actual formal instruction in this subject so I don't know all the standard terminology just yet.
> I wish people understood that fp is much easier to understand by reading definitions.
The real landscape of its adoption begs to differ. For the great majority of people, examples and analogies are fantastically more efficient for communicating ideas than building up from first principles. You get to re-use existing mental machinery, intuition, etc, until enough experience has been gained to refine it.
These concepts are usually explained via first-principles definitions, and they are usually opaque and unapproachable for most people. That's not a coincidence.
There's nothing in this list:
- Algebra: Semigroups, Monoids.
- Algebraic Data Types: product and sum types.
- Functor, Applicative, Monad
which covers basically all the fundamentals to be proficient in functional programming that has definitions that are opaque and unapproachable. And all of those have very simple examples, both in real life and especially programming. But definition has to come first, or you have this great mass of people that do not understand what they talking about even when they blog about it.
If you can take your time to understand that a type constructor (and take the time to see what it is) and a map function form a pair called functor, you are equipped to learn about monads.
It's not rocket science, but yes, it requires a bit of studying and learning, which is what people don't want to hear, and instead choose the long road of contrived example-driven, inaccurate and confusing blog posts.
As another commenter pointed out, the key is to use an example as a starting point and then refine from there. "X is like Y, but different in these ways". Comparisons don't muddy the waters; they give people a quantum-leap from 0% understanding to 70% or 90% understanding, from which point the remaining gap can be filled in at the usual rate. To ignore this is to ignore human nature.
(a -> b) -> F a -> F b; the parentheses are critical. I don't fully disagree with your point, but if you're going to emphasize rigor and definitions, it would be wise to make sure you're not setting people on the fence up for mistakes akin to those in the original post.
To add, I suspect that the Haskell type notation is not intuitive to people not familiar with it. For anyone wondering, (a -> b) -> f a -> f b means "A function taking a function from one type to another "(a -> b)" and a functor applied with one type "(f a)" and returns a functor applied with another type "(f b)".
> I wish people understood that fp is much easier to understand by reading definitions.
I wish more FP writers understood that not everyone has the same neurotype, and "easier to understand by reading definitions" is far from a universal statement.
A functor has three things:
1. A type constructor
2. A "map" function
3. A "flatten" function
So basically it is just a parametric type such as List<T> which has a type constructor so you can get a concrete type (eg List<String>), a map function which takes a function f: A => B and and turns it into a function List<A> => List<B>, and a "flatten" function with will turn a List<List<A>> into a List<A>.
The last part is what allows "flatMap" which takes a function f: A => List<B> and turns it into a function List<A> => List<B> and is really just a shorthand for doing map and then flatten.
A functor is a type constructor with a map operation (that obeys composition and identity), similar to how a group is a set with an operation. (And similarly, we casually talk about the type as though it were the functor, just as we talk about the set as though it were the group; if someone says "the Option functor" that's a slight abuse of notation in the same way as "the group of integers").
In particular, a functor is a type constructor F together with a higher-order function deriving transformations `F T -> F S` given a transformation `T -> S`, subject to some semantic requirements. This is the `map` or `fmap` people refer to as defining the functor.
Unfortunately, due to abuse of notation, the type constructor isn't given much focus. But it's true that "type constructor" is the first conceptual hurdle.
You asked. I'm happy to dissect it to your level, but I don't know what you may be familiar with, and if you're not comfortable with type functions, I'm going to have a hard time motivating the extra bits a functor has.
The List functor is a combination of the type function sending `T` to `List<T>` and the ... what do you want me to call it, a function function? implemented in Java as:
static <T, S> Function<List<T>, List<S>> map(Function<T, S> f) {
return (ts) -> {
var ss = new ArrayList<S>();
for (final var t : ts) ss.add(f.apply(t));
return ss;
};
}
We call it as map(f).apply(ts). If we want to pass them both at once, we can rewrite the function so that it's not static, but it doesn't much change that it's a mapping operation.
But it's not the `map` method that's the important part, so much as the idea that we can (or want to; can't in Java) pass `List` to any function that needs a Functor, which can then use whatever `map` implementation that functor has, without knowing what actual type function it was given.
Really, I suspect it's neither the type constructor nor the map function that's the conceptual hurdle. It's abstracting over the type constructor; taking a type constructor as a parameter. You may have never used a language that supports that, or seen a need for it, and this may all seem like needless sophistry until you do.
I might get flack from the FP purist crowd, but I like to think of functors as containers + context.
- 5 is a value. Its type is int
- int is a type
- T is a type parameter. Like the x in "f(x)", we have to pass one in to evaluate it
- List<T> is a type constructor. It takes a type, T, and spits out a new, "compound" type. It will "contain" T's.
- [3,5,7] is a list. Its type is List<int>. We fed the type "int" to List<T> to construct a new type
- List<T> is a functor because it "contains" T's. List<int> "contains" ints.
- F<T> -> () (a function which takes a T and returns nothing) is a type constructor. It's not really a functor. There's ways in which it technically can be (e.g. decorators in python) but for the sake of pedagogy and giving a counterexample, I'm going to say it's not, because you usually aren't going to map over something like that.
- because functors "contain" other values, you can apply a function to the contents, without changing the container context. This is called map. It may change types, eg mapping sqrt over a list of ints could give floats. But it always gives the same "container type"
The tricky bits:
- To be a true blue functor, there has to exist an identity function that is a no-op and gives you the same types and values back. You needn't define it, it just has to be possible to define.
- functors need not actually "contain" anything, nor the contained value be primitive data. But they always have this wrapper-like feel to them, with an outer type, an inner type, some context/data/value/computation, and the ability to map over that inner value. E.g. Optional<T> could contain nothing, but you can still map over it.
- it's not necessary to be able to dereference or "dispense" the contained value. Sometimes, like the IO monad pattern, the inner value gets "stuck". it never leaves the IO, it's only ever (flat)mapped over.
- the inner value can be: nothing, a single datum, a collection of data, a function, a computation, another functor, another type constructor...almost anything you could assign to a variable.
- well-known functors include: List<T>, Dict<K,V>, Optional<T>, Result<T,E>, Future<T>, Generator<T>, IO<T>, Tree<T>. T* (pointer to a T). Virtually all container types.
I like your approach. However, I don't think that this:
- List<T> is a functor because it "contains" T's. List<int> "contains" ints.
Is really correct. I believe a `Container<T>` becomes a functor only if it also 'has' (can have?) a function that can take a function and apply it to all values in the 'container'. So, a 'map' of some sort.
I mean, I see your explanation of 'map' later on. It's also probably true that in real world software engineering contexts any 'container type' of that kind would also be one that either has or can naturally have a `map'. It's just that if someone willing to understand this read your comment and went: "Aha! Some container thing is a functor because it contains things!" I think they'd gain incorrect understanding.
I have pretty much the same intuition, except I think of functors not just as containers, but as sources of T. If you have a source of Ts, you can adapt it with a function from T to S to get a source of Ss. If you want to apply a pipeline of type-changing operations to some source of initially Ts, a functor is the right metaphor. (And if you have a sink instead of a source, that's a contrafunctor.)
If you have two sources and you want to combine them into a single source, you need an Applicative Functor, also known as a monoidal functor.
If you have a source that itself produces sources, and you want to flatten the nesting and treat it as a single-level source, you need a Monad.
> F<T> -> () (a function which takes a T and returns nothing) is a type constructor. It's not really a functor.
I'm having a little trouble matching the prose against the type signature. A function which takes a T and returns nothing would have type `T -> ()`; no F in sight. I'm guessing you meant that F<T> is defined to give `T -> ()`, in which case F is indeed not a functor; it's a contrafunctor, a place to which Ts can be sent (not retrieved).
Not exactly dynamically - both a monad and a functor have to be a kind of "function" from type to type. The most common kind is a generic type with one type parameter. (e.g. you can see "List" as the "constructor" that takes "String" to "List<String>", takes "Int" to "List<Int>" and so on)
Not quite - the type constructor is the thing that does the same thing with the types themselves, not with Class (which is sort-of-but-not-really a way to represent types as values). In Java or C# there's no way to actually represent a type constructor (e.g. you can't have a class that takes a type parameter F that could be List or Set, and then you use that type to form F<String> within the class itself and it will be List<String> or Set<String> depending on whether you do new MyClass<List> or new MyClass<Set>), but other languages are more powerful in what they let you do with types. Look up "higher-kinded types" for the general concept.
> Sometimes it makes me mad that so much confusion (and as another commenter put it, gatekeeping) has been sown in FP circles through the invention of pointlessly-obfuscated terminology for everything (and through - among many in those circles - a lack of interest in connecting the very simple dots that would allow masses of people to understand these concepts)
This is why people say "a monad is a monoid in the Category of endofunctors" as a joke whenever anyone posts an unnecessarily complicated explanation. This is the biggest and most visible flashpoint between people who don't understand, and the people who don't understand why they don't understand and think that defining things in terms of other things that you also don't understand is a viable strategy.
You see, there's a bit of irony here in characterizing jargon as gatekeeping, because in the author's attempt to distill it, some pretty critical stuff got lost in translation.
I share the sentiment that FP jargon can be impenetrable to the uninitiated, but the same can be said about programming jargon to non-techies: it may sound like gatekeeping to talk about "closures" but there's technical reasons why closures are called closures and global state being accessed by functions are not.
The same goes for FP. Saying `val => val + val` is a functor because it maps numbers to numbers isn't really correct: you could arguably only say that in an universe where `val + val` is the only possible operation, and even then, that's not really correct because the utility of the function is hardcoded (meaning that if we were to hypothetically introduce an axiomatic operation, the internal consistence of this new algebra would implode). In a more useful algebra in a regular universe, the mapping must hold for any valid operation for that type. So a functor for the `number` type ought to look more like something like `Number.prototype.map = function(f) {return f(this)}` (i.e. the mapping contract holds for addition, subtraction, and all other algebraic operations that are valid on numbers contained within `f`)
There are also practical technical things the article glossed over: Array.prototype.map is not monadic. The signature of the callback is `(T, number, Array<T>) => U`, which is most certainly not unary (and for that matter, using JS to illustrate FP is fundamentally problematic since JS isn't side-effect-free to begin with). If you think that's nitpicky, one fundamental thing with FP is that composition relies heavily on algebras not breaking on corner cases. This is why, for example, fantasy-land specifies a different method name for `map` (called `fantasy-land/map`); because `map` is already taken by Array and it breaks some composition patterns (notoriously, `[1,2,3].map(parseInt)`)
I absolutely think this is nitpicky, and a perfect demonstration of the pedantry I'm talking about:
> Array.prototype.map is not monadic. The signature of the callback is `(T, number, Array<T>) => U`, which is most certainly not unary (and for that matter, using JS to illustrate FP is fundamentally problematic since JS isn't side-effect-free to begin with).
The unspoken understanding in the OP is that we're only using .map() in the single-argument form. The author makes it clear that only a function with a single argument counts for their definition, and I feel there's also an implicit understanding that that function has to be pure.
The fact that JavaScript technically lets you break both of these assumptions is entirely beside the point. For the sake of teaching, this idealized case is carved out for the example, and I for one had no misconceptions resulting from the relevant quirks of JS. We aren't writing a bullet-proof type system here, we're learning about concepts.
It's not beside the point, though. It's a crucial aspect of FP!
Perhaps I'm getting a different reading from the article than you, but as someone who's gone in and out of this rabbit hole, I found that the author was making some pretty stretchy claims. For example, he says "It may also seem like every monad that is needed already exists. Some common ones are" and proceeds to name Arrays and Promises, neither of which can be used in functional composition beyond the very basic `foo.map(f)` (and may break even then, as per my trivial example above!)
It's fine to try to use a non-functional language to try to explain functional concepts to those who are familiar w/ JS but not FP, but also keep in mind that you may be misunderstanding unknown unknown nuances because of the misappropriation of one domain (JS) to explain another (FP). You yourself are an example of someone who seemed to be about to take a mischaracterized technicality at face value before an avalanche of people started pointing out issues. How do I know to what extent you or someone else understands the implications of functions not always being endofunctors, Arrays not actually being monadic, or why map vs fantasy-land/map matters?
There's a real cost when people come out of reading articles thinking they know more FP than they actually do. This exact discussion about strictness already had implications to the design of Javascript itself: the algebraic consistency argument was brought up while Promises were being specified, but it got dismissed and we ended up with non-monadic promises (and shitshows festered all over the place as a result, e.g. rxjs had to special case them, and we have stuff like fluture.js because why not have multiple future types). The Fantasy Land project itself was created out of spite of a dismissive comment in the promises discussion calling algebraic consistency "fantasy land". On another occasion, one of the React core team members went on twitter at one point saying react hooks are pure (and don't even get me started on algebraic effects). The amount of misunderstanding surrounding FP - even among JS engineers at FAANG - is frankly scary and "loose-is-fine" mentality seeping into the design of widely used APIs is not exactly ideal.
Kind of reminds me of an old saying I heard somewhere, that I'll paraphrase here: "novice writers use little words, intermediate writers use big words, and expert writers use little words."
Like, it's fun to communicate in technical jargon -- and personally I'm quite proud of the vocabulary I have built up over time -- but you are totally correct in that it serves as a gatekeeper for an in-group to retain its dominance over a given field. There is a lot to be said for effective communication using a simple, base language and reserving obtuse technical terms for areas where one needs to be very specific.
There's another point to be made for not inventing new technical terms when existing ones apply. The amount of overlapping terminology in this field is infuriating to me.
I very much agree with part of your point, especially the novice-intermediate-expert part on jargon. I generally favor wording that is as simple as possible, but no simpler. Sometimes technical precision is important, and when talking to colleagues and other people that are on a similar technical proficiency level as me I prefer concise and informative words. I'd rather say "ARP poisoning" than "network attack", because the latter loses information, but would obviously use the latter to muggles.
I don't agree that having a domain jargon that is technical and concise is "gatekeeping" for functional programming. If you are a frontend developer you need to know what the DOM is. If you are a Haskell programmer you need to know what a monad is. The fact that you don't get the Haskell jargon "for free" coming from other programming disciplines doesn't mean that it's "gated", it just means you need to learn. And there are plentiful resources to help you with that, countless "how to understand monads" articles and so on. In my experience, the Haskell community is perhaps the single most welcoming and helpful programming community. There's even a handy guide with big, friendly drawings.
My point wasn't so much a dig at FP as it was at programming in general. For example, I started my career writing Perl, which uses the word 'hash' to describe a dictionary-like datastructure. But Python uses the word 'dictionary' to mean the same thing. Javascript's equivalent is an 'object', though it is effectively a different. Other languages call this datastructure a 'map', others an 'associative array', and so on.
It's like, effing pick one! And if you have to have multiple why do they have to overlap with other completely different things? When I first read about a 'map' in this context I was very confused.
You also see this a lot comparing Microsoft environments to everyone else. Reading microsoft docs in the late 90s (which is where I first learned a lot of these concepts) you learn one set of vocabulary, and then in the _nix and webdev worlds you learn a whole different set. Take 'databinding', for example... I have not once heard this term used discussing shadow DOM stuff like React or Vue, yet databinding is exactly one of the services they provide. But no, they have to call it something different, making a lot of prior-art type research much more difficult than it needs to be. Perhaps it is part of the reason why the webdev world seems so intent on pointlessly repeating history. It hampers discussion and contributes to the conceptual isolation and tribalism that seems so common in this field.
(And in the perl example, yes I know it's short for hashtable and that this is because this dictionary-like thing is exactly that, but I think that from an end-user's point of view it would be best if all these different terms were unified)
Edit 2: I'm sorry for getting a little inflammatory with my original comment. I have a headache today, and one of my biggest frustrations is needlessly poor communication of concepts, especially if it's willful, and especially if it wastes the potential of capable people who could otherwise be given understanding.
With that said I may have gone on a bit of a rant here and made some generalizations, and I don't feel good about that aspect, so I apologize.
You remind me of when I started to actually get this stuff and it occurred to me that monads are just metadata+data with some special properties, and I posted about it on reddit and got downvoted to hell and told the many ways how that's wrong. The FP crowd...must be great at parties. I get this frustration.
I think a big part of it is difference in definitions. There's the mathematician's monad, which is pure and abstract and obeys all these laws. And then there's the engineer's monad: an interface you can map, ap, and flatmap over. People get so hung up over "algebraic purity" they forget why they were invented/co-opted for software in the first place: to solve the problem of applying pure functions to side-effecty operations.
> A monad is a wrapper. Anyone who tells you otherwise is being obtuse.
> It's like when the medieval Catholic Church refused to print a bible in anything but Latin so that they'd remain the sole authority on its content.
I'd say reading the Bible, or any other deep philosophical/spiritual text in a translation is almost an utter waste of time (unless that actually helps you psychologically, then it is not), if not harmful.
The original words and phrasing with all their possible meanings make a huge lot more sense than specific translations.
Something that sounds banal or weird can actually mean something entirely different and deep once you carefully analyze the original words.
It is, however, important to remember Latin is not the original for the Bibile. But it still has a lot of what has been lost in many other translations.
A functor has two pieces: a pure unary function from types to types, and a pure unary function from functions to functions. The article doesn't talk about the function on types; it doesn't even talk about the function on functions. Its first example of a functor is the function `(num) => "" + num`, which isn't a functor. They map values of Integer to values of String, but they do not map any type to some type, nor do they map any function to some function. Neither part of a functor is present nor nearby.
As an example, for every type T, there is a (non-generic!) type of lists with elements of type T. The non-generic part is really, really important, and is probably a big source of confusion. When we define, say, `class List<T>`, we're defining a whole family of independent types, which we might concretely name List__Integer, List__String, and so on. The List<T> notation is a way of getting that specific type without knowing what its name is. By abuse of notation, we (programmers, not category theorists) talk about List<T> as though that were the name of the type. Theorists separate the two notions, and consider `List` to be an actual function from types T to types List__T, whatever that type actually is.
Most languages that let you define a family of types don't let you refer to the type function on its own. Java (say) never lets you refer to the List function on its own; the name List refers to some other shameful and unrelated concrete, non-generic type. When your language does let you speak about the type function itself, and pass it around to other things, we say that it has "higher-order types". (Just as a language that lets you speak of and pass around a function `factorial` without invoking it has "higher-order functions"; notwithstanding closures, that's what "higher-order" means. [0])
Just having a type function is not enough to have a functor. You also need a function that takes transformations between two types, T and S, to transformations between whatever types the type function sends them to. (For List, we said they're called List__T and List__S, but we can always refer to them indirectly by saying "whatever List maps T to", which is generally written F<T> for any type function F.)
Because of the abuse of notation, we collectively "forget" that `List<T>` defines a function from types to types, and pretend that a functor is just defined by what it does to functions from T to S. But most of the point of functors in functional design is that you can pass around the type-function part, `List`, with the knowledge that it describes a mappable type. If you don't pass around type functions, the concept of a functor will be useless to you.
It's not an artificial barrier, you just didn't learn anything useful yet. So now you know what the words mean, but they mean super mundane stuff that you've probably dealt with a hundred times. You already knew how to use map and array concatenation before you even heard of the word monad.
There's some magic to these words, but that magic is in how they're used to create new software, real things you can do with them that are easier to talk about when you've got single words for the concepts instead of vague descriptions.
People in Haskell do things like having concatenating to an array be the same syntax as executing two statements sequentially. That's sort of weird, and probably useless, but the whole idea that two sequential statements are basically a monadic operation over the state of your computer, and maybe over the entire world was a new idea in the 90s and it captured something in the formal domain that we hadn't really captured as well before I believe.
edit: I'm not trying to convince you that monads are important or even useful in general, I hope it doesn't come across that way. My favourite programming languages don't have monads as a fundamental concept, Haskell fell from my list a couple years ago. It's an interesting way of thinking about types and computing and I think that makes it more interesting than just a bunch of dense definitions for mysterious looking names.
I should be clear: you don't have to sell me on Haskell or these other concepts. I would love to add all that stuff to my toolbelt. I'm suggesting that the zoo of new terminology makes the effort barrier to doing so much higher than it needs to be.
I'm sure some of it really is warranted, but my experience looking at formal math and logic is that they make things a lot harder than they need to be by introducing terms and symbols that stand-in for intuitive concepts and require unnecessary mapping back and forth between what you're reading on the page and the underlying concepts.
Alright, but you were praising the article for conveying the meaning of the words, when those meanings are useless without some sort of interesting application.
I believe people find monads difficult to grok not because the definition is hard to remember, but because the situation in which it is useful to distinguish the type class is abstract and frankly not super useful in most cases.
Funny thing about zoos of new terminology, back when I was an undergrad I found the type classes to be a confusing subject. Then one day I realized that type and class are basically synonyms so you might as well call them type types or class classes, which totally cemented the idea for some reason. My brain had been getting stuck on this random terminology and this just unclogged it.
> those meanings are useless without some sort of interesting application
They're useful when trying to grok other blog posts or discussions that talk about them (often in service to some further concept that you have no hope of understanding without knowing that first layer of terminology)
> My brain had been getting stuck on this random terminology and this just unclogged it
Exactly! What I'm requesting is that the FP community at large gets more comfortable with the idea of providing those "X is roughly just Y" comparisons for newcomers, so they don't get stuck on all the random terminology and can be "unclogged".
To expand on this, because it's actually fascinating...
Functors capture a particular pattern of "pipelining": a series of operations A -> B, B -> C, etc. can be uniformly assembled in the context of any arbitrary functor F, ultimately giving a unary pipeline `F A -> F C`. (I won't detail what this means completely; I'm going for a gut instinct in the following bit.)
But what if you have a binary function, (A1, A2) -> B? Functors only let you assemble unary operators; there's no provision for taking the outputs of two pipelines and weaving them together. Applicatives (or, "monoidal functors") give you an additional operator that let you turn a pair `(F A1, F A2)` into a contextual pair `F (A1, A2)`, which can then be fed to a unary pipeline. (In terms of pipe shapes, it's a Y-bend.)
Monads extend this in a less interesting way, but in the sense of "monadic" as "unary", functors are actually more monadic than monads!
> Sometimes it makes me mad that so much confusion (and as another commenter put it, gatekeeping) has been sown in FP circles through the invention of pointlessly-obfuscated terminology for everything
That's only Haskell. The other FP languages have sane communities.
A monoid is something where you take two things and multiply them to get one thing. 2 x 3 = 6
In a monad, you take a doubly-nested thing and "multiply" and get a singly-nested thing: [[a,b],[c]] => [a,b,c]
The monoid laws say that, though you can multiply in different ways, it doesn't matter what order you do it, the end result is the same: (2 x 3) x 4 = 2 x (3 x 4)
The monad laws say the same thing: the order you do the "un-nesting" doesn't matter:
Yes, this was unfortunately my first thought too when I saw the headline. The video is really funny though. I don't know how popular a meme it is generally, the first and only time I saw it used was this one wrt functional programming and it still makes me laugh every time I watch it.
That's actually the only correct part of the blog, arrays form monoids via concatenation and empty arrays.
That's algebra tho, which is very relevant to functional programming (monoids capture the essence of composition) in general, but not the right monoids in category theory.
Of course they form a monoid with concatenation, but it's not the monoid that makes the monad (which should be pretty obvious since concatenation is not used in the monad operations for arrays).
If you're looking for a not-quite-monad tutorial that answers real-world programming problems, blows the gates off monad-notation gatekeeping, and pokes good-natured fun at the OP title, I highly recommend Railway Oriented Programming:
https://fsharpforfunandprofit.com/rop/ for the "hub" that discusses how this isn't really a monad tutorial but hints at how you can go deeper - and if you read this before you read the OP you can see how the meta-puzzle pieces fit together!
At the highest level, this helped me see that monads are really just Level 2 of "things that help you glue things together that weren't meant to be glued together (particularly if those things emit changes to some external state.)" And that's exactly what the railway/error-handling analogy brilliantly shows. You've probably written almost-monadic things yourself, you just don't know it!
Just today, Don Syme wrote up thorough explanation on why he won't be adding type classes and more higher-order-types (or whatever the correct term is) to F#. As someone learning F# and starting to use it in production, I love it because it shows that there is a focus on practical FP even at the very top of the community. https://github.com/fsharp/fslang-suggestions/issues/243#issu...
> This phrase is the cheeky line to (somewhat) formally define the monad
It's actually a satirical joke[1] that people started taking way too seriously. Honestly, imho people should never use this line when explaining monads. It's like saying 'C is a purely functional programming language!' because Conal Elliott, around the same time, wrote[2] a parodic blog post making fun of purely functional programming zealots.
The phrase that forms the title of this post is very close to what (CT giant) Saunders Mac Lane wrote, quite seriously. In fact it's missing the word "just"! Iry was inspired by Mac Lane, but you seem to have got the wrong end of the stick on the actual status of these words.
I am obviously talking in the context of programming, not abstract math ;-)
In this context, it's quite obvious that I am correct. Programmers around the world wouldn't have been perplexed for a decade because of a labyrinthine quote from Mac Lane's Categories for the Working Mathematician.
Conal Elliott wasn't making fun of pure functional programming zealots. Elliott is a pure functional programming zealot, and was making fun of Haskellers who defend the IO type as a purely functional way to express effects. He thinks the IO type sullies Haskell here, and that we should have picked a different representation for effects (historically, that was true FRP, something he conceived with the late Paul Haduk).
This. By that same virtue (although admittedly with far greater stakes), I wonder if the GP would call safety regulations on civil engineering a similar kind of "gatekeeping" in need of "disruption".
Not exactly. When using the I/O monad in a pure language like Haskell, your code doesn't directly have side effects, instead you're building a container (a monad) of instructions of what side effect having operations to do, and what should be done with the results. The Haskell runtime then takes this monad and unwraps it layer by layer, each layer executing the side effect having instruction and using the results of the side effects as input for unwrapping the next layer.
You could argue that because of this system the language itself is pure and without side effects and without mutation.
Note that the effect of this system is exactly the same as a language that does have side effects. They are functionally identical. The nicety of Haskell's purity comes from how the monads allow you to organize your code.
By the way, not sure if this is controversial but JavaScript's I/O system is a lot like the I/O monad. I/O doesn't really get executed immediately, and you can't directly operate on the results of I/O. The runtime executes the I/O after all JavaScript's been executed, and you use callbacks to tell the runtime to do whenever the I/O data returns.
Of course JavaScript does allow for mutation, so it's not pure in that sense.
> instead you're building a container (a monad) of instructions of what side effect having operations to do, and what should be done with the results. The Haskell runtime then takes this monad and unwraps it layer by layer, each layer executing the side effect having instruction and using the results of the side effects as input for unwrapping the next layer.
Note that this is the implementation of a specific monad - not all monads are like that. Many monads are not containers, and some can't be "unwrapped" at all.
> Note that the effect of this system is exactly the same as a language that does have side effects. They are functionally identical. The nicety of Haskell's purity comes from how the monads allow you to organize your code.
You might enjoy "the C language is purely functional": http://conal.net/blog/posts/the-c-language-is-purely-functio... . The useful part of purity is that the pure form of Haskell has some interesting algebraic structure (in particular there are a lot of ways to refactor code while preserving its semantics), whereas the pure form of C or javascript does not have many equivalence laws.
> By the way, not sure if this is controversial but JavaScript's I/O system is a lot like the I/O monad. I/O doesn't really get executed immediately, and you can't directly operate on the results of I/O. The runtime executes the I/O after all JavaScript's been executed, and you use callbacks to tell the runtime to do whenever the I/O data returns.
I think you're conflating interface and implementation here. Javascript I/O is implemented similarly to Haskell I/O in some ways, yes. But the interesting part of Haskell's I/O isn't the implementation, it's the (pure) API that it uses, and Javascript has nothing like that.
> But the interesting part of Haskell's I/O isn't the implementation, it's the (pure) API that it uses, and Javascript has nothing like that.
No, I insist JavaScript really has a pure approach to I/O, quite like Haskell. There is literally no side effects except for application state mutation from the perspective of a JavaScript function (if you disregard the few deprecated synchronous API's). And this pure API has proven very useful and distinctive for JavaScript (i.e. through node.js)
> There is literally no side effects except for application state mutation from the perspective of a JavaScript function (if you disregard the few deprecated synchronous API's).
That's a pretty big "except" - there are no side effects except for all the side effects (and there's nothing unique about JavaScript there, that much is the same as almost any other language). JavaScript's approach to I/O, like most languages, uses things that look like functions but aren't functions, in that they give different outputs for the same inputs. The whole point of Haskell's I/O system, the thing that separates it from other languages, is that it doesn't do that; in Haskell your functions are actually functions and I/O operations are very clearly not functions.
> That's a pretty big "except" - there are no side effects except for all the side effects (and there's nothing unique about JavaScript there, that much is the same as almost any other language)
It's not like Haskell doesn't have those either though, I don't think it's a very big except. Discussing synchronous I/O in JavaScript is not interesting, were not littering our Haskell with unsafePerformIO either.
> JavaScript's approach to I/O, like most languages, uses things that look like functions but aren't functions, in that they give different outputs for the same inputs.
No, this is just not true, are we using the same JavaScript? JavaScript's functions change only based on modified application state, not on any other side effect.
> The whole point of Haskell's I/O system, the thing that separates it from other languages, is that it doesn't do that; in Haskell your functions are actually functions and I/O operations are very clearly not functions.
Sure, in the current Haskell that's true. In previous iterations of Haskell this wasn't always the case though, monadic I/O wasn't the first pure system, we also had stream based and continuation/callback based I/O, the latter being basically what JavaScript does.
> No, this is just not true, are we using the same JavaScript? JavaScript's functions change only based on modified application state, not on any other side effect.
If you read some file (or remote URL) multiple times, you may get different data each time. Haskell makes "functions" with this property clearly distinct from regular functions. Most languages, including JavaScript, don't. That's what matters, not whether I/O is synchronous or not.
> Sure, in the current Haskell that's true. In previous iterations of Haskell this wasn't always the case though
That may or may not be technically true but it's not really informative or relevant - Haskell has had monadic I/O for over 20 years and the overwhelming majority of Haskell users have never used any other kind.
Well, either it's impossible to read a file (or remote URL) in JavaScript, or the data gets into your program somehow. Whether you get it as a plain value, a promise, or a callback is not really relevant; it comes into your program looking like a normal, idiomatic function evaluation (because passing callbacks to normal functions like Array.map is perfectly idiomatic JavaScript). There is no practical way to separate a JavaScript program into fragments that depend on external mutable state (files, remote services) and fragments that don't, because a function that accesses and depends on external mutable state (say, a calculation that uses a lookup table that it loads from a file) looks the same, at API level, as one that doesn't.
Well that's true. I do think there's some value to the fact that if you call a JavaScript function you are guaranteed that no I/O has been executed (provided no on is using the old sync API's) before the function returned. I lean on this property often, and I don't know any other language besides Haskell that has this property.
I do agree that Haskell is even stronger because it doesn't just guarantee the I/O has not yet been executed yet, it also reveals the intent of I/O through the use of the I/O monad.
> I do think there's some value to the fact that if you call a JavaScript function you are guaranteed that no I/O has been executed (provided no on is using the old sync API's) before the function returned. I lean on this property often, and I don't know any other language besides Haskell that has this property.
Are you just talking about the absence of shared-memory threading (which you also get in, say, OCaml, or even Erlang or idiomatic Python)? I can understand the value of not having to reason about arbitrarily interleaved executions, but not how that particular kind of sequencing of I/O specifically is more useful than that.
What do you mean "the function"? One can certainly write functions in JavaScript that return the result of an HTTP request, and that result can change each time the function is run. In Haskell you can't do that.
Sure it's possible, you can use unsafePerformIO just fine in Haskell. It's idiomatic to not use it, just like it's idiomatic to not use synchronous I/O in JavaScript. Imo it's also not really interesting to talk about non idiomatic use of a language but I guess we disagree there.
It seems to me that there is a qualitative difference between having synchronous HTTP requests in the JavaScript standard library and having access to System.IO.Unsafe.unsafePerformIO in Haskell. Still, I take your point that in theory JavaScript could remove all synchronous I/O side effecting functions and replace them with continuation-based ones.
Anyway, we've wandered pretty far off the main thread, which wasn't mine to begin with, so I'll let lmm take up the discussion again if he wants.
What's state without mutation? If something is immutable then you can't tell the difference between a value and a copy of that value, so the question of whether it's "state" is rather meaningless.
I think you can define it. You just need to be willing to pin down some definitions so there's something you can formally talk about.
For example, let's say an "program" (in whatever abstract sense, whether you want to represent it as DAGs of function compositions or as a sequence of instructions or whatever else) takes, by definition, an infinite sequence of input symbols, and produces an infinite sequence of output symbols. Both sequences start (WLOG) at index 0. Note that for finite sequences, you can represent them by appending an infinite number of symbols that you consider null.
Let's say that "running" the program "until step k" (in whatever abstract sense you want to define, whether it's evaluating functions or following a sequence of operations or whatever) corresponds to "producing all outputs up to index <= k". The "state" of that program at step k might then be defined as the amount of information (measured in bits or whatever) that that particular program requires for eventually producing outputs at indices > k, aside from the information needed to represent the program itself.
As long as you formally define a way to measure information and a way to represent your program, I think you should be able to come up with a definition as I did above to define "program state" formally. You just need to be willing to do that, is all.
I don't think that captures the aspects people care about most of the "program state" that people care about is unrelated to I/O - particularly in Haskell, people care about programs that are essentially "evaluate this large equation" where there's only one piece of output at the end, but might be a lot of intermediate computation. And the details of what's stored in memory aren't what matters - after all, Haskell very deliberately makes no distinction between a plain value like 3 and a large and complicated thunk that will eventually evaluate to that value - but if you just measure the minimum number of bits required to store something equivalent then you've assumed away the whole evaluation of the program.
At least from the functional perspective you're coming at this from the wrong end in the first place - you're looking at it operationally rather than denotationally. The point of saying that there's "no state" or "no mutation" in a functional program is that there is no such concept at the semantic, code level: when reading any given piece of code, you don't need to think about state to understand what it's doing.
You're muddying the waters here. If you're saying "I/we don't care about a notion of state in Haskell", that's fine; I can't force you to care about something you don't care about. I'm just saying if you did care to, you very well could find a pretty meaningful and useful definition for "state".
The thing is though, the fact that you don't doesn't imply state is meaningless or useless. After all, you're still going to face the fundamental limits on computation that are out there, regardless of the model of computation. It's not like switching to Haskell and beta-reductions suddenly lets you solve every problem instantaneously, right? You're still going to have just as hard of a time (if not harder!) solving a problem like TSP efficiently in Haskell, as you would in Python or Prolog.
Look at it this way: the only reason you wouldn't "care" about state would be that you already know how things are going to turn out, not because the whole notion is itself meaningless. If tomorrow you wrote a Haskell program that factored integers in time & space linear to the input size, you wouldn't toss it into the trash thinking "whatever, time and space are meaningless concepts in FP". You'd absolutely care. Not only would you care, but you'd safely assume everyone else would too. You'd either find a way to profit off those results, or you'd publish them with formal definitions and tell everyone and their grandmother how awesome and meaningful they are. You'd find them as far from meaningless as anything could be. Of course, you're probably not going to get that lucky, but your lack of luck or care for the concepts doesn't render the concepts themselves meaningless.
> I'm just saying if you did care to, you very well could find a pretty meaningful and useful definition for "state".
I'm not at all convinced. The thing that actually determines the performance of real-word programs these days (after algorithm choice) is cache efficiency, and no mainstream programming model gives you a "state" model that actually lets you reason about that.
> Look at it this way: the only reason you wouldn't "care" about state would be because you already know how things are going to turn out, not because the whole notion is itself meaningless. If tomorrow you wrote a Haskell program that factored integers in time & space linear to the input size, you wouldn't toss it into the trash thinking "whatever, time and space are meaningless concepts in FP". You'd absolutely care. Not only would you care, but you'd safely assume everyone else would too. You'd either find a way to profit off those results, or you'd publish them and tell everyone and their grandmother how awesome and meaningful they are. You'd find them as far from meaningless as anything could be. Of course, you're probably not going to get that lucky, but your lack of luck or care for the concepts doesn't render the concepts themselves meaningless.
Today's programmers put way too much focus on performance given that we as an industry haven't even mastered producing the correct output for any given input. Do I care about how much memory my program will use at runtime? Sure, at some level. Is it something I want front-and-centre in my programming language? No; language features that help me write correct programs are a higher priority.
> The thing that actually determines the performance of real-word programs these days (after algorithm choice) is cache efficiency
> Today's programmers put way too much focus on performance
So statefulness is a meaningless concept in functional programming because... programmers put too much focus on performance? and cache efficiency is what matters?
Is there a logical chain of implications I'm missing here? I feel like we're not even in the same conversation at this point.
Well, I got lost trying to follow you. My position is: Functional programming more or less means expressing (denotational) computation without using a concept of (hidden, mutable) state. This is a good approach because it makes it easier to write correct programs. I disagree with the argument that a programming language should expose state at the language level (rather than making it a detail of the implementation) for the sake of performance on two levels: performance is less important than correctness, so it's a bad idea to sacrifice correctness for performance in language design, but also exposed state doesn't even help you improve performance (because cache efficiency is what matters).
Agree. Too often descriptions of monads assume that the reader has no formal math training whatsoever and do a lot of handwaving, diagrams, examples, etc. without actually providing a useful definition. This post is the exact opposite.
The closest I’ve come to understanding monads is the Wikipedia page on them (in the functional programming context, there’s also a separate monad page in the context of category theory specifically which is a lot more jargon heavy)
There’s a few gaps in this explanation that my deductive completionist brain is looking for.
Namely, I’m wondering what kind of thing is even capable of being a monoid and an endofunctor at the same time. Mathematically, a monoid is a set (or collection to be more general) closed under a binary operator (the monoidal product) and with a distinguished identity element. An endofunctor is a mapping from a category to itself, which entails a mapping of each object as well as a mapping of each morphism. So I’m not even sure how to parse the phrase “monoid in the category of endofunctors” because the data required to describe these two things seems completely different.
The categorical definition of a monoid is different than the usual algebraic one (although one can be recovered from the other) and usually treats a monoid as a single object (hence "mono-").
In particular, usually a monoid is defined as a single object category (sometimes a "monoid object" is defined inside a category, but that's a different presentation). The usual multiple objects of an algebraic monoid correspond to different arrows/morphisms within a monoid.
So for example, while the usual algebraic presentation of a monoid would say the integers form a monoid with an identity element `zero` and normal integer addition forming the monoidal operator, the categorical definition says instead that the monoid is the category that consists of only one element Unit and the morphisms (x => x + 0), (x => x + 1), (x => x + 2), etc. We have an identity morphism (x => x + 0), which when composed with any other morphism does not change it (x => x + 2 composed with x => x + 0 still is just x => x + 2). This is a common pattern in category theory: everything is reduced to composition.
So that's a categorical monoid, just a single object with a lot of morphisms and an identity morphism. We can back out the usual algebraic definition by associating with each morphism the "element within" (i.e. associating (x => x + c) with c), but it represents a different way of thinking.
We can also talk about a monoid object in a larger category in much the same way.
Hence now that we can talk of a monoid as a single object, we can then say that an endofunctor is a monoid (given the proper mappings on an endofunctor, i.e. natural transformations).
> We can also talk about a monoid object in a larger category in much the same way.
Indeed that is one way of viewing a monoid. However, the most basic categorical definition of a monoid (and the first one usually introduced in a category theory textbook) views it as a category with only one object, where all the "interesting stuff" happens with the morphisms. A monoidal category and monoid objects are a restatement of that idea in a larger category.
You're right, there's a missing step. By "a monoid M in the category C" we mean that M is an object in C along with two morphisms "unit" : 1 -> M and "multiplication" : M x M -> M satisfying the "monoid laws" translated to C. (And really C should be a so-called "monoidal category".) When C = Set, this gives the usual notion of a monoid, which classically is a set by definition, as you say. However there are lots of interesting monoid objects in other categories!
The trick is that it is not a monoid AND and endofunctor but of monoid OF endofunctors. The whole "monads are monoids in the category of endofunctors" was a joke because it is a needlessly complex way of describing what a monad is.
I've always found the definition of monoid objects in a category of endofunctors to be tougher to grasp than the Kleisli-category definition of a monad, at least if one is being formal about "monoid object", and checking that the necessary diagrams commute.
Given a functor m of Hask, we define a squiggly arrow ~>, where a ~> b is a -> m b. If these ~> are the arrows in some category (which we call the Kleisli category for m), then we call m a monad. Here id :: a ~> a in that category is what we call return :: a -> m a, and the composition (.) :: (b ~> c) -> (a ~> b) -> (a ~> c) in that category is used to create bind :: m a -> (a -> m b) -> m b, where bind x f = (.) f (const x) (return ()), where (.) is the squiggly arrow (.) we just mentioned. Bind is what's spelled >>= in Haskell, and is what's behind the "x <- f" do-notation.
I don't know if you mean that you are an outsider to HN or an outsider to functional programming.
The problem in this thread is not that monads are controversial or poorly understood. The problem is that there is a strong selection effect: the thread is populated by people for whom the topic of monads is relatively new, and who think that this discussion is worth having in this context. People who are "productive" with monads already know exactly what the structure is (it's not complicated) and they're unlikely to want to enter this discussion. They just have better things to do than engage with the misconceptions of "learners" on the Internet.
HN in general suffers from posters who write confidently about things they don't fully understand. This tends to drive genuinely competent people away from the site. It affects politics as well as tech discussions.
The problem isn't monads, it's the denizens of HN.
Like many, I'm still learning a lot of this - especially the formal terminology and the distinctions between the mathematical and computational variances of these ideas.
It can be tough to push past the more intense and techincal jargon and I enjoy writing about these ideas to document my learnings for myself and to try and make it more accessible to others.
I'm happy some found it useful and for the discussion here where people can help correct and inform parts that aren't as sound.
So we cannot talk about a type being monad without also saying under what function?
E.g. Arrays are monads under concatenation. So why people then say easily "Option type is monad" without stating under which operation? I assume Option is monad under "all" and "any" function, but not sure.
1. A type constructor M of a single argument
2. A function of type a -> M a
3. A function of type M (M a) -> M a
subject to the monad laws. So the 'array monad' is the triple (Array, \x -> [x], Array.concat) and the 'option monad' is the triple (Option, \x -> Some(x), \x -> match x | Some(o) => o; None => None). Saying a type 'is' a monad is imprecise but just means it has an associated monad instance. I've never seen a type with multiple monad instances but I don't know if there could be one.
> I've never seen a type with multiple monad instances but I don't know if there could be one.
There can, it's just like there can two monoid structures on the same set. In fact if you have an example of a set S which has two monoid structures, you have an example of a functor with two monad structures: _ × S. join multiplies the two elements of S, so you get a different monad structure for every monoid structure on S.
Wow that's clearer. I wonder if just a list of examples (and counter-examples) would be enough to explain monads (preferrably with configurable syntax for Haskell-deprived folks).
Btw, I think you got a mistake there, in the third part of Option should be "Some(Some(o)) => Some(o), Some(None) => None, None => None", otherwise o can be not an Option at all.
Yes, but its usually obvious which one is meant, so you don't bother saying under what operation. Option is a monad under the same concatenation as Array, just think of them as arrays that always have length 0 or 1.
Ever use Facebook? WhatsApp? Discord? Telephones? Docker? Amazon EC2? Bought something in a Walmart store or on their websites? etc. etc. Some of their core, critical parts are written in functional programming languages.
Just because you don't see FP out in the wild being conspicuous, doesn't mean it's not there ;-)
- WhatsApp: famous for being written in Erlang, a functional programming language, and processing more messages a day than the entire global SMS network with a team of 50 backend engineers
- Discord: handling extreme amounts of chat/call traffic using Elixir, another functional programming language based on the same tech as Erlang
- Telephones: telephone switches from Ericsson (and in fact, internet switches from Cisco) use Erlang
- Docker: core virtualization component for macOS (hyperkit) written in OCaml
- Amazon EC2: another core virtualization component of all computes, parts of the Xen hypervisor, written in OCaml
Well... chances are you've made thousands of phone calls through switches running Erlang. You may have used Emacs, Discord, Facebook, Pinterest, Spotify, Font Awesome, xmonad or visited web sites running Elm or an Elixir backend... or even driven a Volvo.
Here's a list of companies using Haskell, with similar links to other functional languages: https://github.com/erkmos/haskell-companies. It includes names like Facebook, Tesla, Klarna, Target and Kaspersky.
Not to mention the FP paradigms used in Python, C++ and other languages. In fact, if you've never come across FP "in the wild doing something" then I suspect you're living very much off-grid.
I don't agree that a transformation which takes an int[] and outputs a string[] is an endofunctor. Yes they are both arrays, but they are different types.
Since when did writing words then defining those same words become a big deal? And doing it wrong? Let's not confuse jargon with understanding or getting things done.
Language evolves, as the wiki article you linked describes. Your prescriptivist nit-picking doesn't contribute to the discussion.
From the HN guidelines:
- Please respond to the strongest plausible interpretation of what someone says, not a weaker one that's easier to criticize. Assume good faith.
- Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something.
- Eschew flamebait. Avoid unrelated controversies and generic tangents.
It makes no sense at all to try to explain that stuff in a language lacking higher kinded types. All you can do there (without awkward encodings) is creating instances of those abstractions. You can't create the abstraction as such!
A quite straight-forward explanation of the "monoid in the category of endofunctors" thing can be found here:
https://blog.rockthejvm.com/monads-are-monoids-in-the-catego...
Even the linked explanation is a "quite 'simple' one for that topic" it's still way more involved than what was shown in the article we're discussing here. That Scala stuff is actually correct, this one here isn't even close.
Sorry for the quite negative comment but imho there isn't anything else to add. Before writing a blog post about something one should get at least some basics. Things like: I need HKTs to express functors and such…
As I didn't see the given link here I think my comment makes a useful contribution even it doesn't bring anything else to the table; besides some rage about "very wrongly explained math". :-)