Functors, Applicatives, and Monads in Plain English
russbishop.net
russbishop.net
It's a problem that stems from being surrounded by millions of people who take disproportionate pride in the belonging to a savant elite. What I always say to people who ask me to describe programmers: "Programmers are people who like to create metaphors, but who like to correct other people's metaphors even more".
That being said, I feel like I've progressed in my understanding of those concepts by reading the post, so thanks to the author.
This is probably all you need to know in terms of Swift.
If you're talking about the actual mathematical theories, or how other languages see it, this is a gross oversimplification. But since we're talking about just Swift it's fine.
Swift lacks that amount of expressiveness. Some people call that level of expressiveness "academic wankery" and some people think it's the best thing ever.
It does sadden me that people think a language is worse or better when it is simply different.
It's easy to understand with this article that the usual notion of type (int32,char*,...) is just a subset of what types actually are. (T) -> T is also a type. And if most developers can remember that, well, that's a good thing.
In the end, I still pushed them out and they made the rounds with positive feedback, but it definitely took way longer to write than I thought. I know that's probably not a very healthy way of going about it, and a big part of it in my opinion has to do with how it's too easy to issue ego-boosting corrections.
[1] http://longcao.org/2015/06/15/easing-into-functional-error-h...
[2] http://longcao.org/2015/07/09/functional-error-accumulation-...
Being against cargo cults does not make you elitist. This characterizes a lot of people, and it's not fair or accurate to blindly ascribe them with malicious motivations.
Think about a different area: people who try to "simplify" quantum computing. What do we get? Mass confusion. The fact that so many people think that quantum computers can solve all NP complete problems by trying every possibility is a real problem, not a consequence of "people who take disproportionate pride..."!
And then people go on an try to build things on top of these ideas and end up creating a mess because they started off on shaky foundations. Then that mess gets enshrined in a popular library, it creates lots of problems for everyone. Then programmers either live with those problems or conclude that the whole functional programming "thing" is delusional and useless.
I was addressing the difficulty I've seen in the programming community of trying to make things more accessible when they actually can and should be.
>> Writers use hedges in the vain hope that it will get them off the hook, or at least allow them to plead guilty to a lesser charge, should a critic ever try to prove them wrong. A classic writer, in contrast, counts on the common sense and ordinary charity of his readers, just as in everyday conversation we know when a speaker means in general or all else being equal. If someone tells you that Liz wants to move out of Seattle because it’s a rainy city, you don’t interpret him as claiming that it rains there 24 hours a day, seven days a week, just because he didn’t qualify his statement with relatively rainy or somewhat rainy. Any adversary who is intellectually unscrupulous enough to give the least charitable reading to an unhedged statement will find an opening to attack the writer in a thicket of hedged ones anyway.
> I love this notion of relying on “the common sense and ordinary charity of readers”. What a wonderful, inspiring idea. I realize I’ve begun writing defensively on the web, putting in hedges and clarifications that really aren’t necessary for a charitable reader. I’ve also taken to toning down any rhetorical flourishes that could be interpreted uncharitably in a way that annoys some people. The result: boring writing stripped of a lot of my own personal style.
You can avoid complexity by ignoring it in the proverbial Dunning-Kruger kind of way - where you don't know what you don't know, but you try to turn your toy misunderstanding of some domain into code anyway.
Or you can avoid it by creating over-systematised technologies that try to barricade "impure" unpredictability behind a big wall of abstraction and insider-only jargon.
They're both defensive moves against the messiness of the real world.
There may be other approaches that trade off accessibility with useful results in other ways.
"If I have to wave my hands and explain it, I would explain it like this. In algebra there are sequences of operations which have proven to be important and effective in one circumstance. Algebraists try to reuse these operations in different contexts in the hopes that what proved effective in one situation will be effective again. By contrast an analyst is likely to form an idiosyncratic mental model of specific problems. Based on that mental model you have intuitions that let you carry out long chains of calculations that are, in principle, obviously going to lead to the right thing. Typically your intuition is correct to within a constant factor, and you're only interested in some sort of limiting behavior so that is fine."
How else is a person supposed to intelligently explore the solution space of a problem other than through some kind of "naive reductionism"?
[1] http://bentilly.blogspot.com/2010/08/analysis-vs-algebra-pre...
There's nothing wrong with making a concept easier to digest, and to introduce a topic to an otherwise uninformed reader, but you have to do so with the clear disclosure that there is always more to it.
Everybody starts somewhere when learning.
You're basically telling carpenters, listen, learning to use the new hammer is quite tricky (it's abstract, complicated shit) but it's going to expand your minds, and in the end, after all the hard work, you'll be building things in a completely different way than you do today (although the final result would be rather similar) -- it's totally worth it!
Sometimes the coddled carpenter has trouble grasping a new (actually, a century old...) concept, throws up arms in bewilderment and frustration, and proclaims the concept "too abstract, too complicated" and therefore unsuitable for all. For example, deciding that the value for pi is just too mind-bendy, and deciding on a nice happy value of "22/7" instead.
Computer programming (and theoretical computer science, quantum computing, type theory, etc.) is fundamentally intertwined with the mathematical laws that describe our known universe. There will always be parts of it that seem esoteric to someone, and I bet you that even developers extremely confident in their world of playdough tools would writhe and gnash teeth when reviewing some of the fundamental elements that make their coziness possible. The most obvious example of this might be the parser for their favorite programming language - it is a very complex subject and the algorithms are formidable.
There appears to have been a massive culture shift (rift?) somewhat recently - from individuals who take pride in understanding and growing what we know and what we can do with computers, to individuals who demoralize, coddle, and impede what we can do with them.
Except that none of this applies to pure functional programming. PFP is an idea -- a very interesting one -- about how to program. It neither uncovers the fundamentals of computer science nor grows what we can do with computers. There is absolutely nothing about monads that is fundamental to computation, and understanding monads does not make us understand computation better.
I could say that there appears to be a "culture shift" in which a very interesting abstraction (computation as a function) has shown some promise but has failed to yield significant results (and certainly not a revolution), and so as a marketing effort, begins to present itself as some kind of a necessary "fundamental mathematical" understanding of computer science, while it is nothing of the sort. It is an interesting reformulation where functions and monads replace the familiar concept of the continuation, and that may or may not lead to significant gains. So far, it has not.
Over-hyping research results is often the norm rather than the exception. What may be unique in this case is that rather than believing that in light of recent research, an amazing breakthrough is right around the corner, some PFP advocates seem to claim that the breakthrough is already here, although they find it hard to support their claim with any evidence. I'd say it's a combination of scientific hype and industry-method hype.
It is as worthy of study as any of the other hundreds of research ideas in CS which hold some promise but aren't yet ready for large-scale industry adoption. It is necessary only for those who are interested in exploring computer science's "theory B", and particularly programming language design (which in itself is an important but not an unusually central sub-discipline of the field).
My skepticism of PFP is specific to PFP -- certainly not to studying any of the many under-explored corners of computer-science. I think that PFP's hype/reality ratio is particularly high -- even by CS standards -- and easily rivals that of machine learning (or "AI" as some call those statistical algorithms). It is not skepticism towards study in general but towards PFP in particular, which has so far overpromised and underdelivered.
> Our coddled carpenter inevitably shrivels up in bewilderment
Requiring carpenters to spend a great deal of time to learn how to work in a completely different way, all to achieve a similar level of productivity shows, IMO, a lack of understanding of what carpenters do. It is a mathematician's duty to look at things from different perspectives out of a sense of curiosity or to fund structure. A carpenter should spend time and effort on new methods only if they increase his or her productivity commensurately. I can tell you that algorithms we require programmers to use and/or understand have a much more significant impact relative to their adoption cost.
If we compare techniques and tools to medical drugs, PFP is barely out of the lab and is very early in its human-trials phase. Treating it as a complete success, and requiring that all practitioners spend a great deal of effort learning it at this point in time, is a grievous misrepresentation of the actual achievements of the idea. It is an interesting idea, it shows some promise, and if you have time and interested in this subject, you should give it a look, that's it.
At the end of the day, not everyone responds the same way to metaphors, so the more tutorials and metaphors on these concepts, the better. One day, you'll stumble upon that one article that makes all things click for you.
You might have progressed but I would guess that you actually haven't, because it was a very poor explanation. How is IO a container? How is State a container? Sure, you can stretch the definition so that container means "Functor" but then you've made a circular definition. Containers are examples of functors. They do not exhaust all possible functors.
EDIT: What yummyfajitas said: https://news.ycombinator.com/item?id=11553828
Just ignore them and their elitist comments, because replying to their comments just invites more elitism, abstractionism, and other insanely high level talk without anything constructive. They will just say its wrong without even explaining why its wrong. If they feel the article is only 90% right, they could very well contribute their 10% back as comments - but no, all they want is to just stop the whole thing.
For good examples, look at comments above and below.
* Explaining these concepts in the abstract results in bafflement as to why anyone would care about these useless abstract concepts.
* Explaining only the concrete instances of these concepts results in missing the point that they are all instances of the same concepts (and that you can write reusable code at that level, which can be a big productivity improvement).
* The only way to understand both at once is to sit down and read/write a bunch of code until you understand both levels. And once you pass that point you get it, but then you hit the above two roadblocks trying to find a shortcut to explain the concepts to someone else.
It reminds me of music theory, where you can bombard someone with all sorts of concepts like scales, modes, chords, etc., but it's all nonsense until they actually play music for a while--then most of it is both understandable and useful.
In all these sort of articles I've never seen something that can't be done simpler with a bit of mutability sprinkled here and there. Sure having something 100% pure is great, but I don't know if I want that if it requires a 10x increase in complexity.
Abstractions make code easer to reason about (Go read about parametricity! really!).
Mutability doesn't even help you from a superficial level for some things. Sure, if you're shoehorning a state monad somewhere, a locally scoped variable might look easier. However, try to fix 'Futures' without monads? It's much much less elegant.
1. "Functors are containers you can call map on. That's it. Seriously."
class Functor f where
fmap :: (a -> b) -> f a -> f b
fmap (+2) [5] = [7]
class Functor f => Applicative f where
-- | Lift a value.
pure :: a -> f a
-- | Sequential application.
(<*>) :: f (a -> b) -> f a -> f b
pure 5 = [5]
[(+2)] <*> [5] = [7]
class Applicative m => Monad m where
-- | Sequentially compose two actions, passing any value produced
-- by the first as an argument to the second.
(>>=) :: forall a b. m a -> (a -> m b) -> m b
[1,2] >>= (\x -> [x + 5, x + 10])
[6,11,7,12]
Usually these also come with some laws to help you reason about the typeclass, but looking purely at the language level it can help to remember that a Functor, Applicative, or Monad are nothing more than a type together with some functions with a certain signature.
I find it's usually more useful for a beginner to just start writing code without all the abstractions. Once they have a pile of code and start to want to clean it up a bit, it's not too hard to start stacking some monad transformers.
Instead it is the "why". Groking lens was probably the first time I truly understood why type classes have laws. Unfortunately no one has found an easy path to figuring that out, it takes a long time to truly understand the mechanics of the type classes and a bit longer still to understand why they are useful.
No idea about other communities, but C++ programmers have understood this for ages. Stepanov put it quite nicely: “Algorithms are defined on algebraic structures.” And algebraic structures are defined by their equational laws.
Maybe a: "Either it's a value or nothing"
[a]: "The value was obtained from a list of possible values"
IO a: "The value was obtained from a database somewhere"
Except ErrorType a: "The value is either an error message or a real value"
ExceptT ErrorType IO a: "this value was obtained from a database somewhere, and also maybe there was an error message"
StateT ConnectionPool IO a: "this web server response value was calculated using a connection obtained from the server's stateful connection pool, and a database connection"
State stateType returnType = StateT stateType Identity returnType
liftIO $ putStrLn "Hello World"
Note: IO does more than just databases, of course.
So let's say you want to create a function that operates on some state and might return a value. These are clearly both monads that you've heard about in Haskell, but how do you use them together? The answer is to use a monad transformer.
StateT is the state monad transformer that takes any other monad and adds state to it. `StateT s m a' is a monad that adds a state of type s to a monad m. So `StateT Int Maybe a' is thing that when given an int which is its state, might return a value.
This particular combination was a little esoteric, so I'm not sure what a great example of this would be. However, you could also think of a situation where you want to have some sort of read-only state (such as flags from the command line) and the ability to write to a log.
In Haskell these are provided by the Reader and Writer monads. But again, you have two separate monads here and in order to actually make use of them, you'll need to combine them somehow. Enter a monad transformer. You can either transform a Writer monad with the ReaderT monad transform or transform a Reader monad with the WriterT transform.
ReaderT r (Writer w) a
OR
WriterT w (Reader r) a
Respecting type class laws isn't optional: The laws are an intrinsic part of the abstraction's definition, so if your instances don't respect them, your code is simply wrong.
In any case, you might argue it isn't a mathematical monad, but it can still be a Haskell monad as long as it implements the typeclass.
I agree it makes the most sense if it implements the laws: Otherwise, it's like calling something a Stack<String> when it really deletes your home directory whenever you peek an element. Technically anything that implements the Stack<> interface is a Stack in the language, but it's not an abstract Stack.
This attitude is unacceptable, because it undermines the meaning of abstractions, on which much of the Haskell ecosystem critically depends. It is also a potential turnoff for those who want to learn Haskell but find the learning curve too steep: "What use is investing so much time and effort learning abstractions that people will routinely break anyway?"
This point might have been made elsewhere, but I think the abstract nature of such concepts discussed in the article, makes it hard for "partial understanding" to be useful. In other words, for a beginner to read the article, and then go and start using the concepts themselves, is very unlikely. Either you learn the existing interface like the Maybe monad, or the Reader monad, and you learn how to invoke its functionality, OR you have a solid grasp of Monads as a concept and how it can be applied in any language, which usually means some understanding of category theory. To JUST know that Monads are containers that return "flattened" containers is useless. In other words, you don't need to understand Monads to use them, and if you want to understand them, then perhaps containers are a bit too bastardizing to give you a full view of how and why they're a useful pattern.
https://byorgey.wordpress.com/2009/01/12/abstraction-intuiti...
And, as always, I urge people spend an hour of their life and get the explanation of all this from someone who knows the math but still able to explain this in plain English: https://www.youtube.com/watch?v=ZhuHCtR3xq8 To the best of my limited knowledge, it's all 100% correct.
A little more formally, if you have a functor F you can take some (a -> b) and make it into an (F a -> F b). For example, if F is [] (List), you get ([a] -> [b]).
So [] adds something (a list "context"), but in a sense you don't lose anything (you can still reuse your (a -> b) which knows nothing about the context). That's the wonderful thing about these formal approaches: composability.
(It's sometimes unfortunate that List has this special syntax).
[] a -> [] b type List = []
List a -> List b type Function = (->)
type On f g a b = f (g a) (g b)
{-# LANGUAGE TypeOperators #-}
(Function `On` List) a b
An individual array, as a runtime object, isn't, never was, and never will be a functor, as the term is used in this discussion. Rather, the functor is the type constructor of arrays itself (to be pedantic: the type constructor and the `map` function). In the grammar of most programming languages, type-level and value-level terms are kept separate, so not even in principle could you conflate a type constructor (a type-level entity) with a runtime object (a value-level entity).
<rant>
This is a very common problem. Most programmers are only used to reasoning about runtime objects, like “lists”, “sockets” and “windows”. Inasmuch as they talk about entities that don't have a runtime manifestation, like “types”, “preconditions” and “invariants”, these words are merely used as shorthand for things they want to say about runtime objects.
Understanding how concepts from abstract algebra and category theory are applied to programming requires a change of mindset: the subject matter is no longer “what happens to this individual object”, but rather “what is the structure common to a large class of objects” and “how can this structure be used as the backbone of our algorithms”. This requires a new vocabulary in which abstract structures (which describe or constrain the representation of runtime objects, but don't have a runtime representation of their own) are first-class entities, so that you can say “the type constructor of immutable arrays is a functor” just as easily as you can already say “this runtime object is an array”.
</rant>
Okay, "the type of this array stops belonging to the typeclass of functors". Better? Peace? :-)
I totally agree with your rant and I'm personally less than half way there myself, but this particular comment was within the context of the original article. I do understand the difference between the type and the value (instance). It's not even very hard for C++ programmers.
Here's a monad (which is also an applicative functor) that isn't a container: probability. The space of probability distributions is a functor which can be mapped. In the sampling representation:
p.map(f) = new Prob {
def draw = f(p.draw)
}
p.flatMap(f) = new Prob {
def draw = f(p.draw).draw
}
Monads avoiding double-containering is nice because you want to be able to use them a lot without finding yourself working with an Optional<Optional<Optional<Optional<Optional<Optional<Optional<Optional<bool>>>>>>>> at the end.
Applicative computations have effects and return a value. They can be combined but only in a restricted way that ensures that the effects of one of the computations do not depend on the value returned by another.
For example, if you read a person's bio and photo from two independent files and combine them into a Person value, that fits the Applicative model.
However, if the path to the photo file were included in the bio file and not known beforehand, that wouldn't fit the Applicative model, because one of the effects (reading the photo) depends on the result value of the other.
So why have this limitation, and why create a separate interface for it?
- For one, Applicatives are more "analyzable" than unrestricted monadic computations. You can identify the separate stages of a computation, collect estimates of required resources, etc.
- Some effects like concurrency, validation, and context-free language parsing fit the Applicative mold very well.
- Combinations of different Applicative effects are themselves applicative. If you have a computation that reads a file and validates the resulting data (a combination of Applicative effects) the combined effect is Applicative and can be combined with other effects of the same type.
Suppose you have a function of type (String -> IO ()). For example, putStrLn. It takes a String and converts it into a real world computation (printing the string) of type (IO ()).
That's nice, but what if the input string is not purely there but only "hidden" in another IO computation? For example, it could come from getLine which has type (IO String).
Now we have some (IO String) and some (String -> IO ()) and would like to compose these, i.e. print out again what was input. But they are not strictly compatible since the left thing is in IO context (i.e., computed at runtime).
Since IO is a functor we can do (fmap putStrLn getLine) which is of type (IO (IO ())) if you do the math. This is a computation which at runtime computes another computation (putStrLn applied to the computed string).
The thing that Monad gives you is to merge layers. In the case of IO, that is to actually execute the dynamically computed computation. Formally, merging (IO (IO ())) to (IO ()). Or for any type a, merging (IO (IO a)) to (IO a).
The merging method is called join and is the cleanest way to explain what makes a monad. However in haskell the Monad instances are unfortunately given by (>>=) which is a more complicated way to define the same thing. There is also join in Haskell but it's defined in terms of (>>=).
But while I liked that tutorial, I think what worked was time. I tried to write Haskell and slowly got a feel for them. After awhile, I started to read JS and Java code and think "oh, another monad".
This one is kind of nice in its succinctness, but that ends up meaning it doesn't explain why I should care or what I would do with my monad once I have grokked it.
I've yet to write my personal "how I grokked my monad and why everyone else is wrong" post, but I suspect that there's probably a sweet spot somewhere between 'monad is simply a monoid in the category of endofunctors' and a 'plain English' translation of the monad laws with no context. Preferably with an explanation of why I would want or need such a thing up front. Preferably without Haskell notation.
That said, such an intro would probably still be pretty hard going, some things are just hard, or at least difficult to understand without context. I said I've been reading lots of these recently, actually I've been reading them for a couple of years, but I've only been understanding them recently because I've bumped into a problem domain for which the solution I was groping for in the dark turned out to be a monad.
Swift wise, I found the following to be very enlightening
http://alisoftware.github.io/swift/2015/10/17/lets-talk-abou...
http://alisoftware.github.io/swift/async/error/2016/02/06/as...
http://khanlou.com/2015/09/what-the-heck-is-a-monad/