Scala - Corecursion

This chapter takes you through the concept of corecursion in Scala programming. Corecursion is a dual of recursion, where you generate potentially infinite data structures and can call itself. Instead of calculating the result by breaking the problem into smaller sub-problems, corecursion focuses on progressively generating the output.

Corecursion

Corecursion produces stream-like data structures, where each element is produced on demand. Corecursion functions are used when you work with infinite sequences and when you need to model continuous data generation.

Recursion vs Corecursion

There is difference between recursion and corecursion in Scala. Recursion is a process where function calls itself. Whereas, corecursion is a process where a function produces its output gradually and may call itself.

def factorial(n: Int): Int = if (n == 0) 1 else n * factorial(n - 1)

def streamFrom(n: Int): Stream[Int] = n #:: streamFrom(n + 1)

Definition of Corecursion

Corecursion is a technique where a function produces its output gradually and may call itself. Unlike recursion, base condition may not always be required in corecursion because it can produce infinite structures.

Syntax

The syntax of corecursive function in Scala is -

def corecursiveFunction(params: Type): Stream[ReturnType] = {
   // generate the first element
   // generate the rest of the stream corecursively
   firstElement #:: corecursiveFunction(nextParams)
}

Example

The following example shows defining and using a corecursive function in Scala programming -

object Demo {
   def fibonacci(a: Int, b: Int): Stream[Int] = {
      a #:: fibonacci(b, a + b)
   }

   def main(args: Array[String]): Unit = {
      val fibs = fibonacci(0, 1)
      println(fibs.take(10).toList) 
   }
}

Save the above program in Demo.scala. Use the following commands to compile and execute this program.

Command

> scalac Demo.scala
> scala Demo

Output

List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)

In the example, the fibonacci function generates an infinite stream of Fibonacci numbers. Each element is produced on demand using the #:: operator. It prepends first element to rest of the stream generated corecursively.

Advantages of Corecursion

Corecursion is the dual of recursion. It can be used when you work with lazy evaluation, where elements are generated only when needed. So corecursions are efficient infinite data structures. You can use corecursion for modular and composable code, where data production logic is separated from data consumption logic. You can also use corecursive functions for stream processing, where data is processed as it is generated. So these are efficient for large and infinite sequences.

Corecursion with Streams

Streams in Scala are used to implement corecursive functions. Streams are lazy lists. You can use streams where elements are computed only when they are accessed.

Syntax

The syntax of corecursion with streams is -

def corecursiveFunction(params: Type): Stream[ReturnType] = {
   firstElement #:: corecursiveFunction(nextParams)
}

Example

Consider the example of generating an infinite stream of natural numbers using corecursion in Scala programming -

object Demo {
   def naturalNumbers(start: Int): Stream[Int] = {
      start #:: naturalNumbers(start + 1)
   }

   def main(args: Array[String]): Unit = {
      val nums = naturalNumbers(1)
      println(nums.take(10).toList) 
   }
}

Save the above program in Demo.scala. Use the following commands to compile and execute this program.

Command

> scalac Demo.scala
> scala Demo

Output

List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

In the example, the naturalNumbers function generates an infinite stream of natural numbers starting from a given number. Each number is produced on demand using corecursion.

Corecursion with Trees

You can also use corecursion to generate tree-like structures, where each node is generated step by step.

Syntax

The syntax of corecursion with trees is -

case class Tree(value: Type, children: Stream[Tree])

def corecursiveTreeFunction(params: Type): Tree = {
   Tree(rootValue, corecursiveTreeFunction(nextParams))
}

Example

Consider the example of generating an infinite binary tree using corecursion in Scala programming -

case class Tree(value: Int, left: () => Tree, right: () => Tree)

object Demo {
   def infiniteTree(value: Int): Tree = {
      lazy val leftSubtree = infiniteTree(value * 2)
      lazy val rightSubtree = infiniteTree(value * 2 + 1)
      Tree(value, () => leftSubtree, () => rightSubtree)
   }

   def main(args: Array[String]): Unit = {
      val tree = infiniteTree(1)
      println(tree.left().left().value)  
      println(tree.right().right().value) 
   }
}

Save the above program in Demo.scala. Use the following commands to compile and execute this program.

Command

> scalac Demo.scala
> scala Demo

Output

4
7

In the example, the infiniteTree function generates an infinite binary tree, where each node has a left and right child. The tree is generated corecursively, with each node value doubling or doubling plus one from its parent node.

Corecursion with Streams and Filtering

You can use corecursion combined with filtering to generate streams that satisfy given conditions.

Syntax

The syntax of corecursion with streams and filtering is -

def corecursiveFilteredFunction(params: Type): Stream[ReturnType] = {
   val nextValue = computeNextValue(params)
   if (condition(nextValue)) nextValue #:: corecursiveFilteredFunction(nextParams)
   else corecursiveFilteredFunction(nextParams)
}

Example

Consider the example of generating an infinite stream of even numbers using corecursion and filtering in Scala programming -

object Demo {
   def evenNumbers(start: Int): Stream[Int] = {
      if (start % 2 == 0) start #:: evenNumbers(start + 2)
         else evenNumbers(start + 1)
   }

   def main(args: Array[String]): Unit = {
      val evens = evenNumbers(1)
      println(evens.take(10).toList) 
   }
}

Save the above program in Demo.scala. Use the following commands to compile and execute this program.

Command

> scalac Demo.scala
> scala Demo

Output

List(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)

In the example, the evenNumbers function generates infinite stream of even numbers starting from a given number. You can produce each even number on demand using corecursion and filtering.

Corecursion Summary

• Corecursion is used to generate potentially infinite data structures step by step.
• Corecursive functions can use lazy evaluation to produce elements on demand. So it is efficient for working with large and infinite sequences.
• You can apply corecursion to streams, trees, and other data structures, etc,.for modular and composable code.
• You can also filter with corecursion to generate streams that satisfy given conditions.