All Articles

Lazy Evaluation and Infinite Data Structures

This is the simplest example of lazy evaluation in Haskell. It is a recursively defined variable which produces an infinite amount of ones.

x = 1:x

On its own, the program will print 1 infinitely. However, this infinite variable is useful whenever a program wants to grab a finite, but yet to be determined, amount of values.

> take 5 x
[1,1,1,1,1]

In this situation, no values exist in memory, until take asks for five of them; this is due to lazy evaluation.

Primes

Infinite data structures with lazy evaluation can also be used evaluate prime numbers.

primes :: [Integer]
primes = filter (\x -> isPrime x) [0..]

isPrime :: Integer -> Bool
isPrime x
    | x == 0 || x == 1 = False
    | otherwise =
        null (filter (\y -> x `mod` y == 0) [2 .. (x - 1)])

The function primes is infinite due to the use [0..]. Using this definition a program can ask for any amount of primes.

> take 10 primes
[2,3,5,7,11,13,17,19,23,29]

Geometric Progression

Another example of lazy evaluation with infinite data structures is geometric progression. Consider the geometric progression a, ar, ar^2, ar^3, ar^4 ... where r > 0 and a is a scale factor.

geo :: Num a => a -> a -> [a]
geo a r = a : geoHelper a r 1

geoHelper a r 1 = a*r : geoHelper a r 2
geoHelper a r exp = a*r^exp : geoHelper a r (exp + 1)

With this implementation any range of a, ar, ar^2, ar^3, ar^4 ... can be taken in Haskell.

> take 4 (geo 2 2)
[2,4,8,16]

Summary

Lazy evaluation in Haskell allows programs to have infinite data structures that only occupy space when accessed. This gives values the ability to produce any amount of results when requested during runtime.

Published 12 Dec 2015