Functional languages have the notion of lazy sequences, which are an abstraction of infinite sequences that are stored using a small, finite amount of memory. It would be wasteful to realize an entire infinite sequence before even using it. The basic idea is to only call the function that generates the sequence when needed, and cache the results. With lazy sequences, you don't blow the stack and the elements in the sequence are not recalculated everytime.

Let's look at how the two most popular and functional JVM languages handle lazy sequences.

Clojure has the lazy-seq macro to create lazy sequences. Since most functions are lazy in Clojure, sequences generated by these functions are also lazy. Here's how the Fibonacci sequence is implemented in Clojure.

(def fibo-seq
  (map first
    (iterate (fn [[a b]] [b (+ a b)]) [0N 1N])))

(defn fibo-list [n]
  (take n fibo-seq))

(defn fibo-last [n]
  (last (fibo-list n)))

This is a really elegant implementation that uses the lazy iterate function.

Scala has the parameterized Stream[T] class to represent a lazy list. Here's what a Scala Fibonacci stream looks like.

object Fibo {
  lazy val fibo: Stream[BigInt] =
    BigInt(0) #::
    BigInt(1) #::
    fibo.zip(fibo.tail).map { n => n._1 + n._2 }

  def fiboList = fibo.take(_: Int).toList

  def fiboLast = fiboList(_: Int).last
}

This implementation uses the lazy right-associative #:: function, which is actually the Stream.cons method. There's also an implicit conversion from a sequence to a stream, from the Stream companion object. I'm sure Haskell programmers will eagerly point out the need for a zipWith function.

Let's look at how these two implementations match up against eachother in terms of performance. In Clojure, the time macro can be used to measure the time taken to evaluate a form. There's really no equivalent in Scala, so let's implement our own. We should be able to simply say time(fiboLast(n)), for example.

def time[R](block: => R): R = {
  val t0 = System.currentTimeMillis
  val result = block
  val t1 = System.currentTimeMillis

  println("Elapsed time: " + (t1 - t0) + "ms")
  result
}

Note that the time taken to print the result of a statement in the REPL shouldn't be measured. We can ensure this by binding the result to a variable. This is done by using val fibo = time(fiboLast(5000) in Scala, and (time (def fibo (fibo-last 5000))) in Clojure, for example. Memory usage can be ignored, as the GC is invoked unpredictably.

And here are the results!

A weird observation in the Scala implementation is that fiboList(1) takes 8-10 milliseconds to evaluate. But Scala actually performs better on average, which is mostly due to the use of static types.

Interestingly, the Clojure fibo-list function evaluates in constant time, which is less than a millisecond! Clojure also fetches cached elements in the lazy sequence much faster than Scala. However, fibo-last performs linearly since the last function has linear time-complexity.

« LINQ Is Not Quick The WebBrowser nightmare »