Apply.applyN and Apply.mapN evaluate arguments in reverse

[ceedubs]

Example:

scala> import cats._, cats.std.implicits._
import cats._
import cats.std.implicits._

scala> Apply[Function0].map2(() => { println("1"); 1 }, () => { println("2"); 2 })(_ :: _ :: Nil)()
2
1
res0: List[Int] = List(1, 2)

scala> Apply[Function0].apply2(() => { println("1"); 1 }, () => { println("2"); 2 })(() => _ :: _ :: Nil)()
2
1
res1: List[Int] = List(1, 2)

I would expect the "1" to print before the "2" in both cases. I suppose it is arbitrary and that as long as we are consistent, we could maybe keep it the way it is, but it does seem counterintuitive.

I believe that this was probably the reason that #142 existed in the first place. @non ended up changing Lists's traverse implementation, but I think changing the implementation of map2 would have been an alternative solution.

What Cats is currently doing is the opposite of scalaz. My confusion in https://github.com/non/cats/pull/142#issuecomment-73452302 was because I had naively copied the Cats traverse implementation for List into scalaz changing map2 to apply2 not realizing the differences in semantics. I believe the current Cats implementation also does opposite of what Haskell does.

I propose changing this to an evaluation order that matches the order of the arguments (and the scalaz precedent). Does anybody have a reason not to?

This could be done by changing the definition of apply2 to:

apply(fb)(apply(fa)(map(f)(f => (a: A) => (b: B) => f(a, b))))

Similar changes would need to be made to map2, List's traverse implementation, and perhaps some other places.

[bobbyrauchenberg]

i can pick this up

[ceedubs]

@bobbyrauchenberg thanks for volunteering! I suspect that other people will want to go forward with this, but let's give them a little bit of time to weigh in before you start the work.

[bobbyrauchenberg]

@ceedubs Sure

[aryairani]

I would've expected that methods like applyN would be like Lisp, in that the order of evaluation is explicitly unspecified, e.g. they could be executed in parallel. If that's true, then whichever implementation is faster is probably better, even if it doesn't perform side-effects in a left-to-right order. If it's not true, then I don't have an opinion :-)

[aryairani]

@ceedubs When you say Haskell has the opposite behavior, do you mean in some expression with performUnsafeIO?

[ceedubs]

@refried sorry I forgot about this for a while.

No, when I say that Haskell has the opposite behavior, I am not referring to cases of performUnsafeIO.

