I would classify this as a pun, not an explanation.
That said, I prefer a presentation using `times` and `join` rather than `ap` and `bind`:
map :: (a -> b) -> (f a -> f b)
times :: (f a, f b) -> f (a, b)
join :: f (f a) -> f a
Reason being, `ap` and `bind` are just `times` and `join` composed with `map`; it's easier (for me) to think about what `ap` and `bind` bring to the table separately from the behavior of `map`.
`times` lets you take a pair of sources and turn it into a source of pairs. This lets you build pipelines that flow together from multiple sources into a single result; with just `map` you can only assemble a unary pipeline with one source.
`join` lets you take a source of sources and meld the layered structures together into a single source. This lets you create pipelines whose contents dynamically extend the pipeline. Without `join`, you can only construct pipelines whose stages are fixed up-front.
(As a bonus, the presentation with `times` leads to the idea that an "applicative functor" is a monoidal functor. If you don't know what a monoid is, maybe it's a toss-up in terminology, but the term "monoid" is vastly more common than the term "applicative".)
Thank you for that, the explanation about `times` makes a lot of sense. However I can't really understand your explanation for `join`. Do you have any example or longer explanation about "pipelines whose contents dynamically extend the pipeline" and how they are different from "pipelines whose stages are fixed up-front"?
Are you familiar with promises, particularly in the JavaScript ecosystem? A Promise<A> represents a pending interaction; you'll get an A when the interaction has finished, but you don't have an A now. But even while you don't have the A, you can prepare a pipeline now that will process it later.
Promise<_> is a functor because we can write a function `map : (Promise<A>, A -> B) -> Promise<B>` that takes a pipeline stage to run, and promises to run it on the A when it arrives. That stage produces a B, but we don't have it yet, either (since it needs that A). Just having a `Promise<B>` doesn't tell us how many pipeline stages it's built -- the fact that we called `map` isn't evidenced in the type itself -- but we know that there's a fixed number, and that all of the stages have already been given to it. After all, we call `map` in the current timestep; the stages are known long before they get to run.
Promise<_> is a monoidal functor because we can write a function `times : (Promise<A>, Promise<B>) -> Promise<(A, B)>` (but see note^). We don't necessarily have either the A or the B, and the interactions that produce them may not complete at the same time; but eventually we will have both of them, so we can wait until then and pair them together. Because we can wait for two pending interactions at once, we can wait for any number of them at once; think about how to write a function `[Promise<A>] -> Promise<[A]>` using `times`.
With `times`, we're just combining all of the stages in the existing promises together. Unlike `map`, which applies stages sequentially, `times` applies them concurrently -- like a branching series of pipes with Y-bends where `times` is used. With this, a `Promise<A>` still has a fixed number of stages known up-front -- all stages are still provided through `map,` which we still call before we ever have an actual `A` to run them with -- but we also now have a fixed number of forks/branches, where before it was a straight-line series of stages.
Promise<_> is a monad because we can write a function `join : Promise<Promise<A>> -> Promise<A>`. The nested promise means that we need to wait for one pending interaction, and then wait for another pending interaction, before we can get an A. This often happens because we interact sequentially with a backend service; we need to log in before we query the system, so if we try to put together pipeline stages like `(Username, Password) -> Promise<Session>` and `Session -> Promise<SensitiveInfo>`, we'll end up with a `Promise<Promise<SensitiveInfo>>`. This type only lets us make up to two interactions; if we can't get `SensitiveInfo` within two interactions, we simply can't write the program at all.
The `join` function lets us collapse two interactions within a single Promise; and just like `times`, if we can collapse two interactions, we can collapse any number of them. With `join`, a type like `Promise<SensitiveInfo>` may take an arbitrary number of interactions before we finally get the result. However, this is a lot more powerful than you might expect: those inner promises don't exist yet! They will exist, as each interaction completes; but now a single `Promise<A>` includes both the stages we've set now, and any stages that future interactions may generate. We can no longer tell how many stages it will take until the final `A` is computed, nor how many interactions it will take. We'll only know when it actually happens.
(^) Well, we also need a function `pure : A -> Promise<A>`, which lets us pretend we don't have an `A` yet. Or, put differently, it puts an A behind a "no-op" interaction that completes immediately and makes the A available to any downstream stages as soon as it's needed. Something like an echo server.
Only Haskell programmers would consider the type signature a replacement for an explanation. I don't mean to be rude to you personally - this is endemic to the culture of Haskell.
Possibly once you're immersed in the world and up to speed with Haskell type signatures are all you need. Unfortunately for people coming to the language we need more context to fit the pieces together, and the vast majority of documentation I found lacked that context.
The type signature and the laws are all functors, applicative and monads are. It's just that these type signatures happen often "in the wild", so we give them names to make reasoning easier.
To take another example, an iterator could be something like:
next :: T a -> a
hasNext :: T a -> bool
That's all an iterator is. The cool thing is that if you implement next and hasNext for a list, an array, a tree and a graph, you can all use them with the same code. That's what monads, functors and applicatives are.
As for the culture part, I think Rust is the sweet spot. Types are here, but you also have explanations. I personally find explanations without types worse than types without explanations, but ideally you should have both. Of course that's assuming meaningful types.
Strictly speaking, in an immutable world, your iterator only gives you access to the head of your collection.
I think this is a fairly standard functional representation of iterable entities:
next :: T a -> Maybe a
rest :: T a -> Maybe (T a)
We could (and you should) argue that this is correct by intuition, but it's also possible to sketch a proof that these structures all "behave" the same as lists would. We can first combine `next` and `rest` into a single function -- note that we can always interconvert between (next, rest) and step:
step :: T a -> Maybe (a, T a)
This has the form of something called a "co-algebra", which consists of (1) a functor `F`, (2) a type `k`, and (3) and a function `k -> F k`. In this case, `k = T a` and `F = Maybe (a, -)`.
The interesting thing is that the functor `Maybe (a, -)` can have many co-algebras, depending on which type and step function you pick. The type [a] -- that is, picking T to be [] -- gives a particularly special co-algebra, called the "terminal" coalgebra for `Maybe (a, -)`. In short, while any other choice of coalgebra may support additional operations, you can convert any one of them to a list without disturbing a process that only makes use of the nominated `step` function. They're observationally equivalent to lists.
> Strictly speaking, in an immutable world, your iterator only gives you access to the head of your collection.
That's true, but I was talking about iterators in general. My point was that functors, applicative and monads may seem weird and special, but we use the same thing in everyday life. Same thing about the signatures: iterator is that, just a signature, but nobody complains about it.
Your explanation about functional iterators is great, I think it shows really well how iterators are about treating any data structure as if it was the simplest data structure. In a imperative language, it's the array, in a functional language, it's the list.
> The type signature and the laws are all functors, applicative and monads are
Yes, and the parent I was replying to had only provided the type signatures.
Even more than that though, describing what something is is usually not sufficient. You also have to describe why it's useful, or rather what it's for.
This is analogous with comments in code - in well written code you don't need many comments telling you what the code is doing, it's often fairly clear. They're also for convenience not necessity because you can, with enough time, figure out what the code is doing because you have all the information. What are irreplaceable are "why" comments telling you why something is done. E.g. "this prints two newline characters at the end of the document" is inferrable, but "print two newline characters because X program is unreliable unless we end with a blank line" is invaluable.
> Even more than that though, describing what something is is usually not sufficient. You also have to describe why it's useful, or rather what it's for.
The thing is, these things are very abstract. The signature is what they are and why they are useful. A way to think about them is that they were discovered. People wrote a lot of code, saw the same pattern come up over and over again, and named it so they can abstract over it and reason about it.
> This is analogous with comments in code - in well written code you don't need many comments telling you what the code is doing, it's often fairly clear. They're also for convenience not necessity because you can, with enough time, figure out what the code is doing because you have all the information. What are irreplaceable are "why" comments telling you why something is done. E.g. "this prints two newline characters at the end of the document" is inferrable, but "print two newline characters because X program is unreliable unless we end with a blank line" is invaluable.
I agree with you here. The problem is that it's very hard to describe why they are useful if you didn't encounter the problem they solve yourself.
Yes and no, there are tons of folks who are part of the haskell culture who recognize the need for more context (myself included).
But I think GP comment summarized it pretty well, it shows how they all relate to each other in a concise way. If its not enough of an explanation, ok, look for another.
Of course, there are lots of libraries that only have type signatures as documentation. I think most people think that's less than optimal, but the haskell community is much smaller than many others. So what you'll want to do is look for a blog post or something that explains it in more detail.
This is not an explanation. But it's handy to keep up on a post-it not next to your monitor after you already understand the concepts but are still getting comfortable with them.
I'm not an haskel programmer. I barely understand haskell type signatures. But it worked for me. It is not a substitute for an explanation but as a very condensed summary (as in if you forget everything remember at least this) it works great.
I wonder why auto-curried function syntax has become so ubiquitous in explaining this. For anyone coming from a more traditional CS background, it's just extra cognitive overhead in understanding the meat of the argument.
For example,
(a -> b,T a) -> T b
(a -> b,T<a>) -> T<b>
Is just as good in explaining what bind means as the curried version, but more familiar to the vast majority of programmers and CS graduates.
Note: I do understand why auto-currying is extremely useful for doing functional programming, and I have no objections to teaching it. I just don't think it's important for teaching functors, applicatives and monads.
In a separate nit-pick, these three function definitions don't mean much on their own, and there are many pure functions that satisfy them without forming a functor/applicative/monad.
> I wonder why auto-curried function syntax has become so ubiquitous in explaining this.
Probably because Haskell (and related languages) use it.
> For anyone coming from a more traditional CS background, it's just extra cognitive overhead in understanding the meat of the argument
I find that curried function signatures are slightly lower cognitive overhead after a bit of exposure, and while I can see that its the kind of thing that is likely to vary from person to person a bit, I can't see that it's likely to be a big thing either way.
> I wonder why auto-curried function syntax has become so ubiquitous in explaining this.
I think it's primarily because this is the form you use them in in a language like Haskell. Most explanations are exported from Haskell in one way or another, so they're deeply colored by Haskellisms.
It's the same reason why `ap` and `bind` are generally preferred over `times` and `join` -- in Haskell you can even use `f <$> a <*> b`, which is a deeply clever use of infix `fmap` and `ap` that drives a syntactic analogy with regular function application, `f a b`. Try doing that in another language and you'll barf. And do-notation desugars most cleanly into >>=, so that's where Haskell-oriented explanations start from.
If you implement these in Java (which you can, you just can't abstract over T), it looks like this:
class List<A> {
<B> List<A> map(Function<A, B> f) { ... }
<B, C> List<C> map2(List<B> other, BiFunction<A, B, C> f) { ... }
<B> List<B> flatMap(Function<A, List<B>> f) { ... }
// bonus; note that these make more sense static
static <A, B> List<Pair<A, B>> times(List<A> as, List<B> bs) { ... }
// in fact, this one has to be static
static <A> List<A> join(List<List<A>> aas) { ... }
}
That is, the second argument `T a` in the top poster's comment becomes the implicit `this` parameter for instance methods. I find the `static` alternatives often make more syntactic sense in context; just goes to show that one language's norms don't always transfer.
I once had to add logging to a large set of methods in C#, so I thought, well, let's make a function decorator like Python or Haskell, there's no reason it wouldn't work on C#.
Well, it indeed worked perfectly well. But the amount of noise added to satisfy the type checker was larger than reimplementing the log procedure at each place.
I think it's clearer to think of map as a function
(a -> b) -> (f a -> f b)
i.e. one which lifts function application over values of the functor. This is then analagous to the role of `f` for mapping types, and corresponds to the concept of a functor in the category of types. This relationship is harder to see in the tupled version. There's a similar argument for e.g.
That’s a very pretty way to lay it out. I’ve never thought of reversing the order of arguments in the monad before, but it makes sense when you see it next to the others.
What about this? Is this even possible?
(T a -> b) -> T a -> T b
I guess to complete the set you can also add this one which is not very interesting, it’s just “apply the function”
Not at all. There’s sensible implementations which aren’t like that. (You might as well say that (>>=) is just function application proceeded by ‘unwrap’.) My favourite example is cellular automata: if you have a data structure containing a grid along with a position on that grid, then that function signature corresponds precisely to running a cellular automaton on that grid. The idea is that the initial ‘T a -> b’ function is run for every single position, then all the results are combined into a single ‘T b’ grid.
Except of course there is no unwrap in the actual definition while both application and return are sure to be there. It’s not like any of this is relevant anyway. The usual abstractions liked by Haskellers are utterly pointless as this whole discussion nicely demonstrate.
> Except of course there is no unwrap in the actual definition while both application and return are sure to be there.
The actual definition of what? `return` is not part of the Comonad class, while `unwrap` (alternatively called `extract`) is not part of the Monad class. No matter what your preferred way of designing abstractions, it seems a strange complaint to say "feature X is useless with abstraction Y" if you don't have a Y in the first place.
> It’s not like any of this is relevant anyway. The usual abstractions liked by Haskellers are utterly pointless as this whole discussion nicely demonstrate.
Well, okay then.
You may not find value in this way of thinking, but other software developers -- many of whom, yes, ship actual software with actual business value -- find these ideas extremely valuable in organizing their thoughts about the problem domain.
I'm open to sharing that mindset with anyone of a curious mind, but most of us aren't going to shove it down your throat. You're welcome to do what works for you.
The important missing context is that a monad has `(return, bind)`, while a comonad has `(extract, extend)`, and both have their own respective laws letting you reason about combinations of those operations.
You can certainly do what you describe if you have a monad, but since you can't even try to unwrap a value if you don't know what the monad is concretely, you have no way to write a function `T a -> b` that's generic over T. Functions `T a -> b` only really make sense for comonads, which give you the `extract` and `extend` functions as primitive.
That said, I prefer a presentation using `times` and `join` rather than `ap` and `bind`:
Reason being, `ap` and `bind` are just `times` and `join` composed with `map`; it's easier (for me) to think about what `ap` and `bind` bring to the table separately from the behavior of `map`.`times` lets you take a pair of sources and turn it into a source of pairs. This lets you build pipelines that flow together from multiple sources into a single result; with just `map` you can only assemble a unary pipeline with one source.
`join` lets you take a source of sources and meld the layered structures together into a single source. This lets you create pipelines whose contents dynamically extend the pipeline. Without `join`, you can only construct pipelines whose stages are fixed up-front.
(As a bonus, the presentation with `times` leads to the idea that an "applicative functor" is a monoidal functor. If you don't know what a monoid is, maybe it's a toss-up in terminology, but the term "monoid" is vastly more common than the term "applicative".)