14

For the function monad I find that (<*>) and (>>=)/(=<<) have two strikingly similar types. In particular, (=<<) makes the similarity more apparent:

(<*>) :: (r -> a -> b) -> (r -> a) -> (r -> b)
(=<<) :: (a -> r -> b) -> (r -> a) -> (r -> b)

So it's like both (<*>) and (>>=)/(=<<) take a binary function and a unary function, and constrain one of the two arguments of the former to be determined from the other one, via the latter. After all, we know that for the function applicative/monad,

f <*> g = \x -> f x (g x)
f =<< g = \x -> f (g x) x

And they look so strikingly similar (or symmetric, if you want), that I can't help but think of the question in the title.

As regards monads being "more powerful" than applicative functors, in the hardcopy of LYAH's For a Few Monads More chapter, the following is stated:

[…] join cannot be implemented by just using the functions that functors and applicatives provide.

i.e. join can't be implemented in terms of (<*>), pure, and fmap.

But what about the function applicative/mondad I mentioned above?

I know that join === (>>= id), and that for the function monad that boils down to \f x -> f x x, i.e. a binary function is made unary by feeding the one argument of the latter as both arguments of the former.

Can I express it in terms of (<*>)? Well, actually I think I can: isn't flip ($) <*> f === join f correct? Isn't flip ($) <*> f an implementation of join which does without (>>=)/(=<<) and return?

However, thinking about the list applicative/monad, I can express join without explicitly using (=<<)/(>>=) and return (and not even (<*>), fwiw): join = concat; so probably also the implementation join f = flip ($) <*> f is kind of a trick that doesn't really show if I'm relying just on Applicative or also on Monad.

Enlico
  • 23,259
  • 6
  • 48
  • 102
  • Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackoverflow.com/rooms/233507/discussion-on-question-by-enlico-does-the-function-monad-really-offer-something). – Machavity Jun 08 '21 at 12:34

2 Answers2

21

When you implement join like that, you're using knowledge of the function type beyond what Applicative gives you. This knowledge is encoded in the use of ($). That's the "application" operator, which is the core of what a function even is. Same thing happens with your list example: you're using concat, which is based on knowledge of the nature of lists.

In general, if you can use the knowledge of a particular monad, you can express computations of any power. For example, with Maybe you can just match on its constructors and express anything that way. When LYAH says that monad is more powerful than applicative, it means "as abstractions", not applied to any particular monad.

