Scala 流 : how to avoid to keeping a reference to the head (and other elements)

Question

假设我有一个尾递归方法，它循环遍历 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;博士:您的方法 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只是方法 @tailrec 的第一个参数之前 foldLeft声明是有道理的。

现在我们终于可以理解 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你没有提到流的头部。