if Type is Monad than `ap` from Applicative should be sequential?

[safareli]

In documentation of Control.Monad at section class Applicative m => Monad m where is written: (<*>) = ap and ap is defined like this:

{- | In many situations, the 'liftM' operations can be replaced by uses of
'ap', which promotes function application.
>       return f `ap` x1 `ap` ... `ap` xn
is equivalent to
>       liftMn f x1 x2 ... xn
-}
ap       :: (Monad m) => m (a -> b) -> m a -> m b
ap m1 m2 = do { x1 <- m1; x2 <- m2; return (x1 x2) }
-- Since many Applicative instances define (<*>) = ap, we
-- cannot define ap = (<*>)

In Control.Applicative we read about <*>:

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

To sum up if Monad is also Applicative then <*> should preserve sequentiality. Currently there is no word about this nor in Monad nor in Chain nor in Applicative laws.

So is it intentional?

If this should be stated in laws then here is current state of Future/Task/LazyPromise-es:

• @robotlolita/data.task invalid
• @rpominov/fun-task valid
• @Avaq/Fluture invalid
• ramda/ramda-fantasy#Future invalid
• @safareli/Free invalid? (it delegates .ap to target monad so not quite invalid but sort of invalid)
• fantasyland/fantasy-promises valid

---

I found it out just yesterday on tweet of @jdegoes

[rpominov]

This actually stated in Fantasy Land but a bit indirectly see https://github.com/rpominov/fun-task/issues/28

[rpominov]

Curious what if we just turn derivations into laws? E.g. add a second law for Chain:

u.chain(f => v.map(f)) is equivalent to v.ap(u)

[safareli]

I think that's a good Idea! and maybe also add them to laws/*.js

[SimonRichardson]

Good spot, there was a PR open in fantasy-promises that did talk about this, but that was probably the wrong place to do so.

[safareli]

I have checked PRs and Issues of fl-promises but could not find anything related to it.

One thing to note is that for example Haxl is not fully lawful. I don't know if it's common practice in haskell to partially obey this law.

Some libs might ignore this law but I think we should make it clear that it's also a law and should be obeyed as others.

Currently this are derivations separately from algebras but i think we can move them to algebras like this:

• map may be derived from bimap => BiFunctor
• map may be derived from promap => ProFunctor
• map may be derived from traverse => Traversable
• reduce may be derived from traverse => Traversable
• map may be derived from ap and of => Applicative
• map may be derived from chain and of => Monad
• ap may be derived from chain => Chain

I would try to create PR to address this issue.

[rpominov]

If we convert derivations to laws, I wonder should we do this for all derivations? Maybe some of them shouldn't actually be laws, maybe in Haskell they doesn't correspond to a law etc.?

Btw, was very interesting to know that in Haskell it also not always obeyed, thank you for the link!

[safareli]

@rpominov good point! We should check if all derivations are actually laws in haskell.

[safareli]

I was thinking recently that having law that ap must be derived from chain is essential in haskell because for example:

do 
  action1;
  action2;

is translated to action1 >> action2, and as (>>) = (*>) it's action1 *> action2 which is action1 *> action2 = (id <$ action1) <*> action2 and as applicative instance is used in do, it's essential to preserve sequential nature of monad in applicative instance.

But we don't have do notation in js. also it's it's much practical to not enforce sequentiality for example with Task/Future, and also even haxl is ignoring this law and if you want to sequence actions with haxl you should write: (so that do uses monadic bind)

 do 
  _ <- action1;
  action2;

With that in mind I don't see any reason to make applicative sequential when it can be parallel and more practical. So i think this derivation should not be a law, or should be ignored form in Task/Future. What others think on this?

[jdegoes]

Without the law, it basically means that a program's behavior may change if you change a constraint from Monad to Applicative, or visa versa, even assuming it only uses Applicative functions. More relevant in statically typed programming languages, but still rather unexpected.

Note that a notion of sequentiality is often present for purely Applicative structures, such as Applicative parsing combinators, in which the "left" is parsed before the "right".

Perhaps someone has done work on determining the implications of changing these laws?

[safareli]

actually I was not correct in sequentiality

With that in mind I don't see any reason to make applicative sequential when it can be parallel

Applicative should still be sequential, from left to right or right to left. but in case of Task/Future, it should not wait for first task to be finished in order to fork second (Applicative instance derived from chain forks first one and waits until it's finished and then forks second and so on).

In case of maybe, either and other non lazy monadic structures, if we implement ap by hand it's result should be same as result of derived one, even for IO (as it's synchronous). But when we have async structures like Task/Future than the law is not that useful, as it limits us in making ap more efficient (using concurrency).

Perhaps someone has done work on determining the implications of changing these laws?

I might misunderstood your question but currently only fun-task, fantasy-promise and task in new folktale are lawful.

Without the law, it basically means that a program's behavior may change if you change a constraint from Monad to Applicative, or visa versa, even assuming it only uses Applicative functions

Did not quite understand how program's behavior could change, can you provide example or something.

[jdegoes]

Here's an example:

foo :: forall m. (Applicative m) => m Unit
foo = void $ doA *> doB

foo :: forall m. (Monad m) => m Unit
foo = void $ doA *> doB

One intuitively expects the observable behavior of these two functions to be the same. But that's not what happens if monad is inconsistent with applicative.

By the way, there are two ways to solve your problem: simply add a new type wrapper which is ONLY applicative, and not monadic; OR, add a new function to an applicative called zip (or par), which is similar to ap, but which does not promise consistency with monad.

[safareli]

I have just read this redit thread on Applicative Effects in Free Monads and there was interesting discussion about the law.

So as this question is already discussed, I will close this issue. I have created #188 on moving some derivations into corresponding algebras.

[masaeedu]

@safareli Could you please explain what the conclusion is in general? Is it the case that for any lawful applicative, ap must somehow embed some notion of sequencing as chain does, or is this just a historical artifact of Haskell? As an example, say I have two IOs:

1. io1 :: IO (String -> String): Sequentially, wait five seconds, raise an exception, return x -> x ++ "bar"
2. io2 :: IO (String): Sequentially, wait two seconds, delete foo.txt, return "foo"

Let's say I have main = io1 <*> io2. I understand that the value level manipulation (i.e. the application of x -> x + "bar" to "foo") has to proceed in a particular direction and produce "foobar".

What I'm trying to understand is whether the "contextual" effects must also be sequenced. Is it required of a lawful implementation of <*> for IO that foo.txt will not be deleted if the first IO throws, as would be the case with io1 >>= (\f -> io2 >>= (\x -> return f x))? If IO did not throw an exception, would the operation complete in 5 seconds or 7?

[safareli]

If a structure is a Monad then it's Applicative instance should behave like ap:

ap f a = do
 f' <- f
 f' <$> a

This rule makes it possible to refactor code using do notation into code using <*>, without it, you would need to think about all use cases this code be used.

In Purescript and in Haskell there is sequential Io/Aff and parallel version Async/ParAff which is not a Monad. (same for with fluture.js too).

But for example Haxl is a lib used for fetching data and has caching built in, so for it all actions could be parallelized as they would have no observable difference (except the speed). tho doing this for IO will definitely have observable difference.

[masaeedu]

@safareli Thanks. I'm assuming the point of this rule is that the user is forced to convert between different data types and explicitly choose between the two possible (legal) applicative instances, i.e. parallel vs "early exit".

[safareli]

yes, so you will convert your sequential values to parallel one, work with it and then covert back.