Scala equivalent to Python generators?


Question

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

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, foo may be more complex and recurs through some acyclic object graph.

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/reset concept. Will continuation eventually make it into the main compiler and would it be possible to extract out the complexity in a library?

Edit 2: check Rich's answer in that other thread.

1
54
5/23/2017 12:26:23 PM

Accepted Answer

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:

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 Iterator simply by calling .iterator on the resulting Stream:

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

The foo definition, using Stream, would be rendered thus:

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.

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.

33
6/30/2016 11:57:25 PM

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

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

Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon