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
    }
  }
}