Traversing a list/vector is in reverse

[AdamChlupacek]

Hello,

I have been traversing a List using:

val L = implicitly[Traverse[List]]

L.traverse(List(1,2,3))(???)

And I have encountered issue that the order the list get traversed in is 3, 2, 1, which in my opinion is a bit unintuitive. I would find the order 1, 2, 3 to be more intuitive. I do understand that the motivation behind the reverse traversing is so that we only prepend to the result list, but this way I have to do 2 reverses to traverse the list in the order I want.

Instead I propose to traverse the list in the order 1, 2, 3 while still prepending to the head of the result and then reverse the result list.

Adam Chlupacek

[adelbertc]

What is the ??? in this case? If the function is pure the order of traversal should not be observable.

Example with Scalaz:

scala> import scalaz._; import Scalaz._
import scalaz._
import Scalaz._

scala> List(1, 2, 3).traverse { i =>
     |   println(i) // side effect!
     |   Option(i)
     | }
3
2
1
res0: Option[List[Int]] = Some(List(1, 2, 3))

scala> import scalaz.concurrent.Task
import scalaz.concurrent.Task

scala> def printOption(i: Int): OptionT[Task, Int] = {
     |   val task = Task(println(i)) *> Task.now(i)
     |   OptionT(task.map(Option(_)))
     | }
printOption: (i: Int)scalaz.OptionT[scalaz.concurrent.Task,Int]

scala> List(1, 2, 3).traverseU(printOption).run.unsafePerformSync
1
2
3
res3: Option[List[Int]] = Some(List(1, 2, 3))

[AdamChlupacek]

The ??? has an effect, and it requires to be executed in this precise order. It is something along these lines:

def doAction(i: Int): Task[ResultList] = Task.delay(cs.executeAsync(i)) //connection to db

[djspiewak]

@AdamChlupacek This is essentially dependent on the Traverse instance for List, which is not implemented by fs2.

@adelbertc If the traversal is done in an inverse order, the inner applicative may be sequenced incorrectly. Even in pure computations, this is observable. It is irrelevant only for commutative monads, of which Task certainly is not one. I don't believe there are any traverse laws which prevent this though, which is part of what I don't like about Traverse in general.

[AdamChlupacek]

@djspiewak I am using the instance from fs2.util.Traverse

[djspiewak]

Oh, fs2 defines Traverse. Terrific…

Both the Vector and List instances have a call to reverse. I'm guessing that was inserted because of the use of foldLeft, which generates a right-leaning tree. However, right-leaning is not "inverted", and applicatives have associativity. So in other words, the reverse is explicitly causing this problem, and generates a Traverse which is possibly not lawful, and at a minimum significantly unintuitive.

[pchiusano]

This is a bug. Traverse should be implemented with a stack safe right fold,
with the order of effects being the order specified by the list.
On Thu, Oct 13, 2016 at 2:53 PM Daniel Spiewak [email protected]
wrote:

Oh, fs2 defines Traverse. Terrific…

Both the Vector and List instances have a call to reverse. I'm guessing
that was inserted because of the use of foldLeft, which generates a
right-leaning tree. However, right-leaning is not "inverted", and
applicatives have associativity. So in other words, the reverse is
explicitly causing this problem, and generates a Traverse which is
possibly not lawful, and at a minimum significantly unintuitive.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
#746 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AAArQmIbMT-Gh9AMxqhHu_RNDmB9W0tJks5qzn4vgaJpZM4KWLMG
.

[pchiusano]

Actually I am looking at this and the traverse instance does not look
wrong... the list is reversed but it looks like effects are done in he
right order?

Maybe the applicative instance is backward for the type you are using?
On Thu, Oct 13, 2016 at 3:52 PM Paul Chiusano [email protected]
wrote:

This is a bug. Traverse should be implemented with a stack safe right
fold, with the order of effects being the order specified by the list.
On Thu, Oct 13, 2016 at 2:53 PM Daniel Spiewak [email protected]
wrote:

Oh, fs2 defines Traverse. Terrific…

