使用Cats实现递归Monad执行：链式查找服务类型错误排查

错误原因分析 #

1. 第一次实现错误：
   for推导中db.read返回F[Option[String]]，map（即yield）后的分支类型不统一：一个分支返回递归调用的F[Option[String]]，另一个分支返回普通字符串，导致外层F包裹的内容类型混乱，不符合方法签名要求的F[Option[String]]。
2. 第二次实现错误：
   tailRecM的状态元组第一个元素应为Option[String]，但你直接把db.read(value)返回的F[Option[String]]塞进了状态里，没有解包F上下文，导致类型不匹配。

正确实现 #

import cats.Monad

trait LookUp[F[_]] {
  def read(key: String): F[Option[String]]
}

def readWhileFound[F[_]: Monad](initialKey: String, db: LookUp[F]): F[Option[String]] = {
  Monad[F].tailRecM((Option(initialKey), List.empty[String])) { case (currentKeyOpt, acc) =>
    currentKeyOpt match {
      // 存在合法未重复的查询key，发起db查询
      case Some(currentKey) if !acc.contains(currentKey) =>
        // 解包db.read返回的F上下文，拿到下一级查询key
        db.read(currentKey).map { nextKeyOpt =>
          Left((nextKeyOpt, currentKey :: acc))
        }
      // 触发终止条件：查询key为空/出现重复值
      case _ =>
        val result = if (acc.isEmpty) None else Some(acc.reverse.mkString(""))
        Monad[F].pure(Right(result))
    }
  }
}

实现说明 #

• 状态元组设计为(下一个要查询的key: Option[String], 已累加的结果列表: List[String])，避免把未计算的F上下文塞进状态
• 每次db.read返回结果后才更新状态进入下一轮递归，完全符合tailRecM的栈安全要求
• 终止时翻转累加器（因为每次是头插）再拼接，保证返回字符串的顺序和查询顺序一致
• 首次查询就返回None的场景会直接返回None，完全匹配需求定义

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