Cats框架下State Monad列表的sequence方法能否实现快速终止？

这确实是个很实用的需求——默认的State序列操作会严格执行所有步骤，哪怕中途已经满足终止条件，就像你看到的那样，后面的冗余步骤完全没必要跑。想要实现类似Either的快速失败，我们有两种比较优雅的方案，不需要写大量尾递归样板：

方案一：用EitherT包装State，利用短路Monad特性 #

Cats里的EitherT是一个Monad转换器，它的sequence操作天生支持短路：一旦遇到Left值，后续的所有步骤都会被跳过。我们可以把每个State操作的结果包装成Either[StopRunning.type, ContinueRunning.type]，这样就能让序列自动终止。

代码实现 #

import cats.data.{State, EitherT}
import cats.instances.list._
import cats.syntax.traverse._
import cats.syntax.either._

trait MachineState
case object ContinueRunning extends MachineState
case object StopRunning extends MachineState
case class Machine(candy: Int)

// 调整addCandy返回EitherT包装的State
val addCandy: Int => EitherT[State[Machine, *], StopRunning.type, ContinueRunning.type] = amount => EitherT(
  State[Machine, Either[StopRunning.type, ContinueRunning.type]] { machine =>
    val newCandyAmount = machine.candy + amount
    if (newCandyAmount > 10) {
      // 超过上限，返回Left终止后续操作
      (machine, Left(StopRunning))
    } else {
      // 正常添加，返回Right继续
      (machine.copy(candy = newCandyAmount), Right(ContinueRunning))
    }
  }
)

// 执行序列操作
val (finalMachine, result) = List(
  addCandy(1), addCandy(2), addCandy(5), 
  addCandy(10), addCandy(20), addCandy(50)
).sequence.run(Machine(0)).value

println(finalMachine) // Machine(8) —— 执行到前3步后，第4步触发终止，状态停在8
println(result)       // Left(StopRunning) —— 第一个终止信号被返回

这个方案的好处是完全复用Cats的现有工具，几乎不需要额外的样板代码，语义也非常清晰：Left代表终止，Right代表继续。

方案二：自定义带终止语义的Traverse函数 #

如果你需要更定制化的结果（比如保留已经执行成功的步骤列表），可以写一个自定义的traverse函数，手动处理终止逻辑。这个方案的样板代码很少，逻辑也直观：

代码实现 #

import cats.data.State
import cats.instances.list._
import cats.syntax.traverse._

trait MachineState
case object ContinueRunning extends MachineState
case object StopRunning extends MachineState
case class Machine(candy: Int)

// 定义执行结果类型，区分完成和终止两种情况
sealed trait ExecutionResult
case class Completed(completedSteps: List[MachineState], finalMachine: Machine) extends ExecutionResult
case class Aborted(completedSteps: List[MachineState], reason: StopRunning.type, finalMachine: Machine) extends ExecutionResult

val addCandy: Int => State[Machine, MachineState] = amount => State[Machine, MachineState] { machine =>
  val newCandyAmount = machine.candy + amount
  if(newCandyAmount > 10) (machine, StopRunning)
  else (machine.copy(candy = newCandyAmount), ContinueRunning)
}

// 自定义带短路的traverse函数
def traverseWithShortCircuit(states: List[State[Machine, MachineState]]): State[Machine, ExecutionResult] = {
  states.foldLeft(State.pure[Machine, ExecutionResult](Completed(Nil, Machine(0)))) { (acc, nextState) =>
    acc.flatMap {
      // 如果还在正常执行，继续下一步
      case Completed(steps, machine) =>
        nextState.run(machine).value match {
          case (newMachine, ContinueRunning) =>
            State.pure(Completed(steps :+ ContinueRunning, newMachine))
          case (newMachine, StopRunning) =>
            State.pure(Aborted(steps :+ StopRunning, StopRunning, newMachine))
        }
      // 已经终止，直接返回当前结果
      case aborted => State.pure(aborted)
    }
  }
}

// 执行测试
val result = traverseWithShortCircuit(List(
  addCandy(1), addCandy(2), addCandy(5), 
  addCandy(10), addCandy(20), addCandy(50)
)).run(Machine(0)).value

println(result)
// 输出：Aborted(List(ContinueRunning, ContinueRunning, ContinueRunning, StopRunning),StopRunning,Machine(8))

这个方案能完整保留所有已执行的步骤和终止时的状态，适合需要记录执行过程的场景，代码量也不大，逻辑一目了然。

为什么默认的State sequence不行？ #

默认的State是一个严格的Monad，它的sequence操作会遍历整个列表，不管前面的步骤结果如何。而Either（或EitherT）的Monad实例是非严格的，当遇到Left时会跳过后续的flatMap操作，这就是它能实现快速失败的核心原因。

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