Another encoding of `Traverse` in terms of `mapAccumulate`

traverse.scala

/**
 * In this version of `Traverse`, sequencing always goes through `List` (or some other canonical sequence type),
 * which can be done in a stack-safe manner using a balanced fold as in https://gist.github.com/pchiusano/7667597.
 * It's quite nice that `sequence` and `traverse` are now derived functions.
 */
trait Traverse[F[_]] extends Functor[F] {
  /** Inefficient but correct implementation of `toList` in terms of `mapAccumulate`. */
  def toList[A](f: F[A]): List[A] = mapAccumulate(f, List())((a, rbuf) => (a, a :: rbuf))._2.reverse
  
  /** The only function that must be implemented. Must be consistent with `map`. */                                                           
  def mapAccumulate[S,A](f: F[A], s0: S)(g: (A,S) => (B,S)): (F[B], S)
  
  def sequence[G[_],A](f: F[G[A]])(implicit G: Applicative[G]): G[F[A]] = {
    val gs: List[G[A]] = toList(f)
    val fgs: G[List[A]] = List.sequence(gs)(G)
    G.map(fgs) { (labels: List[A]) => 
      mapAccumulate(f, labels)((_, labels) => (labels.head, labels.tail) // a bit hacky, but safe assuming toList is lawful
      // NB: in a DT language or maybe via path dependent types, probably some way to have typechecker verify safety of this
    }
  }
}

In some ways, I wonder if mapAccumulate better captures the essence of traversal, as it's no longer tied up with effect sequencing (but the effects still end up being sequenced in the same order).

I don't think I follow what you mean by consistent with map. I can think of at least one implementation that type checks and is consistent with map that you may not mean. For instance:

def mapAccumulate[S, A](f: F[A], s0: S)(g: (A, S) => (B, S)): (F[B], S) = {
  type G[A] = (A, S)
  // make an Applicative[G] where pure(a) = (a, s0) and product discards the s on the left.
  f.traverse(g(_, s0))
}

This type checks, I think (and the Applicative is lawful). Is that legit? If so, we can always implement mapAccumulate and it means this is a totally equivalent formulation.

Consistent with map, meaning the implementation of map in terms of mapAccumulate is the map that satisfies functor law(s).

That was the idea, for this to be the same class. The difference is that the primitive is mapAccumulate rather than traverse, and it's easy to implement in a stack safe way without doing anything fancy. Like for any linear sequence, mapAccumulate might use a mutable buffer / builder. When you have the Applicative effects in there, you don't have this option and need to either assume something more than Applicative (like the tailrecm thingy) or use a balanced fold.

So a goal here is: reduce the number of instances that need to do something fancy to ensure stack safety of sequencing.