Scala 相当于 Python 生成器？

Scala equivalent to Python generators?

提问by huynhjl

Is it possible to implement in Scala something equivalent to the Python yieldstatement where it remembers the local state of the function where it is used and "yields" the next value each time it is called?

是否有可能在 Scala 中实现与 Pythonyield语句等效的东西，它会记住使用它的函数的本地状态，并在每次调用时“产生”下一个值？

I wanted to have something like this to convert a recursive function into an iterator. Sort of like this:

我想有这样的东西来将递归函数转换为迭代器。有点像这样：

# this is python
def foo(i):
  yield i
  if i > 0:
    for j in foo(i - 1):
      yield j

for i in foo(5):
  print i

Except, foomay be more complex and recurs through some acyclic object graph.

除了，foo可能更复杂并通过一些非循环对象图递归。

Additional Edit:Let me add a more complex example (but still simple): I can write a simple recursive function printing things as it goes along:

附加编辑：让我添加一个更复杂的示例（但仍然很简单）：我可以编写一个简单的递归函数来打印内容：

// this is Scala
def printClass(clazz:Class[_], indent:String=""): Unit = {
  clazz match {
    case null =>
    case _ =>
      println(indent + clazz)
      printClass(clazz.getSuperclass, indent + "  ")
      for (c <- clazz.getInterfaces) {
        printClass(c, indent + "  ")
      }
  }
}

Ideally I would like to have a library that allows me to easily change a few statements and have it work as an Iterator:

理想情况下，我希望有一个库，可以让我轻松更改一些语句并将其用作迭代器：

// this is not Scala
def yieldClass(clazz:Class[_]): Iterator[Class[_]] = {
  clazz match {
    case null =>
    case _ =>
      sudoYield clazz
      for (c <- yieldClass(clazz.getSuperclass)) sudoYield c
      for (c <- clazz.getInterfaces; d <- yieldClasss(c)) sudoYield d
  }
}

It does seem continuations allow to do that, but I just don't understand the shift/resetconcept. Will continuation eventually make it into the main compiler and would it be possible to extract out the complexity in a library?

似乎延续允许这样做，但我只是不明白这个shift/reset概念。延续最终会进入主编译器，是否有可能提取出库中的复杂性？

Edit 2:check Rich's answerin that other thread.

编辑 2：在其他线程中 检查Rich 的回答。

采纳答案by Daniel C. Sobral

While Python generators are cool, trying to duplicate them really isn't the best way to go about in Scala. For instance, the following code does the equivalent job to what you want:

虽然 Python 生成器很酷，但在 Scala 中尝试复制它们确实不是最好的方法。例如，下面的代码可以完成与您想要的等效的工作：

def classStream(clazz: Class[_]): Stream[Class[_]] = clazz match {
  case null => Stream.empty
  case _ => (
    clazz 
    #:: classStream(clazz.getSuperclass) 
    #::: clazz.getInterfaces.toStream.flatMap(classStream) 
    #::: Stream.empty
  )
}

In it the stream is generated lazily, so it won't process any of the elements until asked for, which you can verify by running this:

在其中，流是惰性生成的，因此在请求之前它不会处理任何元素，您可以通过运行以下命令进行验证：

def classStream(clazz: Class[_]): Stream[Class[_]] = clazz match {
  case null => Stream.empty
  case _ => (
    clazz 
    #:: { println(clazz.toString+": super"); classStream(clazz.getSuperclass) } 
    #::: { println(clazz.toString+": interfaces"); clazz.getInterfaces.toStream.flatMap(classStream) } 
    #::: Stream.empty
  )
}

The result can be converted into an Iteratorsimply by calling .iteratoron the resulting Stream:

结果可以被转换成Iterator简单地通过调用.iterator对所得Stream：

def classIterator(clazz: Class[_]): Iterator[Class[_]] = classStream(clazz).iterator

The foodefinition, using Stream, would be rendered thus:

foousing的定义Stream将呈现为：

scala> def foo(i: Int): Stream[Int] = i #:: (if (i > 0) foo(i - 1) else Stream.empty)
foo: (i: Int)Stream[Int]

scala> foo(5) foreach println
5
4
3
2
1
0

Another alternative would be concatenating the various iterators, taking care to not pre-compute them. Here's an example, also with debugging messages to help trace the execution:

另一种选择是连接各种迭代器，注意不要预先计算它们。这是一个示例，还带有调试消息以帮助跟踪执行：

