Functors, Applicatives, and Monads in Plain English

http://www.russbishop.net/monoids-monads-and-functors

by maxdesiatov • 10 years ago

136 62 10 years ago

I've found that trying to simplify things is an impossible thing to do in the programming community (cue to "You're missing the point / You're oversimplifying / This is not what a monad is").

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.

striking2• 10 years ago

I was going to be one of the people who complained about this post's shortcomings, but of course that's because I learned Haskell rather than Swift, and so the implications of monads et al. are a teensy bit different.

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.

jerf• 10 years ago

I agree, with the caveat that if one is going to mock the Haskell community ("A million words of category theory and Haskell examples to say..."), it would be helpful if you don't summarize it incorrectly ("... Functors contain stuff"). There are plenty of Functors in the Haskell sense that are not immediately obviously containers, such as all functions a -> b, which is actually a very commonly-used one. (Of course one could stretch the definition of "container" to include "function" but, well, would that not constitute engaging in the very academic wankery one is simultaneously trying to mock?) So perhaps it is not so mysterious that it takes a bit longer to explain the Haskell uses of the term.

spriggan3• 10 years ago

While Type theory in general is fundamental for people who implement languages (and too often we see the result of the lack of knowledge of type theory in the implementation of main stream languages, and no, I'm not talking about PHP here), most developers just want to get an idea of what all that stuff is about. Most developers will never use functors but Monads have interesting applications, like Futures (i.e. Promises).

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.

oacgnol• 10 years ago

I've also run into this myself in publishing my own blog posts. I had this burning need to add caveats and write very defensibly because the fear in the back of my head of being "well, actually..."d.

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-...

tikhonj• 10 years ago

No. It's a problem because you, the reader, are missing the point.

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.

VeejayRampay3• 10 years ago

You're absolutely right. To be clear, I was not saying that everything can and should be simplified, some things just warrant a certain level of complexity because they're... well... complex and that's absolutely fine (your example of quantum computing is great in that regard, though I supposed it COULD be vulgarized for the masses to some extent, at least more than it currently).

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.

JamilD• 10 years ago

I don't think the issue is with the simplification itself, but with the illusion of complete understanding.

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.

pron2• 10 years ago

Thing is, you're kind of shooting yourself in the foot here, because a programming language concept should better be very different from something like quantum computing. I know next to nothing about quantum computing, but I do know that currently its significance is mostly theoretical. Concepts like functors and monads (in the context of programming) are literally workman's tools. If explaining to a carpenter how to use a new kind of hammer is as subtle and complex as explaining the standard model, then there is something fundamentally wrong with the hammer. If, in addition, carpenters using the new hammer don't seem to be building things significantly faster (or things that are significantly harder to build) than those using the plain-old hammer, I think it's safe to say that the new hammer kind of sucks.

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!

incepted• 10 years ago

Very often, writing a tutorial about monoids, functors, applicatives, or monads ends up improving the understanding of these concepts a lot more for the author of the post than its readers.

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.

catnaroek6• 10 years ago

Some programmers create fuzzy metaphors; others define crisp, crystal clear abstractions.

tome2• 10 years ago

I feel like I've progressed in my understanding of those concepts by reading the post

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

rdsubhas• 10 years ago

Well said. They won't take any effort to share their knowledge, and they won't let others to share in any possible way as well. As you said, they want to remain a savant elite and don't want anybody else to even start anywhere close.

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.

bcherny• 10 years ago

Nice writeup. I also like http://adit.io/posts/2013-04-17-functors,_applicatives,_and_....

kika2• 10 years ago

I don't know category theory, so I defer to more knowledgeable people here, but that sounds strange: "Functor it understands how to take doStuff and execute it on the value inside itself, then spit out a new Optional. You don't lose the int-ness or optional-ness." So if I map a function, that takes an int and returns a string over an array of ints, this array stops being a functor? Or is it just a Swift thing?

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.

VeejayRampay3• 10 years ago

It's a great video, thanks. Watching it thinking the guy is sporting an afro is even better for some reason.

jstimpfle2• 10 years ago

What he was getting at is that you can reuse functions which know nothing about the specific context (like, what container are we mapping over). It's not that you couldn't change the type of thing inside.

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).