Both the Vector and List instances have a call to reverse. I'm guessing
that was inserted because of the use of foldLeft, which generates a
right-leaning tree. However, right-leaning is not "inverted", and
applicatives have associativity. So in other words, the reverse is
explicitly causing this problem, and generates a Traverse which is
possibly not lawful, and at a minimum significantly unintuitive.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
#746 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AAArQmIbMT-Gh9AMxqhHu_RNDmB9W0tJks5qzn4vgaJpZM4KWLMG
.

[djspiewak]

@pchiusano Are you sure the effects are done in the right order? I don't see anything in the composition which changes the ordering, only the associativity. Thus, the reverse dominates.

[pchiusano]

Am on my phone but it looks like the definition is an inline stack safe
foldRight implemented via reverse and left fold, the key is this line:

(tl,hd) => G.ap(f(hd))(G.map(tl)(tl => (b: B) => b +: tl))
}

So notice that the hd effect is run before the tl effect (assuming the
applicative doesn't do things in backwards order).
On Thu, Oct 13, 2016 at 4:13 PM Daniel Spiewak [email protected]
wrote:

@pchiusano https://github.com/pchiusano Are you sure the effects are
done in the right order? I don't see anything in the composition which
changes the ordering, only the associativity. Thus, the reverse dominates.

—
You are receiving this because you were mentioned.

Reply to this email directly, view it on GitHub
#746 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AAArQlmeyHKVRoUWlpDqcHn2p_csCyjxks5qzpDagaJpZM4KWLMG
.

[AdamChlupacek]

@pchiusano I am using the fs2.Task, so I am pretty sure it is not reversed in my applicative instance. Now If I am reading it right, for Task the Applicative is implemented in Monad which defines it as

def ap[A,B](fa: F[A])(f: F[A => B]): F[B] = flatMap(f)(map(fa))

from this I would assume that we first get the tl effect and hd effect afterwards?

[pchiusano]

@AdamChlupacek yeah I think you've got it!

Honestly, it doesn't matter too much what order it's expected that ap does things in (though running the function's effects first works out nicely, see below) as long as it's documented and any combinators (like traverse, map2, etc) use it in the 'correct' order. But certainly traverse should sequence effects in non-reverse order.

Here are some possible things we could do to fix:

1. Just update those traverse instances and leave everything else alone. We should also audit any usages of traverse internal to the library to make sure they don't need changing (idea - just comment out the instances and compile the code to have Scala tell us any places they are used). Pro: this is binary compatible, could be a point release. Con: it's a subtle semantic change, do we want it to be a totally silent update?
2. Flip the order of the arguments to ap to match the order effects are run. Update traverse instances accordingly. This would be a breaking change. If we are contemplating breaking changes, perhaps we switch to the map2/pure encoding of Applicative while we're at it.

We could do some combination of these, too. 1) for now, with suitable warnings in the release notes / announcement, and then 2) in the next release series, which may not be for a while.

Reason that sequencing the F[A => B] effect first works out nicely:

• map2(a, b)(f) = ap(ap(pure(f.curry), a), b), runs the a effect, then the b effect
• map3(a, b, c)(f) = ap(ap(ap(pure(f.curry), a), b), c))), also works in the order you'd expect

The only thing that is confusing is the F[A => B] is second argument when that effect is run first. There's no type inference reason to put that argument second, the type info doesn't flow into the F anyway:

scala> val T = implicitly[Monad[Task]]
T: fs2.util.Monad[fs2.Task] = Effect[Task]

scala> T.ap(Task.now(10: Int))(Task.now(i => i))
<console>:19: error: missing parameter type
       T.ap(Task.now(10: Int))(Task.now(i => i))

[adelbertc]

Not sure how much it'd help but here are related tickets to how we dealt with it in Cats:

typelevel/cats#167
typelevel/cats#799
typelevel/cats#803

[mpilquist]

Fixed in 0.9 by changing the order of evaluation of default implementation of ap: 38f31cd

In 1.0, we'll change the parameter definition order.