Does the function monad really offer something more than the function applicative functor? If so, what?

Question

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.

Atwitter

Comments are not for extended discussion; this conversation has been moved to chat. – Tilghman

Answer 1

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.

Highgrade

Fyodor, where would you say the knowledge of the function type is encoded in Will Ness' answer? – Atwitter

@Atwitter 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. – Nova

@Nova 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. – Incinerator

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

That's how it's usually said. You can say "the maybe monad" or "the list monad" or "the state monad". – Highgrade

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

@WillNess I didn't mean to compare id to concat – Nova

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

@Atwitter 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. – Incinerator

@FyodorSoikin just so I can understand, is your answer saying that functions Monad is more powerful than Applicative? – Incinerator

@WillNess He's saying that the particular monad, functions, has the whole power of functions. And so does this particular applicative. – Nova

@Nova 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. – Incinerator

( 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)) – Incinerator

Answer 2

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.

Incinerator

I start to see your point, Will. I've also added the combinatory-logic tag, as it's mostly relevant based on your answer. – Atwitter

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 Categorys, but it's still not part of Applicative.) – Anishaaniso

@Anishaaniso 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. – Destined

@Anishaaniso 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)). – Incinerator

... and apparently we can't use app as a primitive, to achieve that. – Incinerator

(by "can't" I meant unable to achieve that using just app as a primitive) @Anishaaniso – Incinerator

@Anishaaniso 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? – Incinerator

@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? – Destined

@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. – Incinerator

@IvenMarquardt (I haven't said nothing new, mind you. see also this comment here). – Incinerator

@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. – Destined

@Anishaaniso 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. – Incinerator

@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. – Anishaaniso

@Anishaaniso well I finally googled it, and got e.g. this (and a supportive comment from luqui few lines down). – Incinerator

Ah, now I might see. flip here is seen as curry . (. swap) . uncurry? – Anishaaniso

@Anishaaniso for me, flip is C. it's primitive. but yes, I guess. – Incinerator

@Anishaaniso 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) – Incinerator