traverse behavior with v2.11.0

[ken1ma]

traverse started to work differently for us with cats 2.11.0.
I'd appreciate if someone can tell me whether this is expected or not.

A reduced code to reproduce the difference (scala-cli version)

#!/usr/bin/env -S scala shebang -S 3.5.1
//> using dep org.typelevel::cats-effect:3.5.4
//> using dep org.typelevel::cats-core:2.12.0

import cats.effect.{IO, IOApp}
import cats.syntax.all.*

case class WriteCursor(offset: Int): // stripped version of fs2.io.file.WriteCursor
  def write(len: Int): IO[WriteCursor] = IO.delay:
    WriteCursor(offset + len)

object TraverseWriteCursor extends IOApp.Simple:
  var wc = WriteCursor(0)  // I was too lazy to rewrite traverse to foldLeft and eliminate var

  val run =
    List(2, 3).traverse: len =>
      for
        nextWc <- wc.write(len)
        _ <- IO.delay { println(s"offset: (${wc.offset}, $len) -> ${nextWc.offset}") }
        _ <- IO.delay { wc = nextWc }
      yield ()
    .void

If we change the dependency to cats-core 2.10.0, it prints

offset: (0, 2) -> 2
offset: (2, 3) -> 5

but with cats-core 2.11.0 and 2.12.0 (as in the above code)

offset: (0, 2) -> 2
offset: (2, 3) -> 3

The the previous behavior is restored if Use applicative methods instead of flatMap is reverted, by changing the code in Traverse.traverseDirectly

  G.map2(accG, f(a)) { case (acc, x) =>
    acc :+ x
  }

to

  G.flatMap(accG) { acc =>
    G.map(f(a)) { b =>
      acc :+ b
    }
  }

1. ChatGPT o1-preview gave me a seemingly good explanation of the above change in a couple of tries.
2. Unlike (very breaking) change in Future instances? #4617, only IO is used in this, so I think the order of evaluations by Traverse should be deterministic.

[ken1ma]

For the context, we found the difference after I upgraded fs2 to 3.11.0 from 3.10.2
(and we didn't have a test case to catch it).

The dependency relationships to cats-core are

1. fs2-core 3.11.0 depends on cats-effect 3.5.4 and cats-core 2.11.0
2. fs2-core 3.10.2 depends on cats-effect 3.5.4 and cats-core 2.10.0
3. cats-effect 3.5.4 depends on cats-core 2.9.0

[satorg]

@ken1ma , the code inside for comprehension is not referentially transparent. To be specific, this line:

nextWc <- wc.write(len)

Since wc itself changes its state, the access to it has to be "protected" by suspending it in IO, e.g.:

  var wc = WriteCursor(0)  // I was too lazy to rewrite traverse to foldLeft and eliminate var

  val run =
    List(2, 3).traverse: len =>
      for
        prevWc <- IO.delay { wc }
        nextWc <- prevWc.write(len)
        _ <- IO.delay { println(s"offset: (${prevWc.offset}, $len) -> ${nextWc.offset}") }
        _ <- IO.delay { wc = nextWc }
      yield ()
    .void

Otherwise, wc.write(len) is called with the initial value of wc for every item traversed.

But I would suggest to switch to Ref instead of var here.

Also, a minor hint – in this example you could make use of traverse_ instead of traverse to avoid adding .void after it.

[satorg]

... and yeah, I would argue with ChatGPT – it is not related to "potentially parallel evaluation of accG and f(a)", actually.

[ken1ma]

Thank you for the comment.

Since wc itself changes its state, the access to it has to be "protected" by suspending it in IO, e.g.:

I should have known.
This should be why delay must be present to read the value in AtomicCell.AsyncImpl.evalModify

https://github.com/typelevel/cats-effect/blob/v3.5.4/std/shared/src/main/scala/cats/effect/std/AtomicCell.scala#L220

[ken1ma]

@satorg Thank you again for the reply.

not referentially transparent

In a less-reduced code, I can still see the problem of not suspending the read of wc.
I'm sharing it to record a pattern without for comprehension:

val writeCursorRes: Resource[F, fs2.io.file.WriteCursor[F]] = ...
val outRes = writeCursorRes.map: writeCursor =>
  var wc = writeCursor
  Some((text: String) => wc.write(Chunk.array(text.getBytes(UTF_8))).map(wc2 => wc = wc2))

// a while later

outRes.use: out =>  // out is a function that takes String and returns F[Unit]
  val inFiles: Seq[Path] = ...
  inFiles.traverse: inFile =>
    out(severalMethodCallTreeToProduceTextFor(inFile))

But I would suggest to switch to Ref instead of var here.

Yes. We are now now using AtomicCell to hold WriteCursor but Ref would suffice in our case.

Also, a minor hint – in this example you could make use of traverse_ instead of traverse to avoid adding .void after it.

Yes. We are waiting for traverseVoid (#4611)