evincarofautumn2• 10 years ago

You can actually write the list constructor in prefix form if you like:

    [] a -> [] b

catnaroek6• 10 years ago

this array stops being a functor?

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>

kika2• 10 years ago

this array stops being a functor

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.

draw_down• 10 years ago

I appreciate the use of plain english, but it doesn't help understand why these things are good or important. Like, ok, monads avoid double-containering. That's... nice?

corysama• 10 years ago

The article is about what they are. Not why they are good or important. Tons of material out there is rambling on about them. Apparently a lot of smart people think they are good and important. But, it's rare that someone explains them clearly without putting on a thesis-defense writing style.

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.

danidiaz• 10 years ago

I find Applicatives very useful.

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.

jstimpfle2• 10 years ago

I think he specifically addressed people who know Swift's flatMap. I don't, but here's more if you know a little Haskell.

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 (>>=).

hyperpape2• 10 years ago

You could try "You Could Have Invented Monads" for an explanation of why they're valuable https://blog.jcoglan.com/2011/03/05/translation-from-haskell... (linking to the JS version, which links to the Haskell version).

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".

Tar90• 10 years ago

The link gives a 404 error. Could you post it again?

haldean• 10 years ago

Somehow in the last hour that link died. Here's a page with the same title, but in Haskell: http://blog.sigfpe.com/2006/08/you-could-have-invented-monad...

hyperpape2• 10 years ago

New link: https://blog.jcoglan.com/2011/03/05/translation-from-haskell...

MichaelBurge4• 10 years ago

His 'plain english' descriptions are really just the definition in Haskell. Haskell defines one or two more methods for efficiency, but if you ignore the entries with default implementations you get:

1. "Functors are containers you can call map on. That's it. Seriously."

    class  Functor f  where
      fmap        :: (a -> b) -> f a -> f b

Historically, fmap in Haskell used to be called map. They gave it a different name so that error messages would appear less abstract when working with lists.

    fmap (+2) [5] = [7]

2. "you may want to have a function in the container and apply it to value(s) in another container of the same kind. "

    class Functor f => Applicative f where
      -- | Lift a value.
      pure :: a -> f a

      -- | Sequential application.
      (<*>) :: f (a -> b) -> f a -> f b

So at least in Haskell, he describes the sequential application operator but leaves out the ability to lift a pure value to a container value.

    pure 5 = [5]

    [(+2)] <*> [5] = [7]

3. "Monads are containers you can call flatMap on. Again, that's it."

    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

And here's how to use it like a flatmap:

    [1,2] >>= (\x -> [x + 5, x + 10])
    [6,11,7,12]

That's [1 + 5, 1 + 10, 2 + 5, 2 + 10] if you didn't catch that.

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.

Guvante• 10 years ago

I think the dilemma with Haskell typeclasses isn't the "how", that is fairly straightforward especially for lists and maybe.

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.

catnaroek6• 10 years ago

why type classes have laws.

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.

Buttons840• 10 years ago

What's a monad transformer? I kind of know what a monad is, but what is a transformer? Functional programming sure does use some scary words. I guess OOP has it's fair share as well, with inheritance, subclasses, superclasses (which are much more super than your lowly subclass apparently), etc.

MichaelBurge4• 10 years ago

If a monad is like giving some additional context to a value:

    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"

, then a monad transformer takes an existing monad and augments it with even more context:

    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"

Most monads like State are actually defined as the monad transformer applied to the Identity monad, which has no special context at all:

    State stateType returnType = StateT stateType Identity returnType