def yieldClass(clazz: Class[_]): Iterator[Class[_]] = clazz match {
  case null => println("empty"); Iterator.empty
  case _ =>
    def thisIterator = { println("self of "+clazz); Iterator(clazz) }
    def superIterator = { println("super of "+clazz); yieldClass(clazz.getSuperclass) }
    def interfacesIterator = { println("interfaces of "+clazz); clazz.getInterfaces.iterator flatMap yieldClass }
    thisIterator ++ superIterator ++ interfacesIterator
}

This is pretty close to your code. Instead of sudoYield, I have definitions, and then I just concatenate them as I wish.

这与您的代码非常接近。而不是sudoYield，我有定义，然后我只是按照我的意愿连接它们。

So, while this is a non-answer, I just think you are barking up the wrong tree here. Trying to write Python in Scala is bound to be unproductive. Work harder at the Scala idioms that accomplish the same goals.

所以，虽然这是一个非答案，但我只是认为你在这里吠错了树。尝试在 Scala 中编写 Python 注定是徒劳的。在实现相同目标的 Scala 习语上更加努力。

回答by Miles Sabin

Another continuations plugin based solution, this time with a more or less encapsulated Generator type,

另一个基于 continuation 插件的解决方案，这次或多或少封装了 Generator 类型，

import scala.continuations._
import scala.continuations.ControlContext._

object Test {

  def loopWhile(cond: =>Boolean)(body: =>(Unit @suspendable)): Unit @suspendable = {
    if (cond) {
      body
      loopWhile(cond)(body)
    } else ()
  }

  abstract class Generator[T] {
    var producerCont : (Unit => Unit) = null
    var consumerCont : (T => Unit) = null

    protected def body : Unit @suspendable

    reset {
      body
    }

    def generate(t : T) : Unit @suspendable =
      shift {
        (k : Unit => Unit) => {
          producerCont = k
          if (consumerCont != null)
            consumerCont(t)
        }
      }

    def next : T @suspendable =
      shift {
        (k : T => Unit) => {
          consumerCont = k
          if (producerCont != null)
            producerCont()
        }
      }
  }

  def main(args: Array[String]) {
    val g = new Generator[Int] {
      def body = {
        var i = 0
        loopWhile(i < 10) {
          generate(i)
          i += 1
        }
      }
    }

    reset {
      loopWhile(true) {
        println("Generated: "+g.next)
      }
    }
  }
}

回答by Eugen Labun

Scala's for-loop of the form for (e <- Producer) f(e)translates into a foreachcall, and not directly into iterator/ next.

Scala 的 for 循环形式for (e <- Producer) f(e)转换为foreach调用，而不是直接转换为iterator/ next。

In the foreachwe don't need to linearize objects' creations and have them in one place, as it would be needed for iterator's next. The consumer-function fcan be inserted multiple times, exactly where it is needed (i.e. where an object is created).

在 中，foreach我们不需要线性化对象的创建并将它们放在一个地方，因为迭代器的next. 消费者函数f可以多次插入，正好在需要的地方（即创建对象的地方）。

This makes implementation of use cases for generators simple and efficient with Traversable/ foreachin Scala.

这使得在 Scala 中使用Traversable/实现生成器的用例变得简单而高效foreach。

---

---

The initial Foo-example:

最初的 Foo 示例：

case class Countdown(start: Int) extends Traversable[Int] {
    def foreach[U](f: Int => U) {
        var j = start
        while (j >= 0) {f(j); j -= 1}
    }
}

for (i <- Countdown(5))  println(i)
// or equivalent:
Countdown(5) foreach println

---

---

The initial printClass-example:

最初的printClass-example：

  // v1 (without indentation)

  case class ClassStructure(c: Class[_]) {
    def foreach[U](f: Class[_] => U) {
      if (c eq null) return
      f(c)
      ClassStructure(c.getSuperclass) foreach f
      c.getInterfaces foreach (ClassStructure(_) foreach f)
    }
  }

  for (c <- ClassStructure(<foo/>.getClass)) println(c)
  // or equivalent:
  ClassStructure(<foo/>.getClass) foreach println

Or with indentation:

