Dec 3, 2009

Infinite Lists in Scala

One of the pretty cool things about Haskell is the ability to have infinite lists, thanks to Haskell's laziness. You can create a list containing all the Fibonacci numbers, or all the digits of π, or something like that.

Turns out that Scala can do it too, despite not being a lazy language. The main way to do it is with the lazy keyword:
lazy val hello = epicCalculation()

if (some condition){
println(hello) // epicCalculation() is done here
}else{
// don't use hello
// in this execution path, epicCalculation is never called
}
Here we're creating a constant variable called hello and only using it in one of our if branches. That means that if execution never goes into our if block, then the epic calculation is never computed. Pretty handy sometimes! This example isn't great because we can just call epicCalculation inside the if block, but whatever.
Unfortunately one catch is that the variable is evaluated when you pass it to another function, regardless of whether it is used or not:
object Main{
def getValue = {
println("getting value")
5
}
def output(y : Any) = {
println("outputting")
}
def main(args : Array[String]){
lazy val x = getValue
output(x)
}
}
Even though the variable y is not actually used inside output(), the value of x is still evaluated. So it isn't true laziness, but whatever.

We can also build infinite lists using the Stream class. Here's an example of generating a familiar list of numbers (I'd use Fibonacci but it is a bit more complex since each element depends on two previous elements instead of one):

object InfLists extends Application{
def numbers(current : Int) : Stream[Int] =
Stream.cons(current, numbers(current * 2))

// print out 10 numbers, starting with 1
numbers(1).take(10).foreach(println)
}
Yet again another trivial example, but it is kinda neat to be able to do this.

Note that the following does not work:
println(numbers(1) take 10)
Why not? Well here, we're not actually evaluating the values for the first 10 numbers. So when println goes to print the list, it just prints the first element followed by a ?, because it doesn't know what the rest of the list is.

Now if you actually want the Fibonacci series, you can do it like this:
Stream.cons(1, Stream.cons(1, fib.zip(fib.tail).map(f => f._1 + f._2)))
Swiped from here, converted to Scala. If you zip something with its tail, then you get a list of pairs that look like this: (ai, ai + 1). Then if you map that using +, you'll get your result.

No comments: