Каков предпочтительный способ реализации "yield" в Scala?

Question

Я пишу код для исследования PhD и начинаю использовать Scala. Мне часто приходится заниматься обработкой текста. Я привык к Python, чей оператор yield очень полезен для реализации сложных итераторов над большими, часто нерегулярно структурированными текстовыми файлами. Подобные конструкции существуют в других языках (например, C#), по уважительной причине.

Да, я знаю, что были предыдущие темы по этому вопросу. Но они выглядят как взломанные (или, по крайней мере, плохо объясненные) решения, которые явно не работают хорошо и часто имеют неясные ограничения. Я хотел бы написать код примерно так:

import generator._

def yield_values(file:String) = {
  generate {
    for (x <- Source.fromFile(file).getLines()) {
      # Scala is already using the 'yield' keyword.
      give("something")
      for (field <- ":".r.split(x)) {
        if (field contains "/") {
          for (subfield <- "/".r.split(field)) { give(subfield) }
        } else {
          // Scala has no 'continue'.  IMO that should be considered
          // a bug in Scala.
          // Preferred: if (field.startsWith("#")) continue
          // Actual: Need to indent all following code
          if (!field.startsWith("#")) {
            val some_calculation = { ... do some more stuff here ... }
            if (some_calculation && field.startsWith("r")) {
              give("r")
              give(field.slice(1))
            } else {
              // Typically there will be a good deal more code here to handle different cases
              give(field)
            }
          }
        }
      }
    }
  }
}

Я хотел бы увидеть код, который реализует generate() и give(). Кстати, give () должно называться yield(), но Scala уже взяла это ключевое слово.

Я понимаю, что по причинам, которые я не понимаю, продолжения Scala могут не работать внутри оператора for. Если это так, generate() должен предоставить эквивалентную функцию, которая работает как можно ближе к оператору for, потому что код итератора с yield почти неизбежно находится внутри цикла for.

Пожалуйста, я бы предпочел не получать ни одного из следующих ответов:

1. 'yield' отстой, продолжения лучше. (Да, в целом вы можете сделать больше с продолжениями. Но их трудно понять, и 99% времени - итератор - это все, что вам нужно или нужно. Если Scala предоставляет множество мощных инструментов, но их слишком сложно использовать на практике язык не получится.)
2. Это дубликат. (Пожалуйста, смотрите мои комментарии выше.)
3. Вы должны переписать свой код, используя потоки, продолжения, рекурсию и т. Д. И т. Д. (Пожалуйста, смотрите #1. Я также добавлю, технически вам также не нужны циклы. В этом отношении, технически вы можете сделать абсолютно все, что вам когда-либо понадобится). используя комбинаторы SKI.)
4. Ваша функция слишком длинная. Разбейте его на более мелкие кусочки, и вам не понадобится "доходность". В любом случае вам придется делать это в рабочем коде. (Во-первых, "вам не понадобится" yield "" в любом случае сомнительно. Во-вторых, это не рабочий код. В-третьих, для такой обработки текста очень часто разбивают функцию на более мелкие фрагменты - особенно когда язык заставляет вас делать это, потому что ему не хватает полезных конструкций - только делает код труднее для понимания.)
5. Перепишите ваш код с помощью переданной функции. (Технически, да, вы можете сделать это. Но результат больше не является итератором, и цепочка итераторов гораздо лучше, чем цепочка функций. В общем, язык не должен заставлять меня писать в неестественный стиль - конечно, создатели Scala верят этому в целом, так как они предоставляют кучу синтаксического сахара.)
6. Перепишите свой код тем или иным способом, или каким-нибудь другим классным, удивительным способом, о котором я только что подумал.

Answer 1

Предположительно, ваш вопрос заключается в том, что вам нужен именно доход Python, и вы не хотите, чтобы другие разумные предложения делали то же самое по-другому в Scala. Если это так, и это так важно для вас, почему бы не использовать Python? Это довольно хороший язык. Если только ваш доктор философии в области компьютерных наук, и использование Scala является важной частью вашей диссертации, если вы уже знакомы с Python и действительно любите некоторые его функции и варианты дизайна, почему бы не использовать его вместо этого?

В любом случае, если вы действительно хотите узнать, как решить свою проблему в Scala, оказывается, что для кода, который вы имеете, продолжения с разделителями являются излишними. Все, что вам нужно, это плоские итераторы.

Вот как ты это делаешь.

// You want to write
for (x <- xs) { /* complex yield in here */ }
// Instead you write
xs.iterator.flatMap { /* Produce iterators in here */ }

// You want to write
yield(a)
yield(b)
// Instead you write
Iterator(a,b)

// You want to write
yield(a)
/* complex set of yields in here */
// Instead you write
Iterator(a) ++ /* produce complex iterator here */

Это оно! Все ваши дела могут быть сведены к одному из этих трех.

В вашем случае ваш пример будет выглядеть примерно так

Source.fromFile(file).getLines().flatMap(x =>
  Iterator("something") ++
  ":".r.split(x).iterator.flatMap(field =>
    if (field contains "/") "/".r.split(field).iterator
    else {
      if (!field.startsWith("#")) {
        /* vals, whatever */
        if (some_calculation && field.startsWith("r")) Iterator("r",field.slice(1))
        else Iterator(field)
      }
      else Iterator.empty
    }
  )
)

PS Scala имеет продолжение; это делается так (реализуется с помощью исключения без стека (облегченного)):

import scala.util.control.Breaks._
for (blah) { breakable { ... break ... } }

но это не даст вам того, чего вы хотите, потому что у Scala нет той доходности, которую вы хотите.

Answer 2

'yield' отстой, лучше продолжения

На самом деле, Питон yield это продолжение.

Что такое продолжение? Продолжение сохраняет текущую точку выполнения со всем ее состоянием, так что можно продолжить в этой точке позже. Это именно то, что Python yield, а также, как именно это реализовано.

Однако я понимаю, что продолжения Python не ограничены. Я не знаю много об этом - на самом деле я могу ошибаться. Я также не знаю, каковы могут быть последствия этого.

Продолжение Scala не работает во время выполнения - на самом деле есть библиотека продолжений для Java, которая работает, выполняя что-то для байт-кода во время выполнения, что не связано с ограничениями, которые имеет продолжение Scala.

Продолжение Scala полностью выполняется во время компиляции, что требует немало работы. Для этого также требуется, чтобы компилятор подготовил код, который будет "продолжен".

И именно поэтому для понимания не работают. Утверждение как это:

for { x <- xs } proc(x)

Если перевести на

xs.foreach(x => proc(x))

куда foreach это метод на xs Класс. К несчастью, xs Класс уже давно скомпилирован, поэтому его нельзя изменить для поддержки продолжения. Как примечание, это также, почему Scala не имеет continue,

Помимо этого, да, это дублирующий вопрос, и, да, вы должны найти другой способ написания своего кода.

Answer 3

Реализация ниже обеспечивает 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)
  }

Давайте проанализируем, что здесь происходит:

1. Наша функция генератора myGenerator содержит некоторую логику, которая генерирует информацию. В этом примере мы просто используем последовательность строк.

2. Наша функция генератора myGenerator вызывает рекурсивную функцию, которая отвечает за yield-ing несколько частей информации, полученных из нашей последовательности строк.

3. Рекурсивная функция должна быть объявлена ​​перед использованием, в противном случае компилятор падает.

4. Рекурсивная функция 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)
} 

• Кредиты Ричу Догерти и Хуйнхлю.
  Смотрите эту ветку SO: Реализация yield (yield return) с использованием продолжений Scala*

• Кредиты Майлзу Сабину за то, что они собрали часть кода выше
  http://github.com/milessabin/scala-cont-jvm-coro-talk/blob/master/src/continuations/Generators.scala