尾递归有界整数对(Scala)？

Question

我对Scala很新,所以请原谅我的无知!我正在尝试迭代以最大值为界的整数对.例如,如果最大值为5,则迭代应返回:

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

我选择尝试并以递归方式将其作为Stream返回:

    @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扩展了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]())
}

你正在做的事情被称为" 尾递归模数缺点 ",这是LISP Prolog编译器在看到尾递归模数模式时自动执行的优化,因为它是如此常见.Scala的编译器不会自动优化它.

流不需要尾递归

流不需要尾递归以避免耗尽堆栈空间 - 这是因为它们使用一个聪明的技巧来阻止foo在代码中出现的递归调用执行.函数调用包含在thunk中,并且仅在您实际尝试从流中获取值时调用.一次只有一个呼叫foo是活动的 - 它永远不会递归.

我已经写了一个前面的答案,解释了#::运算符如何在Stackoverflow上运行.以下是调用以下递归流函数时发生的情况.(它在数学意义上是递归的,但它不会像你通常期望的那样在函数调用中进行函数调用.)

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

你调用foo(10)它,它返回一个已经计算过一个元素的流,尾部是一个thunk,它将foo(9)在你下次需要流中的元素时调用.foo(9)现在不调用 - 而是将调用绑定到lazy val流内部,并foo(10)立即返回.当你最终确实需要流中的第二个值时,foo(9)会调用它,它会计算一个元素,并将hte stream的尾部设置为将调用的thunk foo(8).foo(9)立即返回而不打电话foo(8).等等...

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

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

(请注意您在此流上调用的操作.如果您尝试执行a forEach或a map,则会填满整个堆,但使用take是一种使用流的任意前缀的好方法.)

一个更简单的解决方案

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

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

这将在内存中实现整个集合,并返回一个IndexedSeq[(Int, Int)].

如果您需要特定的Stream,则可以将第一个范围转换为a Stream.

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

这将返回一个Stream[(Int, Int)].当您访问序列中的某个点时,它将被实现到内存中,只要您仍然在该元素之前引用流中的任何点,它就会一直存在.

通过将两个范围转换为视图,您可以获得更好的内存使用量.

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)].