scala的共递归与递归理解
提问于 2015-09-09 04:41:40
如果递归非常清楚，例如
def product2(ints: List[Int]): Int = {
@tailrec
def productAccumulator(ints: List[Int], accum: Int): Int = {
ints match {
case Nil => accum
case x :: tail => productAccumulator(tail, accum * x)
}
}
productAccumulator(ints, 1)
}我不确定会不会是共递归。根据维基百科文章，“共递归允许程序产生任意复杂和潜在的无限数据结构，如流”。例如，像这样的构造
list.filter(...).map(...)准备filter和map操作后的临时流。在filter流只收集过滤元素之后，接下来在map中我们将更改元素。对，是这样?
函数组合器对map filter使用递归执行吗?有没有人在Scala中有“比较递归和共递归”的好例子？
回答 1
Stack Overflow用户
发布于 2015-09-10 00:09:15
理解这种差异的最简单方法是认为递归消耗数据，而协同递归生成数据。您的示例是递归，因为它使用了作为参数提供的列表。另外，foldLeft和foldRight也是递归的，而不是共递归的。现在是一个共递归的例子。考虑以下职能：
def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A]通过查看它的签名，您就可以看到这个函数的目的是生成无限的数据流。它接受初始状态，类型为z的S，以及从S到可能的元组的函数，该元组将包含流的下一个状态和实际值，即类型为A。如果f的结果为空(None)，那么unfold将停止生成元素，否则将继续传递下一个状态，以此类推。它的执行情况如下：
def unfold[S, A](z: S)(f: S => Option[(A, S)]): Stream[A] = f(z) match {
case Some((a, s)) => a #:: unfold(s)(f)
case None => Stream.empty[A]
}您可以使用此函数来实现其他生产性函数。例如，下面的函数将产生最多由A类型的A元素组成的流
def elements[A](element: A, numOfValues: Int): Stream[A] = unfold(numOfValues) { x =>
if (x > 0) Some((element, x - 1)) else None
}REPL中的用法示例：
scala> elements("hello", 3)
res10: Stream[String] = Stream(hello, ?)
scala> res10.toList
res11: List[String] = List(hello, hello, hello)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/32479852
复制相关文章
腾讯云开发者
