Scala中for yield结构中的递归调用

Question

我对Coursera中的以下Scala代码感到困惑。这个代码的目的是在胸板上放置n个王后，这样就不会有王后相互威胁，意思是同一行、同一列或同一对角线。

1. 从k=0到k=n，递归调用PlaceQueen(k-1)的求值是如何在每一步中进行的？在线路yield col::queens中是否发生了递归调用PlaceQueen(k-1)？

2. 如果col::queens将前面行的列附加为列表，则yield col::queens的输出应该是列列表。但是它是如何转化为一组列表的呢？

   object nQueens extends App{
   def queens(n: Int): Set[List[Int]] = {
   def placeQueens(k: Int): Set[List[Int]] =
   if (k == 0) Set(List())
   else
   for {
   queens <- placeQueens(k - 1)
   col <- 0 until n
   if isSafe(col, queens)
   } yield col :: queens
   placeQueens(n)
   }
   def isSafe(col: Int, queens: List[Int]): Boolean = {
   val row = queens.length
   val queensWithRows = (row - 1 to 0 by -1) zip queens
   queensWithRows forall {
   case (c, r) => col != c && math.abs(col - c) != row - r
   }
   }
   
   queens(4)
   }
   

输出为：Set(List(1,3,0,2), List(2,0,3,1))

Answer 1

此代码有多个无限循环。

queens方法简单地调用自己，这显然是不正确的：

def queens(n:Int):Set[List[Int]] = {
def placeQueens(k:Int):Set[List[Int]] = ???
def isSafe(col: Int, queens:List[Int]):Boolean = ???
queens(4)
}

placeQueens方法也在经过一点计算后调用自己：

def placeQueens(k:Int):Set[List[Int]] = {
if (k==0) Set(List())
else
for {
queens <-placeQueens(k-1)
col <- 0 until n
if isSafe(col,queens)
} yield col:: queens
placeQueens(n)
}

Answer 2

忽略代码中的所有问题，这些问题使它无法执行预期操作，您的问题的答案是：

如何将其转换为列表集？

它被转换，因为for中的第一个集合是Set。之所以设置它，是因为Set被定义为placeQueens的返回类型。

queens <- placeQueens(k-1)

这也回答了你的第一个问题：

是否存在递归调用placeQueen(k-1)?

因为这是递归调用所在的位置。