Here is some Haskell code that is roughly equivalent to my example (disclaimer - I don't know Haskell very well):

import Control.Applicative

main = liftA2 (\x y -> x : y : []) (1 <$ (putStrLn "1")) (2 <$ (putStrLn "2"))

The output is:

1
2

and the returned value is [1,2].

A version of the Scala example that would line up a little better with this Haskell code might be something like:

val a = Apply[Function0]
a.map2(a.map(() => println("1"))(_ => 1), a.map(() => println("2"))(_ => 2))(_ :: _ :: Nil)()

which still prints 2 before 1 but then has the result of List(1, 2).

Note: Scala doesn't have a built-in IO type, so I'm using Function0 as a replacement.

I agree that side effects not represented in the type system don't need to have a guaranteed execution order when using something like applyN. But when we are wrapping our side effects in IO-like types (Task, Function0), I would have the expectation that they would execute in a predictable order. I would also expect that order to be the order that they are passed to the applyN call, because any other guaranteed order seems a bit silly.

Does that make any sense? I seem to be alone in this matter, so maybe I'm being silly/ignorant.

[ceedubs]

@refried I guess there could be an alternative point of view here that applyN and friends make no guarantees and that if you want sequential ordering you should use flatMap instead.

I guess that gets into the whole discussion of whether flatMap and ap need to be consistent and if so, whether side effects count as something they need to be consistent about.

[ceedubs]

Sorry to spam this issue, but saying thoughts as they come to me:

It does seem like it would be a bummer to not be able to traverse a list into IO and have that execute in a predictable order. Our Traverse[List] implementation is depending on these side effects happening in a consistent order for this use-case. It's just that it is depending on them happening in the opposite order that I would expect from ap/applyN/mapN.

[tpolecat]

At least in scalaz the constructed IO program is associated to the right, so the elements are visited in reverse but the resulting program does what you want. It's important to distinguish the traversal from the resulting construction. (This may be what you're saying, sorry, I haven't had any coffee yet.)

In any case, see scalaz/scalaz#886

[ceedubs]

@tpolecat yes. I'm not sure whether or not that's what I am saying, but it sounds like we are on the same page.

[aryairani]

Hi folks, I also haven't had coffee, and kind of forgot about this conversation too (double disclaimer) but if I understood @ceedubs correctly then I agree, flatMap is for sequencing operations, and nothing else is.

So again I'm not saying apply should be right to left, but that the order shouldn't be something we rely on. In a pure program, the order doesn't matter; side effects is the only place this comes up. Function0 isn't really about side effects, but Task is, and Task has flatMap for when sequencing is important.

Wait I just saw the second comment about List traverse and IO. The resulting IO should execute in the left-to-right order of the List imo. Does it not? And these are delayed IO effects and not side effects, right? cheers

[ceedubs]

@refried these are delayed IO effects (still side-effects though). The problem with what you are suggesting is that traverse only requires an applicative functor, not a Monad/FlatMap, so you can't rely on flatMap in your traverse implementation.

Oh and regarding "does it not?". It does, due to a change that Erik made that relies on the reverse behavior of apply2.

[aryairani]

Sorry, I later noticed @ceedubs gave a few different viewpoints; I didn't mean to misrepresent.

[aryairani]

Never thought I'd be saying github is too slow compared to IRC!

Hmm what about the rule of thumb "if your container supports sequencing, then use flatMap for its traverse"? List and IO and Task all can. Granted, I still haven't had coffee and I don't completely know what I'm talking about and I'm not at a compiler, but I will try to play with an example later to see if I can unconvince myself.
(I'm going to wait on the "it does" until I can write/paste some code.)

[ceedubs]

@refried if you are traversing a List[A] with A => F[B], where F has an applicative functor, then it doesn't really matter that List has flatMap. If F is IO then F would have flatMap, but you don't know that from the type signature of traverse, which just requires an applicative. So it's not really about whether your container supports sequencing, if I understand what you are saying.

[aryairani]

@ceedubs You probably understood me right, and I am probably wrong, or at least confused because I'm pretty tired. Would you be willing to show an example that uses Task or IO? I didn't understand the part where you said "these are delayed IO effects (still side effects)" because I thought those meant kind of opposite things.

[ceedubs]

@refried Here is an example that uses scalaz.IO (with the help from @rossabaker's handy scataz project after adding a scalaz-effect dependency to it locally). I'm calling unsafePerformIO but only at the "end of the world" so to speak.

scala> import scalaz.effect.IO, cats._, cats.std._, scataz.toCats._
import scalaz.effect.IO
import cats._
import cats.std._
import scataz.toCats._

scala> val a = Apply[IO]
a: cats.Apply[scalaz.effect.IO] = scataz.toCats$$anon$1@4403dedd

scala> a.map2(a.map(IO(println("1")))(_ => 1), a.map(IO(println("2")))(_ => 2))(_ :: _ :: Nil).unsafePerformIO
2
1
res0: List[Int] = List(1, 2)

Regarding "these are delayed IO effects (still side effects)": I don't know maybe I'm being loose with terminology here. I'm just saying that I'm doing println which is a side effect, but I'm capturing that side effect in the type system and delaying it via IO (or Function0 in my previous example).

[aryairani]

@ceedubs Got it — thanks for the example, and the scataz link.

import scalaz.effect.IO
import cats._
import cats.std._ // wouldn't work for me, I copy/pasted the listInstance instead
import scataz.toCats._

val ops = List(IO(println("1")), IO(println("2"))
val orderMatters = implicitly[Traverse[List]].sequence(ops)

My thinking is that as long as this comes out in the right order, all is well. What do you think?

scala> orderMatters.unsafePerformIO
1
2
res6: List[Unit] = List((), ())

[ceedubs]

It seems unintuitive to me to have a list traverse that guarantees left to right effect order by depending on map2's evaluation being right to left. My preference would be to have both be left-to-right like in Haskell and Scalaz. I seem to be alone in caring about this, though, so I am willing to let go of it.

Note that I'm fine with us visiting elements in the list in reverse order. I'm just saying that tracked side effects like IO should happen in the order they are passed to map2.

Also I think throughout this whole PR I have been mixing up the fact that what's called apply2 in Scalaz is called map2 in cats. Sorry for any confusion this may have caused.

[aryairani]

For the record, I don't mind if it's swapped so that it is left-to-right, but my gut is worried about having a rule that it must be left-to-right.

I'm not sure if this example is any good, but how would you feel if it was mapN over Future (or something), and the arguments were evaluated in parallel and completed in an unpredictable order?

[tpolecat]

Yep, I think @ceedubs is correct. When a monad is available (a |@| b).map(f) should be the same as for { x <- a; b <- a } yield f(a, b) but this is not the case. The poor man's IO above illustrates it, but you get the same result with State or anything else with effects.

[aryairani]

@tpolecat Sorry to ask, but are you sure?

[aryairani]

@tpolecat Or is there maybe some law that would settle it?

[ceedubs]

Since this is dealing with side effects, I don't think this is the sort of thing that you can wrap a law around.

@refried I kind of feel like we are stuck in a loop :(. If you want to say that no order is guaranteed in map2, then you also need to be willing to say that there is no order guaranteed when traversing a list into IO. Earlier you said "The resulting IO should execute in the left-to-right order of the List imo". I think you are going to need to choose between one of the two. Personally, I would choose the reliable sequencing of effects.

[aryairani]

@ceedubs I'm leaning towards your side, I just don't understand it (and I may never, due to personal limitations) ;-)

To point 1 (laws vs side effects): Would it help if we look at it in terms of the State monad?

To point 2 (apply vs traverse): I started to wonder the same thing as I was posting, but I couldn't wrap my head around it. Is there some rule that says State effects should execute from head to tail? Maybe there's not. Maybe there shouldn't be, because like you pointed out, traverse only depends on Applicative. I'm trying to decide "Would that be so bad?" When I think about using Validation I don't think it's so bad; and when I think about using some parallel evaluator, I don't think it's so bad. Edit: But at the same time, it is nice to be able to traverse a List of State and get those effects applied in order.

Is there another function like traverse but that uses the sequencing ability of Monad?

[tpolecat]

It's about effects. Try |@| syntax with State and it goes the wrong direction. So we could switch the implementation of ApplyBuilder to pass its args backwards I guess, but it seems to me that we should just make it work like scalaz and call it good. I am confident that scalaz is correct.

[aryairani]

Proof by scalaz. It's ok with me though.

Edit: Even if the order shouldn't be specified, scalaz's is fine. Whatever makes things easier to reason about is good anyway; as long as it doesn't cause some problem I'm not aware of.

Edit 2: Don't mind me; I'm trying to learn, more than I am trying to say stuff.

[aryairani]

Err, wait!

@ceedubs re "traverse only requires an applicative functor, not a Monad/FlatMap, so you can't rely on flatMap in your traverse implementation.": Although I was mixed up, and you're right, the Traversable instance is what specifies the order, not the Applicative instance.

from Haskell docs:

Traversable: "Functors representing data structures that can be traversed from left to right."

So traverse imo should sequence effects "left to right", for whatever "left to right" means for that Traversable instance.

OTOH, <*> says "sequential application" and "sequence computations and combine their results". Although it doesn't explicitly say "left to right". I don't personally understand the Applicative laws, but (a) do they not answer this? And (b) if not, why not?

I feel like I should back out at this point, but I would love to understand the answers to (a) and (b). I dunno who else to tag in to ask.

[ceedubs]

@refried I'm 100% for talking through this sort of stuff and learning more. I don't think I'm articulate enough to do it well over GitHub comments, though. Some time in the next few days I'll try to get a hold of you on Gitter and maybe we can discuss it some more there or on a google hangout or something. How does that sound?

[aryairani]

@ceedubs Same here, sounds great.