Fyodor Soikin
  • 78,590
  • 9
  • 125
  • 172
  • Fyodor, where would you say the knowledge of the function type is encoded in Will Ness' answer? – Enlico May 31 '21 at 22:32
  • 7
    @Enlico `id` is a function. `(<*> id)` is not a polymorphic function that can be used with any applicative. Similarly, only for functions `(>>= id)` and `(id >>=)` are the same. – Bergi May 31 '21 at 22:34
  • @Bergi `id` here is akin to lists' `[]`, not `concat`. that it works is precisely what it means that for functions app. and mon. have same power. otherwise, what are we saying, that in general Monad has more power than App? of course it has, but that wasn't the question. if you could express `join` for lists with `<*>` and `[]`, I'd say it'd mean they have the same power there as well. – Will Ness Jun 01 '21 at 13:54
  • "In general, if you can use the knowledge of a particular monad" you mean "a particular data type". like you suggest using pattern matching. there's no pattern matching on Monad as Monad, only on a data type. as Monad, it knows only `>>=` and `return`. – Will Ness Jun 01 '21 at 14:26
  • That's how it's usually said. You can say "the maybe monad" or "the list monad" or "the state monad". – Fyodor Soikin Jun 01 '21 at 15:28
  • yes it is, and that is unfortunate. :) I mean, when we say "the maybe monad" we have in mind the particulars of how Maybe implements Monad, and that is fine. but here, in this context, it is confusing. – Will Ness Jun 01 '21 at 15:36
  • @WillNess I didn't mean to compare `id` to `concat` – Bergi Jun 01 '21 at 16:50
  • Unaccepted for now as I'm still not sure. On one hand, this answer perfectly tells why I can make without `>>=`, `<*>`, or any other abstraction from the moment I know what the actual data type is. But on the other hand, it doesn't explicitly answer the question in the title. Besides, I start to see Will Ness' point and want some time to think more about it. – Enlico Jun 01 '21 at 19:49
  • @Enlico I just repeated in my answer what I thought was a long accepted uncontroversial part of Haskell lore. I even think I saw it stated here on SO somewhere. – Will Ness Jun 02 '21 at 14:49
  • @FyodorSoikin just so I can understand, is your answer saying that functions Monad _is_ more powerful than Applicative? – Will Ness Jun 02 '21 at 15:30
  • 1
    @WillNess He's saying that the *particular* monad, functions, has the whole power of functions. And so does this particular applicative. – Bergi Jun 02 '21 at 17:01
  • @Bergi I see what's going on now. by "functions" you mean "any pointful definition I can write in Haskell" and I indeed meant combinators, without realizing it. my argument boils down to `W = CSI`, where `S` is unavoidable. (or there are probably ways to express `S` with `W`). in any case it's SK that's the basis. – Will Ness Jun 03 '21 at 12:13
  • ( Wfx=CSIfx=SfIx=fx(Ix)=fxx. ) using pointful notation reveals nothing illuminating. lambda calculus _is_ turing complete (or something). using combinatory notation reveals additional structure. (and, yes, [`S = B(BW)(BBC)`](https://en.wikipedia.org/wiki/B,_C,_K,_W_system)) – Will Ness Jun 03 '21 at 12:24
1

edit2: The problem with the question is that it is vague. It uses a notion ("more powerful") that is not defined at all and leaves the reader guessing as to its meaning. Thus we can only get meaningless answers. Of course anything can be coded while using all arsenal of Haskell at our disposal. This is a vacuous statement. And it wasn't the question.

The cleared-up question, as far as I can see, is: using the methods from Monad / Applicative / Functor respectively as primitives, without using explicit pattern matching at all, is the class of computations that can be thus expressed strictly larger for one or the other set of primitives in use. Now this can be meaningfully answered.

Functions are opaque though. No pattern matching is present anyway. Without restricting what we can use, again there's no meaning to the question. The restriction then becomes, the explicit use of named arguments, the pointful style of programming, so that we only allow ourselves to code in combinatory style.

So then, for lists, with fmap and app (<*>) only, there's so much computations we can express, and adding join to our arsenal does make that larger. Not so with functions. join = W = CSI = flip app id. The end.

Having implemented app f g x = (f x) (g x) = id (f x) (g x) :: (->) r (a->b) -> (->) r a -> (->) r b, I already have flip app id :: (->) r (r->b) -> (->) r b, I might as well call it join since the type fits. It already exists whether I wrote it or not. On the other hand, from app fs xs :: [] (a->b) -> [] a -> [] b, I can't seem to get [] ([] b) -> [] b. Both ->s in (->) r (a->b) are the same; functions are special.

(BTW, I don't see at the moment how to code the lists' app explicitly without actually coding up join as well. Using list comprehensions is equivalent to using concat; and concat is not implementation of join, it is join).

join f = f <*> id

is simple enough so there's no doubts.

(edit: well, apparently there were still doubts).

(=<<) = (<*>) . flip for functions. that's it. that's what it means that for functions Monad and Applicative Functor are the same. flip is a generally applicable combinator. concat isn't. There's a certain conflation there, with functions, sure. But there's no specific functions-manipulating function there (like concat is a specific lists-manipulating function), or anywhere, because functions are opaque.

Seen as a particular data type, it can be subjected to pattern matching. As a Monad though it only knows about >>= and return. concat does use pattern matching to do its work. id does not.

id here is akin to lists' [], not concat. That it works is precisely what it means that functions seen as Applicative Functor or Monad are the same. Of course in general Monad has more power than Applicative, but that wasn't the question. If you could express join for lists with <*> and [], I'd say it'd mean they have the same power for lists as well.

In (=<<) = (<*>) . flip, both flip and (.) do nothing to the functions they get applied to. So they have no knowledge of those functions' internals. Like, foo = foldr (\x acc -> x+1) 0 will happen to correctly calculate the length of the argument list if that list were e.g. [1,2]. Saying this, building on this, is using some internal knowledge of the function foo (same as concat using internal knowledge of its argument lists, through pattern matching). But just using basic combinators like flip and (.) etc., isn't.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • I start to see your point, Will. I've also added the combinatory-logic tag, as it's mostly relevant based on your answer. – Enlico Jun 01 '21 at 19:50
  • 2
    I don't understand. Both `id` and `flip` are specific to functions, and not part of the `Applicative` interface. (Well, `id` actually works for general `Category`s, but it's still not part of `Applicative`.) – dfeuer Jun 01 '21 at 20:19
  • @dfeuer I think the heart of Will's answer is "_id here is akin to lists' [], not concat_", that is if you can combine `<*>` with `[]` to get `join`, than you would have an equivalent proof that applicative and monad are the same for the list instances. –  Jun 01 '21 at 21:22
  • @dfeuer for functions, `join = (id =<<) = (<*> id)`. if `id` is allowed on the left, why shouldn't it be allowed on the right? sure it only works for functions, but that just means that for functions, it works. the true power of monad vs applicative with functions is argument replication (`join f x = f x x`) (and app already has it, `app f g x = (f x) (g x)`, so `join f x = app f id x`... (I didn't think treating `id` as a primitive would be controversial)). the true power of monad vs applicative for lists is nested pattern matching (`join ((x:xs):ys) = x : join (xs:ys)`). – Will Ness Jun 02 '21 at 14:35
  • ... and apparently we can't use `app` as a primitive, to achieve _that_. – Will Ness Jun 02 '21 at 14:45
  • (by "can't" I meant unable to achieve that using just app as a primitive) @dfeuer – Will Ness Jun 02 '21 at 15:58
  • @dfeuer could you help me out please, do you read Fyodor's answer as saying that functions monad is more powerful than applicative? do _you_ think that it is? – Will Ness Jun 02 '21 at 16:00
  • 1
    @WillNess As you already mentioned (if I understand you correctly) functions have a dual role: Considered as a data type they form a monad. But they are also the means to encode the monad operations for all instances. However, as I see it now one cannot deduce from this duality that the function type per se is special. `flip` may be more polymorphic than `concat` but it still uses knowledge of the function arrow `->`. `concat` uses pattern matching as the elemination rule of `[]`. But `flip` uses function application as the elimination rule of `->`. Does this make any sense? –  Jun 02 '21 at 21:44
  • @IvenMarquardt `concat` deconstructs its argument by pattern matching. `flip` does no such thing. there is no data constructor `->` to do the elimination of. having implemented `app f g x = (f x) (g x) = id (f x) (g x) :: (->) r (a->b) -> (->) r a -> (->) r b`, I already have `flip app id :: (->) r (r->b) -> (->) r b`, I might as well call it `join` since the type fits. It already exists whether I wrote it or not. OTOH, from `app fs xs :: [] (a->b) -> [] a -> [] b`, I can't seem to get `[] ([] b) -> [] b`. both `->`s in `(->) r (a->b)` are the same; functions _are_ special. that's all I know. – Will Ness Jun 03 '21 at 11:46
  • @IvenMarquardt (I haven't said nothing new, mind you. see also [this comment](https://stackoverflow.com/questions/67779824/does-the-function-monad-really-offer-something-more-than-the-function-applicativ/67780815#comment119876611_67780815) here). – Will Ness Jun 03 '21 at 13:24
  • @WillNess So adding `join` doesn't make a difference for the function type and that makes functions special. I still don't understand the combinatory logic part but that is on me. I wish there was a broader debate on this issue, but there isn't and it's probably too much to ask. –  Jun 03 '21 at 20:34
  • @dfeuer if I may address you here one more time, I really don't understand the objection(s). the Applicative interface is all of two functions; if we could cook up a `join` from the two of them, and only the two of them, that would prove Monad = Applicative _in general_. why would that be even considered? otherwise, I've edited my answer with more stuff (and left more comments around here trying to clarify what I meant), I don't know if you saw it; perhaps it addresses some of the concerns? I must say I'm baffled by this whole thing here. – Will Ness Jun 08 '21 at 14:54
  • @WillNess, the claim is really true for `Proxy`. `Proxy >>= f = Proxy = Proxy <*> Proxy`. It also seems likely true in some categorical sense for `Identity`, thanks to its `pure` being an isomorphism. `x >>= f = f (runIdentity x) = runIdentity (f <$> x)`. For functions, I just don't see the claim being meaningful. – dfeuer Jun 08 '21 at 15:37
  • @dfeuer well I finally googled it, and got e.g. [this](https://stackoverflow.com/questions/55797418/what-can-the-reader-monad-do-that-applicative-functions-cannot#comment98264475_55797418) (and a supportive comment from luqui few lines down). – Will Ness Jun 08 '21 at 15:43
  • 1
    Ah, now I might see. `flip` here is seen as `curry . (. swap) . uncurry`? – dfeuer Jun 08 '21 at 15:50
  • @dfeuer for me, `flip` is **C**. it's primitive. but yes, I guess. – Will Ness Jun 08 '21 at 15:51
  • 1
    @dfeuer or maybe you were stressing the fact that **Hask** is CCC and functions are both its morphisms and exponentials. (the problem with me saying this is that I personally barely understand the words I'm using there, that's why I didn't say it in the answer) – Will Ness Jun 08 '21 at 16:09