Scala Streams:如何避免保持对头部(和其他元素)的引用

Question

假设我有一个循环遍历a元素的尾递归方法Stream,就像这样(简化代码,未测试):

@tailrec
def loop(s: Stream[X], acc: Y): Y = 
  s.headOption match {
    case None => acc
    case Some(x) => loop(s.tail, accumulate(x, acc))
  }

在迭代时我是否保持对流的头部(以及所有其他元素)的引用,我知道应该避免这种情况吗？如果是这样,那么实现同样的事情的更好方法是什么？

调用它的代码是(我希望)不保留引用.假设list是List[X]代码正在调用

loop(list.sliding(n).toStream, initialY)

编辑:我知道这可以很容易地做到没有尾递归(例如使用foldLeft)但非简化代码不是一次只循环一个元素(有时s使用而不是s.tail有时s.tail.dropWhile(...)使用.所以我想找出来如何正确使用Stream.

Answer 1

tl; dr:你的方法loop是正确的,没有引用流的头部.你可以无限测试它Stream.

让我们将代码示例简化为极限:

class Test {
  private[this] var next: Test = _

  final def fold(): Int = {
    next = new Test
    next.fold()
  }
}

请注意,您的loop方法也是某个对象的方法.

方法是final(就像Stream#foldLeft) - 这非常重要.

通过scalac -Xprint:all test.scala尾递归优化,你会得到这个:

final def fold(): Int = {
  <synthetic> val _$this: Test = Test.this;
  _fold(_$this: Test){
    ({
      Test.this.next = new Test();
      _fold(Test.this.next)
    }: Int)
  }
};

此代码不会帮助您了解正在发生的事情.

通往神奇理解之地的唯一途径是java字节码.

但你应该记住一件事:没有这样的事情method of object.所有方法都是"静态的".并且this只是该方法的第一个参数.如果方法是虚拟的,那就是vtable,但我们的方法是final,所以在这种情况下不会有动态调度.

还要注意,没有参数这样的东西:所有参数都只是变量,在方法执行之前初始化.

所以this这只是方法的第一个变量(索引0).

我们来看看字节码(javap -c Test.class):

public final int fold();
  Code:
     0: aload_0       
     1: new           #2                  // class Test
     4: dup           
     5: invokespecial #16                 // Method "<init>":()V
     8: putfield      #18                 // Field next:LTest;
    11: aload_0       
    12: getfield      #18                 // Field next:LTest;
    15: astore_0      
    16: goto          0

让我们用伪scala代码编写这个方法:

static foo(var this: Test): Int {
  :start // label for goto jump

  // place variable `this` onto the stack:
  //   0: aload_0       

  // create new `Test`
  //   1: new           #2                  // class Test
  // invoke `Test` constructor
  //   4: dup           
  //   5: invokespecial #16                 // Method "<init>":()V

  // assign `this.next` field value
  //   8: putfield      #18                 // Field next:LTest;

  this.next = new Test

  // place `this.next` onto the stack
  //  11: aload_0       
  //  12: getfield      #18                 // Field next:LTest;

  // assign `this.next` to variable `this`!
  //  15: astore_0      
  this = this.next // we have no reference to the previous `this`!

  //  16: goto          0
  goto :start
}

在this = this.next我们没有引用前一个this堆栈或第一个变量之后.以前this可以删除GC!

因此,tail.foldLeft(...)在Stream#foldLeft将被替换this = this.tail, ...; goto :start.并且因为在宣言有意义之前,this这只是方法的第一个论点.@tailrecfoldLeft

现在我们终于可以理解scalac -Xprint:all test.scala结果:

final def method(a: A, b: B, ...): Res = {
  <synthetic> val _$this: ThisType = ThisType.this;
  _method(_$this: Test, a: A, b: B, ...){
    ({
      // body
      _method(nextThis, nextA, nextB, ...)
    }: Res)
  }
};

手段:

final def method(var this: ThisType, var a: A, var b: B, ...): Res = {
  // _method(_$this: Test, a: A, b: B, ...){
  :start

  // body

  //   _method(nextThis, nextA, nextB, ...)
  this = nextThis
  a = nextA
  b = nextB
  ...
  goto :start
};

这正是scalac -Xprint:all你的loop方法body所能得到的,但是会很大.所以在你的情况下:

...
case Some(x) =>
  this = this
  s = s.tail
  acc = accumulate(x, acc)
  goto :start
...

在s = s.tail您没有引用流的头部之后.