Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Corecursion vs Recursion understanding in scala

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"?

like image 419
initmax Avatar asked Dec 08 '22 01:12

initmax


1 Answers

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)
like image 131
lambdista Avatar answered Dec 23 '22 10:12

lambdista