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
= nmatch
{case
0
|1
=>
ncase
_
=>
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 ...