Additionally, IO is very common to bury at the bottom of one of these stacks, so there is 'liftIO' to run an IO action in a monad transformer stack. So your web server can just do:

    liftIO $ putStrLn "Hello World"

if you need a quick log message. You need liftIO, because 'putStrLn "Hello World"' is of type IO (), and the web server needs type 'StateT ConnectionPool IO ()'.

Note: IO does more than just databases, of course.

mezuzza• 10 years ago

I like to think of it as a way to combine monads. Two classic examples might be the State monad and the Maybe monad.

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

Both satisfy this use case. I think those two constructions should be equivalent and conceptually equal. Someone should correct me if I'm wrong and there is some actual reason that those are different. To my understanding, the difference is purely due to limitations of the language as opposed to the mathematical constructs.

catnaroek6• 10 years ago

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.

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.

MichaelBurge4• 10 years ago

blaze-html is an example of something implementing the Monad typeclass just to get desugaring. Somebody wrote Lucid for exactly the reason you describe(you can't use things like forM_ with blaze because it blows up).

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.

stevetrewick2• 10 years ago

Not everyone reads Haskell. In fact I'd be willing to bet that only a vanishingly small number of working programmers can fluently read Haskell notation at this point in time. This article in particular is about Swift. One of the barriers to understanding these concepts is that they are often written about as though throwing in a bind operator on a list monad in Haskell makes the author's point blindingly obvious rather than opaque.

wrs2• 10 years ago

Thousands of blog posts later, I don't think the following has changed:

* 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.

_halgari• 10 years ago

Except some of us understand these concepts, see how they can be used, but yet don't understand why we would ever use them.

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.

wrs2• 10 years ago

Presumably you are no longer in the audience for these blog posts. My impression is the number of people like yourself who understand the concepts completely and decide not to use them is vastly outweighed by the number of people who don't understand the concepts, or think they do because they've read a blog post, but because they have no practical experience actually don't.

runT1ME• 10 years ago

mutability increases complexity by 10x. Higher kinded types do not, they're unfamiliar and a bit weird at fist, but end up simplifying things.

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.

colordrops• 10 years ago

When did "Swift" become "Plain English"?

proc0• 10 years ago

As someone who has walked that path, being a complete beginner in functional programming, learning via simple examples, such as the article, and then finally learning (or perhaps beginning to grasp) the basics of category theory, I can say that from my observation there's no substitution to the actual mathematical perspective on the matter.

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.

jeeyoungk• 10 years ago

My favorite on this subject is "Monads are like burritos"

https://byorgey.wordpress.com/2009/01/12/abstraction-intuiti...

draven• 10 years ago

That reminded me of the introduction of the Typeclassopedia ( https://wiki.haskell.org/Typeclassopedia ), which states one must understand the types and gain a good intuition of how the typeclasses relate to each other (and "good intuition comes from hard work, not from learning the right metaphor".)

yummyfajitas2• 10 years ago

Unfortunately, his simple explanation of these concepts is just not correct. He claims functors are a container you can map on and that monads are also containers.

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)
    }

It also supports flatmap:

    p.flatMap(f) = new Prob {
      def draw = f(p.draw).draw
    }

Yet nothing is "contained". Each Prob object is just a random number variable generator.

nandemo• 10 years ago

Right. And function types aren't containers either. So much for "plain English".

yummyfajitas2• 10 years ago

We should just accept that math is a better language for some concepts and try to learn it. This idea that everything can and should be dumbed down for the innumerate is anti intellectual.

stevetrewick2• 10 years ago

I've read a ton of such blog posts recently in exploring this subject - seems like the tradition is as soon as you believe you understand the monad you must immediately write a blog post explaining it and pointing out why everyone else's metaphor is too complicated.

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/

http://www.javiersoto.me/post/106875422394

http://chris.eidhof.nl/post/json-parsing-in-swift/

Functors, Applicatives, and Monads in Plain English

Related Stories