在Scala中实现'yield'的首选方法是什么？

Question

我正在为博士研究编写代码并开始使用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()的代码.BTW give()应命名为yield(),但Scala已经使用了该关键字.

我认为,由于我不理解的原因,Scala延续可能不适用于for语句.如果是这样,generate()应该提供一个尽可能接近for语句的等效函数,因为带有yield的迭代器代码几乎不可避免地位于for循环中.

请,我不希望得到以下任何答案:

1. '收益'很糟糕,延续更好.(是的,一般来说你可以用延续来做更多的事情.但是它们很难理解,99%的时候迭代器都是你想要的或者需要的.如果Scala提供了很多强大的工具但它们太难用了在实践中,语言不会成功.)
2. 这是重复的.(请参阅上面的评论.)
3. 您应该使用流,延续,递归等来重写代码.(请参阅#1.我还将添加,从技术上讲,您也不需要循环.就此而言,从技术上讲,您可以完成您所需要的一切使用SKI组合器.)
4. 你的功能太长了.将其分解成更小的部分,您将不需要"收益".无论如何,你必须在生产代码中这样做.(首先,"你不需要'收益'"在任何情况下都是值得怀疑的.其次,这不是生产代码.第三,对于像这样的文本处理,经常将功能分解成更小的部分 - 特别是当语言迫使你这样做,因为它缺乏有用的结构 - 只会使代码更难理解.)
5. 使用传入的函数重写代码.(从技术上讲,是的,你可以这样做.但结果不再是迭代器,链接迭代器比链接函数要好得多.一般来说,一种语言不应该强迫我写一个不自然的风格 - 当然,Scala创作者一般都相信这一点,因为它们提供了大量的语法糖.)
6. 用这个,那个或者其他方式重写你的代码,或者我想到的其他一些很酷的,令人敬畏的方式.

Answer 1

你的问题的前提似乎是你想要Python的收益率,并且你不希望任何其他合理的建议在Scala中以不同的方式做同样的事情.如果这是真的,那对你来说很重要,为什么不使用Python呢？这是一个很好的语言.除非你的博士学位 是在计算机科学,使用Scala是你论文的重要部分,如果你已经熟悉Python并且非常喜欢它的一些功能和设计选择,为什么不使用它呢？

无论如何,如果你真的想学习如何在Scala中解决你的问题,事实证明,对于你所拥有的代码,分隔的延续是过度的.您只需要flatMapped迭代器.

这是你如何做到的.

// 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

'收益'很糟糕,延续更好

实际上,Python 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下面的代码中有一个函数，因为yieldScala中已经有一个关键字了，顺便说一句，它与yieldPython 无关。

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")
}

编译该代码是因为生成器可以按s 序列进行分解yield，在这种情况下，a yield匹配延续中涉及的类型。更准确地说，可以将代码分解为链接的块，其中每个块都以a结尾yield。为了澄清起见，我们可以认为yields 的序列可以这样表示：

{ 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") }}}}

同样，无需深入探讨复杂的理论，重点是，在a之后，yield您需要提供另一个以a结尾的块yield，否则将其关闭。这是我们在上面的伪代码正在做的：在后yield，我们打开另一个块，在一个回合结束yield紧接着又yield其与另一回合结束yield，依此类推。显然，这件事必须在某个时候结束。然后，我们唯一可以做的就是关闭整个链。

好。但是...我们如何获得yield多条信息？答案有点晦涩难懂，但是在您知道答案之后便有很多道理：我们需要采用尾递归，并且块的最后一个语句必须是a 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从我们的字符串序列中获取多个信息。

3. 必须在使用之前声明递归函数，否则编译器将崩溃。

4. 递归函数tailrec提供了我们需要的尾递归。

经验法则很简单：如上所述，用递归函数代替for循环。

请注意，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)
} 

• 归功于Rich Dougherty和huynhjl。
  请参见此SO线程：使用Scala延续实现收益（收益回报） *

• 感谢Miles Sabin，他将上面的一些代码放在一起
  http://github.com/milessabin/scala-cont-jvm-coro-talk/blob/master/src/continuations/Generators.scala