Home > Articles > Programming > General Programming/Other Languages

  • Print
  • + Share This
Like this article? We recommend

Lazy Evaluation

One of the most interesting things about Haskell is that it defers evaluation of a statement until its result is used. This means that you can write functions that are undefined for some values or even for some part of their inputs. You can see this easily in a trivial example:

Prelude> let ignoreArg x = "x is not evaluated"
Prelude> let foo x = foo x + 1
Prelude> ignoreArg (foo 1)
"x is not evaluated"
Prelude> foo 1
^CInterrupted.

The function foo is defined as recursively calling itself and then adding 1 to the result. This will never terminate, so it's trivial to see whether the (foo 1) argument to ignoreArg is evaluated: If the function returns immediately, it obviously isn't. If it doesn't return immediately, then it (probably) is being evaluated. Evaluating foo 1 alone lets you see the difference—this function keeps going until you get bored and hit control-C.

This example is pretty useless. You wouldn't want to create a function like this. It's more useful in the case where you only want partial results. For example, there was a paper published that IEEE Visualization conference a few years ago, which used this feature of Haskell to lazily load parts of a scene from disk as they were used.

Lazy evaluation is commonly used in conjunction with list comprehensions in Haskell. This is a simple function for generating the entire Fibonacci sequence in Haskell:

fib = 1:1:[a+b| (a, b) <- zip fib (tail fib)]

This returns a list where the first two elements are 1 and the rest are defined by a list comprehension.

List comprehensions are a bit complex, so it's worth breaking this one down a bit. The next element is defined as a+b, but how are a and b defined? The zip function creates a list of pairs from two lists. In this case, it's the list returned by calling fib and the list returned by calling fib, but with the first element removed by the tail function.

To calculate the third element in this list, it just needs to look at the first two. These are constants, so that's fine. To calculate the fourth element, it lazily calculates the third and then calculates the second from this.

You can see the lazy evaluation more clearly with the take function, which takes n elements from a list:

Prelude> take 10 fib
[1,1,2,3,5,8,13,21,34,55]

This shows the first 10 Fibonacci numbers and only calculates the first 10. Even though the fib function is defined as returning an infinite list, it only actually calculates the first 10 elements because that's all that is accessed.

  • + Share This
  • 🔖 Save To Your Account