在Scala中的Corecursion vs递归理解

Question

例如,如果递归几乎清楚

 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)
  }

我不确定核心运行.根据维基百科的文章," corecursion允许程序产生任意复杂且可能无限的数据结构,例如流 ".例如这样的构造

list.filter(...).map(...)

使得能够准备临时流filter和map操作之后.在filterstream 之后将只收集过滤后的元素,接下来map我们将更改元素.正确？

功能组合器map filter 是否使用递归执行是否有任何正文在Scala"比较递归和核心运行"中有很好的例子？

Answer 1

理解差异的最简单方法是认为递归消耗数据,而corecursion 产生数据.您的示例是递归,因为它使用您作为参数提供的列表.另外,foldLeft和foldRight也是递归,而不是corecursion.现在是一个corecursion的例子.考虑以下功能:

def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A]

只需查看其签名,您就可以看到此函数旨在生成无限的数据流.它将一个初始状态,z类型S和函数从S一个可能的元组,它将包含下一个状态和流的实际值,即类型A.如果结果f为empty(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]
}

您可以使用此功能实现其他生产功能.例如,以下函数将生成最多numOfValues类型的元素的流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)