FreeApplicative applies effects in wrong order

[ceedubs]

Here is a fairly minimal way to reproduce the error:

import cats._
import cats.free.FreeApplicative
import cats.arrow.NaturalTransformation
import cats.implicits._

type Dsl[A] = FreeApplicative[Id, A]
val x: Dsl[String] = FreeApplicative.lift[Id, String]("x")
val y: Dsl[String] = FreeApplicative.lift[Id, String]("y")

// either one produces the wrong output, so it's not a problem with the |@| syntax
//val z: Dsl[Unit] = (x |@| y).map((_, _) => ())
val z = Apply[Dsl].map2(x, y)((_, _) => ())

val asString: Id ~> λ[α => String] = new (Id ~> λ[α => String]) {
  def apply[A](a: A): String = a.toString
}

// produces "yx" instead of "xy"
z.analyze(asString)

I believe this is a bug in the ap implementation.

Scalaz's implementation of FreeAp does the same thing, so it's possible that I'm wrong about what the expected result should be, but I don't think so. cc @runarorama

@adelbertc, @mandubian, or @raulraja would any of you want to take a look at this by any chance?

[ceedubs]

Hmm this might actually be because of how foldMap is implemented (which analyze uses).

[mandubian]

Wouldn't it be due to the way Const Applicative ap is implemented?

https://github.com/non/cats/blob/master/core/src/main/scala/cats/data/Const.scala#L106-L108

[ceedubs]

@mandubian I am pretty sure Const's ap now uses the correct order. It used to be wrong but that was fixed in non@0fb2826. ap is supposed to apply effects in the opposite order of the parameters, which is a bit confusing.

[mandubian]

not yet in master, right?

[ceedubs]

@mandubian It should be. It was merged with #502 I believe.

[mandubian]

oh no, you mean it's normal to be in the opposite and it's right in master :)
The z structure looks like:

z: Dsl[Unit] = Ap(x,Ap(y,Pure(<function1>)))

I've added some dummy println to check order:

scala> z.analyze(asString)
foldMap -> pivot:x
foldMap -> pivot:y
Const.app -> fa:Const(y) f:Const() r:Const(y)
Const.app -> fa:Const(x) f:Const(y) r:Const(yx)
res0: String = yx

So it seems to execute as expected...

[mandubian]

I don't really understand why we have made this modification for apas in Haskell, the signature is:

(<*>) :: f (a -> b) -> f a -> f b

and in cats it's

def ap[A, B](fa: Const[C, A])(f: Const[C, A => B]): Const[C, B]

so f & fa should have been reversed not the order of execution of f & fa...

and in haskell it is clearly considered that order of execution in an applicative has been chosen from left to right (even if in theory, there is no order, it should just be deterministic)

[ceedubs]

@mandubian I think the important thing is that the effect of the F[A => B] occurs before the effect of F[A], which I believe happens in the current implementation, doesn't it?

[mandubian]

I've looked at Haskell Const applicative and yes it seems to apply function before...
but it means our Applicative implementation executes the function before the pivot and this is counter-intuitive compared to what you write and it is normal that you obtain yx

[adelbertc]

I ran into this issue today with: https://github.com/adelbertc/cats/blob/monoidal-redux/laws/src/main/scala/cats/laws/ApplicativeLaws.scala#L36

My initial impression was to do:

F.ap(fa)(f) <-> F.map(F.product(fa, f)) { case (a, f) => f(a) }

but had to change to this to account for the evaluation of effects of F[A => B] vs. F[A]

F.ap(fa)(f) <-> F.map(F.product(f, fa)) { case (f, a) => f(a) }

[LiamGoodacre]

Just as a side note, the free applicative implementation of purescript had this issue too: ethul/purescript-freeap#4

[mandubian]

@adelbertc it seems to be implemented as is if I'm not wrong... you write ap(fa)(f) and then f is executed before fa which seems not logical, right? (in haskell it would be ap(f)(fa) and f would be executed before fa which is expected)

[ceedubs]

@LiamGoodacre thanks for the reference, that's helpful!

@mandubian yes, in ap, f's effects should happen before fa's. However, I think the issue is that foldMap on FreeApplicative was passing the "tail" in as the second argument to ap, so the "tail" effects were coming before the "head".

I've changed the following line of the foldMap implementation:

case Ap(pivot, fn) => G.ap(f(pivot))(fn.foldMap(f))

to this:

case Ap(pivot, fn) => G.map2(f(pivot), fn.foldMap(f))((a, g) => g(a))

This seems to fix the issue. There may be a more elegant or efficient way of writing this. Should I go ahead and submit a PR for this?

[mandubian]

my problem for now is that it's completely error prone... nobody will remind that when calling ap(a)(f), f is executed before a... and map2 does it in the left to right way...

[ceedubs]

@mandubian that's a fair concern. Should we change the signature of ap to take f as the first argument and fa as the second?

I do think that's a separate issue from this one, though. I'm inclined to address each in different PRs.