В приведенной ниже реализации представлен Python-подобный генератор.
Обратите внимание, что в приведенном ниже коде есть функция с именем _yield, поскольку yield уже является ключевым словом в Scala, что, кстати, делаетне имеет ничего общего с yield, который вы знаете из Python.
import scala.annotation.tailrec
import scala.collection.immutable.Stream
import scala.util.continuations._
object Generators {
sealed trait Trampoline[+T]
case object Done extends Trampoline[Nothing]
case class Continue[T](result: T, next: Unit => Trampoline[T]) extends Trampoline[T]
class Generator[T](var cont: Unit => Trampoline[T]) extends Iterator[T] {
def next: T = {
cont() match {
case Continue(r, nextCont) => cont = nextCont; r
case _ => sys.error("Generator exhausted")
}
}
def hasNext = cont() != Done
}
type Gen[T] = cps[Trampoline[T]]
def generator[T](body: => Unit @Gen[T]): Generator[T] = {
new Generator((Unit) => reset { body; Done })
}
def _yield[T](t: T): Unit @Gen[T] =
shift { (cont: Unit => Trampoline[T]) => Continue(t, cont) }
}
object TestCase {
import Generators._
def sectors = generator {
def tailrec(seq: Seq[String]): Unit @Gen[String] = {
if (!seq.isEmpty) {
_yield(seq.head)
tailrec(seq.tail)
}
}
val list: Seq[String] = List("Financials", "Materials", "Technology", "Utilities")
tailrec(list)
}
def main(args: Array[String]): Unit = {
for (s <- sectors) { println(s) }
}
}
Он работает довольно хорошо, в том числе для типичного использования циклов for.
Предупреждение: мы должны помнить, чтоPython и Scala отличаются тем, как реализованы продолжения.Ниже мы видим, как генераторы обычно используются в Python, и сравниваем с тем, как мы должны использовать их в Scala.Затем мы увидим, почему так должно быть в Scala.
Если вы привыкли писать код на Python, вы, вероятно, использовали такие генераторы:
// This is Scala code that does not compile :(
// This code naively tries to mimic the way generators are used in Python
def myGenerator = generator {
val list: Seq[String] = List("Financials", "Materials", "Technology", "Utilities")
list foreach {s => _yield(s)}
}
Этокод выше не компилируется.Пропуская все замысловатые теоретические аспекты, объяснение таково: он не компилируется, потому что «тип цикла for» не соответствует типу, используемому как часть продолжения.Я боюсь, что это объяснение является полным провалом.Позвольте мне повторить попытку:
Если бы вы закодировали что-то вроде показанного ниже, оно скомпилировалось бы нормально:
def myGenerator = generator {
_yield("Financials")
_yield("Materials")
_yield("Technology")
_yield("Utilities")
}
Этот код компилируется, потому что генератор может быть разложенным последовательность yield с и, в этом случае, yield соответствует типу, задействованному в продолжении.Чтобы быть более точным, код может быть разложен на цепочечные блоки, где каждый блок заканчивается yield.Просто для пояснения, мы можем думать, что последовательность yield с может быть выражена следующим образом:
{ some code here; _yield("Financials")
{ some other code here; _yield("Materials")
{ eventually even some more code here; _yield("Technology")
{ ok, fine, youve got the idea, right?; _yield("Utilities") }}}}
Опять же, не вдаваясь в глубокие теории, смысл в том, что после yield вам нужно предоставить еще один блок, заканчивающийся yield, или иначе замкнуть цепочку.Это то, что мы делаем в псевдокоде выше: после yield мы открываем другой блок, который, в свою очередь, заканчивается yield, за которым следует еще один yield, который, в свою очередь, заканчивается еще одним yield, и такна.Очевидно, что эта вещь должна закончиться в какой-то момент.Тогда единственное, что нам разрешено сделать, - это закрыть всю цепочку.
ОК.Но ... как мы можем yield несколько частей информации?Ответ немного неясен, но имеет большой смысл после того, как вы знаете ответ: нам нужно использовать хвостовую рекурсию, и последнее утверждение блока должно быть yield.
def myGenerator = generator {
def tailrec(seq: Seq[String]): Unit @Gen[String] = {
if (!seq.isEmpty) {
_yield(seq.head)
tailrec(seq.tail)
}
}
val list = List("Financials", "Materials", "Technology", "Utilities")
tailrec(list)
}
Давайтепроанализируем, что здесь происходит:
Наша функция генератора myGenerator содержит некоторую логику, которая генерирует информацию.В этом примере мы просто используем последовательность строк.
Наша генераторная функция myGenerator вызывает рекурсивную функцию, которая отвечает за yield -изображение нескольких фрагментов информации, полученных изнаша последовательность строк.
Рекурсивная функция должна быть объявлена перед использованием , в противном случае компилятор падает.
рекурсивная функция tailrec обеспечивает необходимую нам хвостовую рекурсию.
Основное правило здесь простое: замените цикл на рекурсивную функцию, как показано выше.
Обратите внимание, что tailrec - это просто удобное имя, которое мы нашли, для пояснения.В частности, tailrec не обязательно должно быть последним утверждением нашей функции генератора;не обязательно.Единственное ограничение заключается в том, что вы должны предоставить последовательность блоков, которые соответствуют типу yield, как показано ниже:
def myGenerator = generator {
def tailrec(seq: Seq[String]): Unit @Gen[String] = {
if (!seq.isEmpty) {
_yield(seq.head)
tailrec(seq.tail)
}
}
_yield("Before the first call")
_yield("OK... not yet...")
_yield("Ready... steady... go")
val list = List("Financials", "Materials", "Technology", "Utilities")
tailrec(list)
_yield("done")
_yield("long life and prosperity")
}
На шаг вперед, вы должны представить, как выглядят реальные приложенияВ частности, если вы используете несколько генераторов.Было бы неплохо, если бы вы нашли способ стандартизировать ваших генераторов на основе единого шаблона, который в большинстве случаев удобен.
Давайте рассмотрим пример ниже. У нас есть три генератора: sectors, industries и companies. Для краткости, только sectors отображается полностью. Этот генератор использует функцию tailrec, как показано выше. Хитрость в том, что та же самая функция tailrec также используется другими генераторами. Все, что нам нужно сделать, это поставить другую функцию body.
type GenP = (NodeSeq, NodeSeq, NodeSeq)
type GenR = immutable.Map[String, String]
def tailrec(p: GenP)(body: GenP => GenR): Unit @Gen[GenR] = {
val (stats, rows, header) = p
if (!stats.isEmpty && !rows.isEmpty) {
val heads: GenP = (stats.head, rows.head, header)
val tails: GenP = (stats.tail, rows.tail, header)
_yield(body(heads))
// tail recursion
tailrec(tails)(body)
}
}
def sectors = generator[GenR] {
def body(p: GenP): GenR = {
// unpack arguments
val stat, row, header = p
// obtain name and url
val name = (row \ "a").text
val url = (row \ "a" \ "@href").text
// create map and populate fields: name and url
var m = new scala.collection.mutable.HashMap[String, String]
m.put("name", name)
m.put("url", url)
// populate other fields
(header, stat).zipped.foreach { (k, v) => m.put(k.text, v.text) }
// returns a map
m
}
val root : scala.xml.NodeSeq = cache.loadHTML5(urlSectors) // obtain entire page
val header: scala.xml.NodeSeq = ... // code is omitted
val stats : scala.xml.NodeSeq = ... // code is omitted
val rows : scala.xml.NodeSeq = ... // code is omitted
// tail recursion
tailrec((stats, rows, header))(body)
}
def industries(sector: String) = generator[GenR] {
def body(p: GenP): GenR = {
//++ similar to 'body' demonstrated in "sectors"
// returns a map
m
}
//++ obtain NodeSeq variables, like demonstrated in "sectors"
// tail recursion
tailrec((stats, rows, header))(body)
}
def companies(sector: String) = generator[GenR] {
def body(p: GenP): GenR = {
//++ similar to 'body' demonstrated in "sectors"
// returns a map
m
}
//++ obtain NodeSeq variables, like demonstrated in "sectors"
// tail recursion
tailrec((stats, rows, header))(body)
}