或缩进：

  // v2 (with indentation)

  case class ClassWithIndent(c: Class[_], indent: String = "") {
    override def toString = indent + c
  }
  implicit def Class2WithIndent(c: Class[_]) = ClassWithIndent(c)

  case class ClassStructure(cwi: ClassWithIndent) {
    def foreach[U](f: ClassWithIndent => U) {
      if (cwi.c eq null) return
      f(cwi)
      ClassStructure(ClassWithIndent(cwi.c.getSuperclass, cwi.indent + "  ")) foreach f
      cwi.c.getInterfaces foreach (i => ClassStructure(ClassWithIndent(i, cwi.indent + "  ")) foreach f)
    }
  }

  for (c <- ClassStructure(<foo/>.getClass)) println(c)
  // or equivalent:
  ClassStructure(<foo/>.getClass) foreach println

Output:

输出：

class scala.xml.Elem
  class scala.xml.Node
    class scala.xml.NodeSeq
      class java.lang.Object
      interface scala.collection.immutable.Seq
        interface scala.collection.immutable.Iterable
          interface scala.collection.immutable.Traversable
            interface scala.collection.Traversable
              interface scala.collection.TraversableLike
                interface scala.collection.generic.HasNewBuilder
                interface scala.collection.generic.FilterMonadic
                interface scala.collection.TraversableOnce
                  interface scala.ScalaObject
                interface scala.ScalaObject
              interface scala.collection.generic.GenericTraversableTemplate
                interface scala.collection.generic.HasNewBuilder
                interface scala.ScalaObject
              interface scala.ScalaObject
            interface scala.collection.generic.GenericTraversableTemplate
              interface scala.collection.generic.HasNewBuilder
              interface scala.ScalaObject
            interface scala.collection.TraversableLike
              interface scala.collection.generic.HasNewBuilder
              interface scala.collection.generic.FilterMonadic
              interface scala.collection.TraversableOnce
                interface scala.ScalaObject
              interface scala.ScalaObject
            interface scala.Immutable
            interface scala.ScalaObject
          interface scala.collection.Iterable
            interface scala.collection.Traversable
              interface scala.collection.TraversableLike
                interface scala.collection.generic.HasNewBuilder
                interface scala.collection.generic.FilterMonadic
                interface scala.collection.TraversableOnce
                  interface scala.ScalaObject
                interface scala.ScalaObject
              interface scala.collection.generic.GenericTraversableTemplate
                interface scala.collection.generic.HasNewBuilder
                interface scala.ScalaObject
              interface scala.ScalaObject
            interface scala.collection.generic.GenericTraversableTemplate
              interface scala.collection.generic.HasNewBuilder
              interface scala.ScalaObject
            interface scala.collection.IterableLike
              interface scala.Equals
              interface scala.collection.TraversableLike
                interface scala.collection.generic.HasNewBuilder
                interface scala.collection.generic.FilterMonadic
                interface scala.collection.TraversableOnce
                  interface scala.ScalaObject
                interface scala.ScalaObject
              interface scala.ScalaObject
            interface scala.ScalaObject
          interface scala.collection.generic.GenericTraversableTemplate
            interface scala.collection.generic.HasNewBuilder
            interface scala.ScalaObject
          interface scala.collection.IterableLike
            interface scala.Equals
            interface scala.collection.TraversableLike
              interface scala.collection.generic.HasNewBuilder
              interface scala.collection.generic.FilterMonadic
              interface scala.collection.TraversableOnce
                interface scala.ScalaObject
              interface scala.ScalaObject
            interface scala.ScalaObject
          interface scala.ScalaObject
        interface scala.collection.Seq
          interface scala.PartialFunction
            interface scala.Function1
              interface scala.ScalaObject
            interface scala.ScalaObject
          interface scala.collection.Iterable
            interface scala.collection.Traversable
              interface scala.collection.TraversableLike
                interface scala.collection.generic.HasNewBuilder
                interface scala.collection.generic.FilterMonadic
                interface scala.collection.TraversableOnce
                  interface scala.ScalaObject
                interface scala.ScalaObject
              interface scala.collection.generic.GenericTraversableTemplate
                interface scala.collection.generic.HasNewBuilder
                interface scala.ScalaObject
              interface scala.ScalaObject
            interface scala.collection.generic.GenericTraversableTemplate
              interface scala.collection.generic.HasNewBuilder
              interface scala.ScalaObject
            interface scala.collection.IterableLike
              interface scala.Equals
              interface scala.collection.TraversableLike
                interface scala.collection.generic.HasNewBuilder
                interface scala.collection.generic.FilterMonadic
                interface scala.collection.TraversableOnce
                  interface scala.ScalaObject
                interface scala.ScalaObject
              interface scala.ScalaObject
            interface scala.ScalaObject
          interface scala.collection.generic.GenericTraversableTemplate
            interface scala.collection.generic.HasNewBuilder
            interface scala.ScalaObject
          interface scala.collection.SeqLike
            interface scala.collection.IterableLike
              interface scala.Equals
              interface scala.collection.TraversableLike
                interface scala.collection.generic.HasNewBuilder
                interface scala.collection.generic.FilterMonadic
                interface scala.collection.TraversableOnce
                  interface scala.ScalaObject
                interface scala.ScalaObject
              interface scala.ScalaObject
            interface scala.ScalaObject
          interface scala.ScalaObject
        interface scala.collection.generic.GenericTraversableTemplate
          interface scala.collection.generic.HasNewBuilder
          interface scala.ScalaObject
        interface scala.collection.SeqLike
          interface scala.collection.IterableLike
            interface scala.Equals
            interface scala.collection.TraversableLike
              interface scala.collection.generic.HasNewBuilder
              interface scala.collection.generic.FilterMonadic
              interface scala.collection.TraversableOnce
                interface scala.ScalaObject
              interface scala.ScalaObject
            interface scala.ScalaObject
          interface scala.ScalaObject
        interface scala.ScalaObject
      interface scala.collection.SeqLike
        interface scala.collection.IterableLike
          interface scala.Equals
          interface scala.collection.TraversableLike
            interface scala.collection.generic.HasNewBuilder
            interface scala.collection.generic.FilterMonadic
            interface scala.collection.TraversableOnce
              interface scala.ScalaObject
            interface scala.ScalaObject
          interface scala.ScalaObject
        interface scala.ScalaObject
      interface scala.xml.Equality
        interface scala.Equals
        interface scala.ScalaObject
      interface scala.ScalaObject
    interface scala.ScalaObject
  interface scala.ScalaObject
  interface java.io.Serializable

