Corecursion vs scala中的递归理解 [英] Corecursion vs Recursion understanding in scala

问题描述

如果递归几乎清除，例如

  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（...）
 
 code> 

可以在过滤器和 map 操作。在过滤器流之后的
将只收集过滤元素，接下来在映射中，我们将更改元素。正确？

函数组合器是否使用递归执行 map filter
在Scala中有没有很好的例子比较递归和corecursion？

解决方案

最简单的方法是理解不同的是，当corecursion 产生数据时，认为递归消耗数据。你的例子是递归的，因为它消耗了你提供的参数列表。另外，foldLeft 和 foldRight 也是递归，而不是corecursion。现在是一个corecursion的例子。考虑下面的函数：

$ $ $ $ $ $ $ $ $> def unfold [A，S]（z：S）（f：S => Option [ （A，S）]）：Stream [A]

只需查看其签名，就可以看到这个函数是为了产生一个无限的数据流。它需要一个初始状态 z 类型 S ，以及 S 添加到一个可能的元组中，该元组将包含下一个状态和流的实际值，它的类型是 A 。如果 f 的结果为空（ None ），则 unfold 停止生成元素，否则继续传递下一个状态，依此类推。这里是它的实现：

$ pre $ def $ def [S，A]（z：S）（f：S => Option [ （A，S）]）：流[A] = f（z）匹配{
case Some（（a，s））=> a＃:: unfold（s）（f）
case None => Stream.empty [A]
}


您可以使用此函数来实现其他 >生产性功能。例如。下面的函数会产生一个至多为 numOfValues 元素的流 A ：

$ b （元素：A，numOfValues：Int）：Stream [A] = unfold（numOfValues）{x =>
if（x> 0）Some（（element，x - 1））else None
}


REPL中的用法示例：

  scala>元素（hello，3）
 res10：Stream [String] = Stream（hello，？）
 
 scala> res10.toList 
 res11：List [String] = List（hello，hello，hello）
  

if with recursion almost clear, for example

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

I am not sure about to the corecursion. According to the Wikipedia article, "corecursion allows programs to produce arbitrarily complex and potentially infinite data structures, such as streams". For example construction like this

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

makes to posible prepare temporary streams after filter and map operations. after filter stream will be collect only filtered elements, and next in the map we will change elements. Correct?

Do functional combinators use recursion executions for map filter Does any body have good example in Scala "comparing recursion and corecursion"?

解决方案

The simplest way to understand the difference is to think that recursion consumes data while corecursion produces data. Your example is recursion since it consumes the list you provide as parameter. Also, foldLeft and foldRight are recursion too, not corecursion. Now an example of corecursion. Consider the following function:

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

Just by looking at its signature you can see this function is intended to produce an infinite stream of data. It takes an initial state, z of type S, and a function from S to a possible tuple that will contain the next state and the actual value of the stream, that is of type A. If the result of f is empty (None) then unfold stops producing elements otherwise it goes on passing the next state and so on. Here is its implementation:

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

You can use this function to implement other productive functions. E.g. the following function will produce a stream of, at most, numOfValues elements of type A:

def elements[A](element: A, numOfValues: Int): Stream[A] = unfold(numOfValues) { x =>
  if (x > 0) Some((element, x - 1)) else None
}

Usage example in REPL:

scala> elements("hello", 3)
res10: Stream[String] = Stream(hello, ?)

scala> res10.toList
res11: List[String] = List(hello, hello, hello)

这篇关于Corecursion vs scala中的递归理解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！