Scala中BFS与DFS的Monad抽象整合及相关实现疑问

尾递归BFS实现 #

import scala.collection.mutable

/** Do BFS from start and return the smallest distance to end (None if not connected) */
def bfs[A](start: A, end: A, neighbors: A => Seq[A]): Option[Int] = {
  val seen = mutable.Set(start)

  @annotation.tailrec
  def search(curr: Seq[A], dist: Int): Option[Int] =
    if seen(end) then Some(dist)
    else if curr.isEmpty then None
    else search(curr.flatMap(neighbors).filter(seen.add), dist + 1)

  search(curr = Seq(start), dist = 0)
}

示例用法 #

val graph = Map(
  1 -> Seq(2, 3),
  2 -> Seq(4),
  3 -> Seq(4),
  4 -> Seq(5)
)

val dist = bfs(start = 1, end = 5, neighbors = graph)
println(dist)

递归DFS实现 #

def dfs[A](start: A, end: A, neighbors: A => Seq[A]): Option[Int] = {
  val seen = mutable.Set(start)

  def search(curr: A, dist: Int): Option[Int] =
    if seen(end) then Some(dist)
    else neighbors(curr).filter(seen.add).flatMap(search(_, dist + 1)).minOption

  search(curr = start, dist = 0)
}

尝试用Monad整合的代码 #

import cats._
import cats.implicits._

def search[F[_]: Monad, A](start: A, end: A, neighbours: A => Seq[A]): Option[Int] = {
  val seen = mutable.Set(start)

  def doSearch(curr: F[A], dist: Int): Option[Int] =
    if seen(end) then Some(dist) 
    else curr.flatMap(neighbours).filter(seen.add).flatMap(doSearch(_, dist + 1)).minOption
  
  doSearch(curr = Monad[F].pure(start), dist = 0)
}

def bfs[A](start: A, end: A, neighbours: A => Seq[A]): Option[Int] = search[List, A](start, end, neighbours)
def dfs[A](start: A, end: A, neighbours: A => Seq[A]): Option[Int] = search[Id, A](start, end, neighbours)

问题解答 #

1. 编译失败原因与合适的抽象选择 #

编译失败核心原因有两点：

• 类型不匹配：curr.flatMap(neighbours)返回F[Seq[A]]，但后续filter(seen.add)需要可直接过滤的序列类型；同时flatMap(doSearch(...))中，doSearch返回Option[Int]，但F的flatMap无法直接处理Option类型的结果。
• Monad抽象不足：Monad仅能处理单步上下文转换，但这里需要将A的集合（或单个A）转换为新的F[A]结构，还要对F内部元素做遍历、过滤后重建F。更合适的是**Traverse + Monad**组合，或者补充Foldable约束来处理元素遍历。

修正思路：需要把F[Seq[A]]转换为F[A]——比如对List用flatten，对Id则取Seq[A]的第一个元素（符合DFS深度优先的分支选择逻辑）；同时要统一Option和F的上下文转换，避免类型冲突。

2. 实现思路的合理性 #

这个思路合理且有创新性：

• 传统BFS/DFS以容器类型（队列/栈）区分，而你从节点处理粒度出发：BFS批量处理当前层所有节点（对应List多元素上下文），DFS逐个处理分支节点（对应Id单元素上下文），精准抓住了两种遍历的核心差异——并行处理分支 vs 串行处理分支。
• 虽然公开文献中较少直接用Monad关联两者，但本质上是利用Monad的"上下文计算"特性：List代表多分支并行探索，Id代表单分支串行探索，完全对应BFS层序、DFS深度优先的遍历逻辑。

需要注意：原DFS用minOption保证取最短路径，而BFS天然能在第一次遇到终点时得到最短路径，整合时要确保不同F的逻辑都能正确返回最短距离——比如List的批量处理可提前终止，Id则需遍历所有分支后取最小。

3. 实现尾递归的方案 #

有两种可靠方案实现尾递归：

方案一：使用scala.util.control.TailCalls

将递归调用包装为TailRec类型，最后执行result()获取结果：

import scala.util.control.TailCalls._
import cats._
import cats.implicits._

def search[F[_]: Monad: Foldable, A](start: A, end: A, neighbours: A => Seq[A]): Option[Int] = {
  val seen = mutable.Set(start)

  def doSearch(curr: F[A], dist: Int): TailRec[Option[Int]] =
    if seen(end) then done(Some(dist))
    else if curr.isEmpty then done(None)
    else {
      val next = curr.flatMap(a => neighbours(a).filter(seen.add)).foldMap(Monad[F].pure)
      tailcall(doSearch(next, dist + 1))
    }
  
  doSearch(Monad[F].pure(start), 0).result
}

方案二：利用Cats的Monad.tailRecM

Cats的Monad提供了tailRecM方法，专门用于将递归转换为尾递归：

import cats._
import cats.implicits._

def search[F[_]: Monad: Foldable, A](start: A, end: A, neighbours: A => Seq[A]): Option[Int] = {
  val seen = mutable.Set(start)

  def step(state: (F[A], Int)): Either[(F[A], Int), Option[Int]] = {
    val (curr, dist) = state
    if seen(end) then Right(Some(dist))
    else if curr.isEmpty then Right(None)
    else {
      val next = curr.flatMap(a => neighbours(a).filter(seen.add)).foldMap(Monad[F].pure)
      Left((next, dist + 1))
    }
  }

  Monad[Option].tailRecM((Monad[F].pure(start), 0))(step)
}

注：需要为F添加Foldable约束来判断curr是否为空；next的转换逻辑需根据F的特性调整——比如List直接flatten，Id则取Seq[A]的首个元素。

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