Implement Scala Cats Traverse for State

Question

I've been writing my own version of Scala Cats (to assist others when learning this library). I've implemented my own versions of most type classes, but am stuck with a custom implementation of Traverse for State. The function to implement is:

def traverse[G[_]: Applicative, S, A, B](fa: State[S, A])(f: A => G[B]): G[State[S, B]]

As a starter, I asked ChatGPT for an implementation in Scala Cats (since of course, it does not know my own library). A valid (simple) implementation in Cats should help me write a version in my own library. However, ChatGPT has failed me, with over-complicated solutions using the likes of StateT (of which currently I do not have an equivalent in my library). Also, the versions produced by ChatGPT do not compile.

One simple suggestion is the following, but does not compile:

import cats._
import cats.implicits._

def traverse[G[_]: Applicative, S, A, B](fa: State[S, A])(f: A => G[B]): G[State[S, B]] = {
  val gb: G[B] =
    fa.runA _ andThen f

  val stateB: G[State[S, B]] =
    gb.map(b => State(s => (s, b)))

  stateB
}

Answer 1

Every Traversable (Traverse in Cats) is Foldable.

State is Applicative and Monad but not Foldable or Traversable

Why isn't the state monad traversable?

Are there non-trivial Foldable or Traversable instances that don't look like containers? (answer)

You can check that in Cats summoning Applicative[State[S, *]] and Monad[State[S, *]] compile but Foldable[State[S, *]] or Traverse[State[S, *]] doesn't.

State[S, A] is basically a function S => (S, A) (if we ignore wrapping, StateT, and Eval).

If State were a Foldable you'd be able to implement

def foldMap[S, A, B: Monoid](fa: S => (S, A))(f: A => B): B
// or
def foldLeft[S, A, B](fa: S => (S, A), b: B)(f: (B, A) => B): B

If State were a Traversable you'd be able to implement

def traverse[G[_]: Applicative, S, A, B](fa: S => (S, A))(f: A => G[B]): G[S => (S, B)]
// or
def sequence[G[_]: Applicative, A](fga: S => (S, G[A])): G[S => (S, A)]

Combining S => (S, A) and A => G[B] you can have S => (S, G[B]) but how to get G[S => (S, B)] if you only can do def ap[A, B](ff: G[A => B])(fa: G[A]): G[B] and def pure[A](x: A): G[A]?

Foldable means you can fold a structure into a value. Traversable means you can traverse a structure executing some applicative effect in every node of the structure. State is like a function, you can't fold it or traverse it.