回答by Mitch Blevins

To do this in a general way, I think you need the continuations plugin.

要以一般方式执行此操作，我认为您需要continuations 插件。

A naive implementation (freehand, not compiled/checked):

一个天真的实现（徒手，未编译/检查）：

def iterator = new {
  private[this] var done = false

  // Define your yielding state here
  // This generator yields: 3, 13, 0, 1, 3, 6, 26, 27
  private[this] var state: Unit=>Int = reset {
    var x = 3
    giveItUp(x)
    x += 10
    giveItUp(x)
    x = 0
    giveItUp(x)
    List(1,2,3).foreach { i => x += i; giveItUp(x) }
    x += 20
    giveItUp(x)
    x += 1
    done = true
    x
  }

  // Well, "yield" is a keyword, so how about giveItUp?
  private[this] def giveItUp(i: Int) = shift { k: (Unit=>Int) =>
    state = k
    i
  }

  def hasNext = !done
  def next = state()
}

What is happening is that any call to shiftcaptures the control flow from where it is called to the end of the resetblock that it is called in. This is passed as the kargument into the shift function.

发生的事情是任何调用都shift捕获控制流，从它被调用的地方到它被调用的reset块的末尾。这作为k参数传递给 shift 函数。

So, in the example above, each giveItUp(x)returns the value of x(up to that point) and saves the rest of the computation in the statevariable. It is driven from outside by the hasNextand nextmethods.

因此，在上面的示例中，每个都giveItUp(x)返回x（到该点为止）的值并将计算的其余部分保存在state变量中。它是由hasNext和next方法从外部驱动的。

Go gentle, this is obviously a terrible way to implement this. But it best I could do late at night without a compiler handy.

温和一点，这显然是一种糟糕的实现方式。但最好我可以在没有编译器的情况下在深夜完成。

回答by Yang Bo

Dsl.scalais what you are looking for.

dsl.scala就是你要找的。

Suppose you want to create a random number generator. The generated numbers should be stored in a lazily evaluated infinite stream, which can be built with the help of our built-in domain-specific keyword Yield.

假设您要创建一个随机数生成器。生成的数字应该存储在一个惰性求值的无限流中，这可以在我们内置的特定于域的关键字的帮助下构建Yield。

import com.thoughtworks.dsl.keys.Yield
def xorshiftRandomGenerator(seed: Int): Stream[Int] = {
  val tmp1 = seed ^ (seed << 13)
  val tmp2 = tmp1 ^ (tmp1 >>> 17)
  val tmp3 = tmp2 ^ (tmp2 << 5)
  !Yield(tmp3)
  xorshiftRandomGenerator(tmp3)
}

Other examples can be found in the Scaladoc.

其他示例可以在Scaladoc 中找到。