CSc 372 - Comparative Programming Languages
14 : Haskell -- Lazy Evaluation

Christian Collberg

Department of Computer Science

University of Arizona

1 Lazy evaluation

Haskell evaluates expressions using a technique called lazy evaluation:
1. No expression is evaluated until its value is needed.
2. No shared expression is evaluated more than once; if the expression is ever evaluated then the result is shared between all those places in which it is used.
Lazy functions are also called non-strict and evaluate their arguments lazily or by need.
C functions and Java methods are strict and evaluate their arguments eagerly.

2 Don't Evaluate Until Necessary

The first of these ideas is illustrated by the following function:
$\begin{program} ignoreArgument x = ''I didn't evaluate x'' \end{program}$
Since the result of the function ignoreArgument doesn't depend on the value of its argument x, that argument will not be evaluated:
$\begin{program} \redtt{\$ hugs +s} \\ \redtt{> ignoreArgument (1/0)} \\ I didn't evaluate x \\ (246 reductions, 351 cells) \end{program}$

3 Don't Evaluate Until Necessary...

The function seq forces strict evaluation when that is necessary:
$\begin{program} \redtt{> seq ignoreArgument (1/0)} \\ Inf\\ (32 reductions, 78 cells) \end{program}$

4 Evaluate Shared Expressions Once

The second basic idea behind lazy evaluation is that no shared expression should be evaluated more than once.
For example, the following two expressions can be used to calculate :
$\begin{program} \redtt{\$ hugs +s} \\ \redtt{> square*square where square = 3*3... ...ls) \\ \redtt{> (3*3)*(3*3)} \\ 81 \\ (34 reductions, 45 cells) \end{program}$

5 Evaluate Shared Expressions Once...

Notice that the first expression requires fewer reduction than the second.
A reduction is the basic step of evaluating a Haskell expression, by applying a function to its argument.

6 Saving Reductions

Consider these sequences of reductions:

square * square where square = 3 * 3
   -- calculate the value of square by 
   -- reducing 3*3==>9 and replace each
   -- occurrence of square with this result
   ==> 9 * 9
   ==> 81

(3 * 3) * (3 * 3)   -- evaluate first (3*3)
   ==> 9 * (3 * 3)  -- evaluate second (3*3)
   ==> 9 * 9
   ==> 81

Lazy evaluation means that only the minimum amount of calculation is used to determine the result of an expression.

7 Taking the Minimum

Consider the task of finding the smallest element of a list of integers.
$\begin{program} \redtt{> minimum [100,99..1]} \\ 1\\ (2355 reductions, 3211 cells) \end{program}$
[100,99..1] denotes the list of integers from 1 to 100 arranged in decreasing order.
Instead, we could first sort and then take the head of the result:
$\begin{program} \redtt{> :load List}\\ \redtt{> sort [100,99..1]}\\ {[1, 2, 3, 4, 5, 6, 7, 8, ..., 99, 100]} \\ (3430 reductions, 8234 cells) \end{program}$

8 Taking the Minimum...

However, thanks to lazy evaluation, calculating just the first element of the sorted list actually requires less work in this particular case than the first solution using minimum:
$\begin{program} \redtt{> head (sort [100,99..1])} \\ 1 \\ (1877 reductions, 3... ...edtt{> minimum [100,99..1]} \\ 1\\ (2355 reductions, 3211 cells) \end{program}$

9 Infinite data structures

Lazy evaluation makes it possible for functions in Haskell to manipulate `infinite' data structures.
The advantage of lazy evaluation is that it allows us to construct infinite objects piece by piece as necessary
The function ones below generates an infinite list of 1s:

$\begin{program} ones = 1 : ones \\ \\ \redtt{> take 10 ones}\\ {[1,1,1,1,1,1,1,1,1,1]} \\ (277 reductions, 389 cells) \end{program}$

10 Infinite data structures...

Consider the following function which can be used to produce infinite lists of integer values:

$\begin{program} countFrom n = n : countFrom (n+1) \\ \\ \redtt{> countFrom 1}\\ {[1, 2, 3, 4, 5, 6, 7, 8,\verb+^+C{Interrupted!}] } \end{program}$

11 Infinite data structures...

For practical applications, we are usually only interested in using a finite portion of an infinite data structure.
We can find the sum of the integers 1 to 10:
$\begin{program} \redtt{> sum (take 10 (countFrom 1))} \\ 55 \\ (278 reductions, 440 cells) \end{program}$
take n xs evaluates to a list containing the first n elements of the list xs.

12 Infinite data structures...

Infinite data structures enable us to describe an object without being tied to one particular application of that object.
The following definitions for infinite list of powers of two [1, 2, 4, 8, ...]:
$\begin{program} powersOfTwo = 1 : map double powersOfTwo \\ \xxx where double n... ...\redtt{> take 10 powersOfTwo} \\ {[1,2,4,8,16,32,64,128,256,512]} \end{program}$

13 Infinite data structures...

xs!!n evaluates to the :th element of the list xs.
We can define a function to find the th power of 2 for any given integer :

$\begin{program} powersOfTwo = 1 : map (*2) powersOfTwo \\ \\ twoToThe n = powersOfTwo !! n \\ \\ \redtt{> twoToThe 5} \\ 32 \end{program}$

14 Fibonacci

Here's a definition of a function that generates an infinite list of all the fibonacci numbers:
$\begin{program} fib = 1:1:[a+b\vert a,b <-zip fib (tail fib)] \\ \\ \redtt{> take 10 fib} \\ {[1,1,2,3,5,8,13,21,34,55]} \end{program}$

15 Acknowledgements

Christian S. Collberg
2005-09-21

CSc 372 - Comparative Programming Languages 14 : Haskell -- Lazy Evaluation

CSc 372 - Comparative Programming Languages
14 : Haskell -- Lazy Evaluation