scala - Scala中的Corecursion vs Recursion理解

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。根据 Wikipedia article ，“corecursion 允许程序生成任意复杂且可能无限的数据结构，例如流”。例如这样的建筑

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

在 filter 和 map 操作之后准备临时流。
在 filter 流之后将只收集过滤的元素，接下来在 map 中我们将更改元素。正确的？

函数组合器是否使用递归执行 map filter有没有任何机构在 Scala 中有很好的例子“比较递归和核心递归”？

Answer 1

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

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

您可以使用此功能来实现其他生产功能。例如。下面的函数将生成一个最多包含 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)