Cover by Alex Payne, Dean Wampler

Safari, the world’s most comprehensive technology and business learning platform.

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required

O'Reilly logo

Infinite Data Structures and Laziness

We described lazy values in Chapter 8. In functional languages that are lazy by default, like Haskell, laziness makes it easy to support infinite data structures.

For example, consider the following Scala method fib that calculates the Fibonacci number for n in the infinite Fibonacci sequence:

def fib(n: Int): Int = n match {
  case 0 | 1 => n
  case _ => fib(n-1) + fib(n-2)
}

If Scala were purely lazy, we could imagine a definition of the Fibonacci sequence like the following and it wouldn’t create an infinite loop:

fibonacci_sequence = for (i <- 0 to infinity) yield fib(i)

Scala isn’t lazy by default (and there is no infinity value or keyword…), but the library contains a Stream class that supports lazy evaluation and hence it can support infinite data structures. We’ll show an implementation of the Fibonacci sequence in a moment. First, here is a simpler example that uses streams to represent all positive integers, all positive odd integers, and all positive even integers:

// code-examples/TypeSystem/lazy/lazy-ints-script.scala

def from(n: Int): Stream[Int] = Stream.cons(n, from(n+1))

lazy val ints = from(0)
lazy val odds = ints.filter(_ % 2 == 1)
lazy val evens = ints.filter(_ % 2 == 0)

odds.take(10).print
evens.take(10).print

It produces this output:

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, Stream.empty
0, 2, 4, 6, 8, 10, 12, 14, 16, 18, Stream.empty

The from method is recursive and never terminates! We use it to define the ints by calling from(0). Streams.cons ...

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required