scala - 整数对的尾递归有界流(Scala)？

Question

我对 Scala 很陌生，所以请原谅我的无知!我正在尝试迭代受最大值限制的整数对。例如，如果最大值为 5，则迭代应返回:

(0, 0), (0, 1), ..., (0, 5), (1, 0), ..., (5, 5)

我选择尝试尾递归地将其作为流返回:

    @tailrec
    def _pairs(i: Int, j: Int, maximum: Int): Stream[(Int, Int)] = {
        if (i == maximum && j == maximum) Stream.empty
        else if (j == maximum) (i, j) #:: _pairs(i + 1, 0, maximum)
        else (i, j) #:: _pairs(i, j + 1, maximum)
    }

没有 tailrec 注释，代码可以正常工作:

scala> _pairs(0, 0, 5).take(11)
res16: scala.collection.immutable.Stream[(Int, Int)] = Stream((0,0), ?)

scala> _pairs(0, 0, 5).take(11).toList
res17: List[(Int, Int)] = List((0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (1,0), (1,1), (1,2), (1,3), (1,4))

但这对我来说还不够好。编译器正确指出 _pairs 的最后一行没有返回 _pairs:

could not optimize @tailrec annotated method _pairs: it contains a recursive call not in tail position
    else (i, j) #:: _pairs(i, j + 1, maximum)
                ^

所以，我有几个问题:

• 直接解决上面的实现，如何尾递归返回 Stream[(Int, Int)]？
• 退后一步，迭代有界整数序列的最节省内存的方法是什么？我不想迭代 Range 因为 Range extends IndexedSeq ，并且我不希望该序列完全存在于内存中。还是我错了？如果我迭代 Range.view 是否可以避免它进入内存？

在Python(!)中，我想要的是:

In [6]: def _pairs(maximum):
   ...:     for i in xrange(maximum+1):
   ...:         for j in xrange(maximum+1):
   ...:             yield (i, j)
   ...:             

In [7]: p = _pairs(5)

In [8]: [p.next() for i in xrange(11)]
Out[8]: 
[(0, 0),
 (0, 1),
 (0, 2),
 (0, 3),
 (0, 4),
 (0, 5),
 (1, 0),
 (1, 1),
 (1, 2),
 (1, 3),
 (1, 4)]

感谢您的帮助!如果您认为我需要阅读引用资料/API 文档/其他任何内容，请告诉我，因为我渴望学习。

Answer 1

这不是尾递归

假设您正在创建一个列表而不是一个流:(让我用一个更简单的函数来表达我的观点)

def foo(n: Int): List[Int] =
  if (n == 0)
    0 :: Nil
  else
    n :: foo(n - 1)

在这个递归的一般情况下，在foo(n - 1)之后返回函数必须对其返回的列表执行某些操作 - 它必须将另一个项目连接到列表的开头。所以这个函数不能是尾递归的，因为递归之后必须对列表做一些事情。

没有尾递归，对于n的一些大值，你用完了堆栈空间。

通常的列表解决方案

通常的解决方案是传递 ListBuffer作为第二个参数，并填写它。

def foo(n: Int) = {
  def fooInternal(n: Int, list: ListBuffer[Int]) = {
    if (n == 0) 
      list.toList
    else {
      list += n
      fooInternal(n - 1, list)
    }
  }
  fooInternal(n, new ListBuffer[Int]())
}

您正在做的事情被称为“tail recursion modulo cons ”，这是 LISP Prolog 编译器在看到尾递归模 cons 模式时自动执行的优化，因为它很常见。 Scala 的编译器不会自动对此进行优化。

流不需要尾递归

流不需要尾递归来避免耗尽堆栈空间 - 这是因为它们使用了一种巧妙的技巧来防止执行对 foo 的递归调用。在它出现在代码中的位置。函数调用被包装在 thunk 中，并且仅在您实际尝试从流中获取值时调用。只需调用foo一次一次处于事件状态——它从不递归。

我之前写过一个答案来解释 how the #:: operator works在 Stackoverflow 上。以下是调用以下递归流函数时会发生的情况。 (它在数学意义上是递归的，但它不会像您通常期望的那样从函数调用内部进行函数调用。)

def foo(n: Int): Stream[Int] =
  if (n == 0)
    0 #:: Nil
  else
    n #:: foo(n - 1)

您调用foo(10) ，它返回一个已经计算了一个元素的流，尾部是一个将调用 foo(9) 的 thunk下次您需要流中的元素时。 foo(9)现在没有被调用——而是调用绑定(bind)到 lazy val在流内，以及 foo(10)立即返回。当您最终确实需要流中的第二个值时，foo(9)被调用，它计算一个元素并将 hte 流的尾部设置为一个将调用 foo(8) 的 thunk 。 foo(9)立即返回，无需调用 foo(8) 。等等...

这允许您创建无限流而不会耗尽内存，例如:

def countUp(start: Int): Stream[Int] = start #::countUp(start + 1)

(请小心在此流上调用的操作。如果您尝试执行 forEach 或 map ，您将填满整个堆，但使用 take 是一个很好的使用方法流的任意前缀。)

一个更简单的解决方案

为什么不直接使用 Scala 的 for 而不是处理递归和流呢？循环？

def pairs(maximum:Int) =
  for (i <- 0 to maximum;
       j <- 0 to maximum)
    yield (i, j)

这会在内存中具体化整个集合，并返回 IndexedSeq[(Int, Int)] .

如果您特别需要一个 Stream，您可以将第一个范围转换为 Stream .

def pairs(maximum:Int) =
  for (i <- 0 to maximum toStream;
       j <- 0 to maximum)
    yield (i, j)

这将返回 Stream[(Int, Int)] 。当您访问序列中的某个点时，它将被具体化到内存中，并且只要您仍然拥有对该元素之前流中任何点的引用，它就会一直存在。

通过将这两个范围转换为 View ，您可以获得更好的内存使用率。

def pairs(maximum:Int) =
  for (i <- 0 to maximum view;
       j <- 0 to maximum view)
    yield (i, j)

返回 SeqView[(Int, Int),Seq[_]]每次您需要时都会计算每个元素，并且不存储预先计算的结果。

你也可以用同样的方式获取迭代器(只能遍历一次)

def pairs(maximum:Int) =
  for (i <- 0 to maximum iterator;
       j <- 0 to maximum iterator)
    yield (i, j)

返回 Iterator[(Int, Int)] .