Scala эквивалентен генераторам Python?
Можно ли реализовать в Scala что-то эквивалентное оператору Python yield, где он запоминает локальное состояние функции, где оно используется, и "дает" следующее значение при каждом его вызове?
Я хотел иметь что-то вроде этого, чтобы преобразовать рекурсивную функцию в итератор. Пример:
# 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
Кроме того, foo может быть более сложным и повторяется через некоторый ациклический граф объекта.
Дополнительное редактирование:
Позвольте мне добавить более сложный пример (но все же простой):
Я могу написать простую рекурсивную функцию печати, когда она идет:
// 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 + " ")
}
}
}
В идеале я хотел бы иметь библиотеку, которая позволяет мне легко изменять несколько утверждений и работать как 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
}
}
Кажется, продолжения позволяют это сделать, но я просто не понимаю концепцию shift/reset. Будет ли продолжение в конечном итоге превращаться в основной компилятор и можно ли извлечь сложность в библиотеке?
Изменить 2:
Богатый ответ в этом другом потоке.
Ответы
Ответ 1
В то время как генераторы 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
)
}
В нем поток генерируется лениво, поэтому он не будет обрабатывать какие-либо элементы до тех пор, пока их не попросят, которые вы можете проверить, выполнив это:
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
)
}
Результат может быть преобразован в Iterator просто путем вызова .iterator в результирующем Stream:
def classIterator(clazz: Class[_]): Iterator[Class[_]] = classStream(clazz).iterator
Определение foo, используя 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
Другой альтернативой было бы объединение различных итераторов, стараясь не предварительно вычислить их. Вот пример, также с отладкой сообщений, чтобы помочь выполнить трассировку:
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
}
Это довольно близко к вашему коду. Вместо sudoYield у меня есть определения, а затем я просто конкатенирую их по своему желанию.
Итак, пока это не ответ, я просто думаю, что вы лаем по неправильному дереву здесь. Попытка написать Python в Scala должна быть непродуктивной. Усиляйтесь в Scala идиомах, которые достигают тех же целей.
Ответ 2
Другое решение на основе плагинов продолжения, на этот раз с более или менее инкапсулированным типом генератора,
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)
}
}
}
}
Ответ 3
Чтобы сделать это в общем, я думаю, вам нужен плагин продолжения.
Наивная реализация (от руки, не скомпилированная/проверенная):
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()
}
Случается, что любой вызов shift захватывает поток управления, из которого он вызывается в конец блока reset, в который он вызывается. Он передается как аргумент k в сдвиг функция.
Итак, в приведенном выше примере каждый giveItUp(x) возвращает значение x (вплоть до этой точки) и сохраняет остальную часть вычисления в переменной state. Он запускается извне методами hasNext и next.
Пойдите нежно, это, очевидно, ужасный способ реализовать это. Но лучше всего я мог сделать позднюю ночь без компилятора.
Ответ 4
Scala for-loop формы for (e <- Producer) f(e) преобразуется в вызов foreach, а не непосредственно в iterator/next.
В foreach нам не нужно линеаризовать создания объектов и иметь их в одном месте, так как это необходимо для iterator next. Потребительская функция f может быть вставлена несколько раз, именно там, где это необходимо (т.е. Где создается объект).
Это делает реализацию прецедентов для генераторов простой и эффективной с помощью Traversable/foreach в Scala.
Исходный пример 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
Исходный пример printClass:
// 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
Или с отступом:
// 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
Вывод:
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
