为State实现Scala Cats Traverse遇阻，求可行方案指导

我正在编写一个Scala Cats的简化自定义版本（用于教学），已经实现了大部分类型类，但卡在为State实现自定义Traverse上。需要实现的函数签名如下：

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

我曾向ChatGPT索要Scala Cats官方的实现参考，但给出的方案要么过于复杂（用到了我库中尚未实现的StateT），要么无法编译。其中一个看似简洁的方案如下，但同样无法编译：

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
}

问题分析 #

这段代码编译失败的核心原因是类型不匹配：fa.runA _ andThen f的实际类型是S => G[B]（一个接受初始状态并返回G[B]的函数），但代码中强行将其赋值给G[B]类型的变量gb，直接导致编译错误。此外，该实现的逻辑也存在问题：它完全丢弃了原State的状态变换逻辑，只是将B包装成一个不修改状态的State，不符合Traverse的语义要求。

解决方案 #

要正确实现State的Traverse，首先需要明确你的State定义：

• 若你的State是严格版本（即run: S => (S,A)），则无法直接实现Traverse——因为严格State的run方法必须返回同步的(S,A)，无法容纳G[B]的上下文。此时你需要修改State的定义，让其run方法返回一个Monadic类型（如Eval[(S,A)]），采用类似StateT的简化形式。

针对修改后的State（基于Eval的惰性版本），正确的Traverse实现如下：

import cats.Applicative
import cats.Eval
import cats.Traverse

// 定义基于Eval的State
case class State[S, A](run: S => Eval[(S, A)])

object State {
  // 实现Traverse实例
  implicit def traverseInstance[S]: Traverse[State[S, *]] = new Traverse[State[S, *]] {
    override def traverse[G[_]: Applicative, A, B](fa: State[S, A])(f: A => G[B]): G[State[S, B]] = {
      val applicative = Applicative[G]
      // 构造新的State运行逻辑：保留原状态变换，将A映射为G[B]并转换为G[(S,B)]
      val newRun: S => Eval[G[(S, B)]] = s => {
        fa.run(s).map { case (sNext, a) =>
          applicative.map(f(a))(b => (sNext, b))
        }
      }
      // 将新的State包装在G上下文中返回
      applicative.pure(State(newRun))
    }
  }
}

或者更简洁的写法：

import cats.Applicative
import cats.Eval
import cats.Traverse

case class State[S, A](run: S => Eval[(S, A)])

object State {
  implicit def traverseInstance[S]: Traverse[State[S, *]] = new Traverse[State[S, *]] {
    override def traverse[G[_]: Applicative, A, B](fa: State[S, A])(f: A => G[B]): G[State[S, B]] = {
      Applicative[G].pure(State(s => 
        fa.run(s).flatMap { case (sNext, a) =>
          Eval.now(Applicative[G].map(f(a))((sNext, _)))
        }
      ))
    }
  }
}

该实现既保留了原State的状态变换逻辑，又正确地将G上下文与State结构结合，完全符合Traverse的语义要求。

内容的提问来源于stack exchange，提问作者D Ainslie