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)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With