6 ms·

(a -> b) -> T a -> T b T (a -> b) -> T a -> T b (a -> T b) -> T a -> T b

by xashor 5y ago

bspammer 5y ago
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” (T a -> T b) -> T a -> T b
- Twisol 5y ago
  > What about this? Is this even possible? > (T a -> b) -> T a -> T b Yep; that's the signature for the "extend" method of a comonad. https://hackage.haskell.org/package/comonad-5.0.8/docs/Control-Comonad.html#v:extend https://hackage.haskell.org/package/comonad-5.0.8/docs/Contr... Though I prefer the presentation with `duplicate :: w a -> w (w a)`, which is just the signature of Monad's `join` but flipped around.
  - WastingMyTime89 5y ago
    > (T a -> b) -> T a -> T b That’s just a normal function application followed by return.
    - bradrn 5y ago
      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.
      - WastingMyTime89 5y ago
        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.
        Twisol 5y ago
        > 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.
    - thewakalix 5y ago
      You might as well say that `(a -> T b) -> T a -> T b` is extract followed by normal function application.
      - bradrn 5y ago
        Huh, interesting how we came up with nearly identical comments at the same time! (Though I somehow managed to get the function name wrong…)
    - Twisol 5y ago
      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.
Twisol 5y ago
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".)
- Zababa 5y ago
 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"?
 - Twisol 5y ago
 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` 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` 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) -> 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.
tsimionescu 5y ago
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 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.
- Twisol 5y ago
 > 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> { List<A> map(Function<A, B> f) { ... } <B, C> List<C> map2(List other, BiFunction<A, B, C> f) { ... } List flatMap(Function<A, List> f) { ... } // bonus; note that these make more sense static static <A, B> List<Pair<A, B>> times(List<A> as, List 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.
 - dunefox 5y ago
rkangel 5y ago
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.
- acchow 5y ago
  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.
- Zababa 5y ago
  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.
  - Twisol 5y ago
    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.

(a -> b) -> T a -> T b T (a -> b) -> T a -> T b (a -> T b) -> T a -> T b

by xashor 5y ago

(a -> b) -> T a -> T b T (a -> b) -> T a -> T b (a -> T b) -> T a -> T b

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” (T a -> T b) -> T a -> T b

Twisol 5y ago
> What about this? Is this even possible? > (T a -> b) -> T a -> T b Yep; that's the signature for the "extend" method of a comonad. https://hackage.haskell.org/package/comonad-5.0.8/docs/Control-Comonad.html#v:extend https://hackage.haskell.org/package/comonad-5.0.8/docs/Contr... Though I prefer the presentation with `duplicate :: w a -> w (w a)`, which is just the signature of Monad's `join` but flipped around.
- WastingMyTime89 5y ago
  > (T a -> b) -> T a -> T b That’s just a normal function application followed by return.
  - bradrn 5y ago
    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.
    - WastingMyTime89 5y ago
      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.
      - Twisol 5y ago
        > 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.
  - thewakalix 5y ago
    You might as well say that `(a -> T b) -> T a -> T b` is extract followed by normal function application.
    - bradrn 5y ago
      Huh, interesting how we came up with nearly identical comments at the same time! (Though I somehow managed to get the function name wrong…)
  - Twisol 5y ago
    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.

Twisol 5y ago

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

Zababa 5y ago
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"?
- Twisol 5y ago
 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` 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` 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) -> 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.

tsimionescu 5y ago

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

Twisol 5y ago
> 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> { List<A> map(Function<A, B> f) { ... } <B, C> List<C> map2(List other, BiFunction<A, B, C> f) { ... } List flatMap(Function<A, List> f) { ... } // bonus; note that these make more sense static static <A, B> List<Pair<A, B>> times(List<A> as, List 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.
- dunefox 5y ago

rkangel 5y ago

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.

acchow 5y ago
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.
Zababa 5y ago
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.
- Twisol 5y ago
  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.