Решение Scala для nQueen с использованием for-comprehension

У меня есть некоторые трудности с пониманием решения n Queens на Scala, ниже приведена реализация, предполагающая isSafe определяется правильно

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

    placeQueens(n)
  }

Для понимания, как я видел, теоретически должна возвращаться буферизованная коллекция, и я вижу здесь, что она буферизует список ферзей с k :: queens, но на самом деле возвращает Set[List], как определено. Может ли кто-нибудь пролить свет на то, как работает это for понимание?

Верно ли мое предположение, что for каждый раз будет возвращать набор коллекций, и поскольку в этом случае я имею дело с Seq и Set во вложенном выражении for for, он возвращает Set[List].

Вопрос больше связан с пониманием for реализации nQueen, а не nQueen в целом.


scala for-comprehension n-queens
person Somasundaram Sekar    schedule 25.10.2014    source источник
comment
Я думаю, что следующее выражение дает немного ясной картины того, что происходит в фоновом режиме: выражение for(x <- e1; y <- e2) yield e3 разбито на слишком отдельное выражение for(y <- e2) yield e3, плоское сопоставление с первым выражением, приводящим к e1.flatMap(x => for (y <- e2) yield e3), поэтому в приведенном выше случае каждый список полученного queens должен быть плоско сопоставлены с набором, который является коллекцией верхнего уровня.   -  person Somasundaram Sekar    schedule 25.10.2014

Ответы (2)


arrow_upward
1
arrow_downward

Вспомните, что for comprehension — это просто синтаксический сахар для map, flatmap и filter, все три из которых вы используете в своем примере. Все, что вы получите в блоке yield, будет добавлено в сопоставленную коллекцию. Вам может быть интересна эта статья о том, как работает yield.

Когда вы возвращаете k :: queens, вы создаете список с добавлением k в список ферзей, который был сгенерирован рекурсивным вызовом с использованием k-1.

Ваше предположение верно. Понимание for вернет типы задействованных списков. Поскольку placeQueens возвращает Set[List[Int]], то же самое будет и для понимания. Перевод вашего for понимания таков:

placeQueens(k-1).flatMap { queens => 
  (0 until n).withFilter { col => 
    isSafe(col, queens)
  }.map { col => 
    k::queens
  }
}
person Reid Spencer    schedule 25.10.2014

arrow_upward
1
arrow_downward

Помните, что for понимание, по сути, применительно к последовательности описывает отображение элементов этой последовательности с помощью функции, которая указана внутри тела for понимания. Следовательно, конечным результатом будет коллекция исходного внешнего типа (т. е. Set, List или любого другого Seq-потомка) поверх типа, возвращаемого телом for-понимания.

В вашем случае внешний тип — Set, а внутренний тип — тип k :: queens (то есть List[Int], потому что queens — это элемент из последовательности, возвращаемой placeQueens, то есть Set[List[Int]], а k::queens возвращает последовательность того же типа, что и queens .

person Ashalynd    schedule 25.10.2014