Corecursion vs Recursion understanding in scala

Question

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

According to wiki definition, your example of product is corecursion. product as recursion would look like def product(ints: List[Int]): Int = ints match { case Nil => 1 case x :: xs => x * product(xs) } — Kolmar
– Kolmar, Commented Sep 9, 2015 at 12:57
no - the example here is not corecursion - it's a special case of a fold implemented with recursion. - The stuff with corecursion is for example Iterable<..> in Java-world — Random Dev
– Random Dev, Commented Sep 9, 2015 at 13:00

lambdista · Accepted Answer · 2015-09-10 08:09:15Z

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)

Collectives™ on Stack Overflow

Corecursion vs Recursion understanding in scala

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related