Skip main navigation

Infinite Data Structures

Lazy evaluation allows us to define infinite data structures. In this article, Dr Jeremy Singer investigates several infinite lists.
Photo of Columns
© University of Glasgow

In the previous video, we looked at infinite lists. We can define an infinite list of consecutive integers as follows:

[1..]

We can evaluate this list, but it won’t print out in its entirety
— because it goes on for ever.
To repeat a set of identical values, use the repeat function.

repeat 'a'

Again, this list is infinite.
Use the take and drop functions to deal with infinite lists.
It’s permitted to do a finite amount of processing in an infinite list,
but not to traverse it infinitely.

The reason why Haskell can process infinite lists is because
it evaluates the lists in a lazy fashion — i.e. it
only evaluates list elements as they are needed.

Now let’s have a look at two well-known integer lists.
We will study their recursive definitions.

Fibonacci Numbers

The nth Fibonacci number is the sum of the previous two Fibonacci
numbers. The first two numbers are both 1.
Then the third is 2, followed by 3, 5, etc.

1, 1, 2, 3, 5, 8, 13, 21, ...

This can be expressed in Haskell using the zipWith function,
combining pairs of elements with the addition operator.

let fibs = 1:1:(zipWith (+) fibs (tail fibs))

We can evaluate individual elements of this
list using the !! indexed list
selection. Or we could take the first n elements of the fibs list.

Prime Numbers

Below is a series of filter expressions to calculate an
infinite list of prime numbers.

properfactors :: Int -> [Int]
properfactors x = filter (y->(x `mod` y == 0)) [2..(x-1)]

numproperfactors :: Int -> Int
numproperfactors x = length (properfactors x)

primes :: [Int]
primes = filter (x-> (numproperfactors x == 0)) [2..]

Let’s analyse how this definition works:

  1. The properfactors function takes an integer value x and returns
    a list of proper factors for x. Factors are numbers that divide x and
    leave no remainder. Proper factors for an integer x do not include 1 or x.
  2. The numproperfactors function simply counts how many proper factors
    there are for x, by returning the length of the properfactors x list.
  3. Finally, primes list uses the filter function to select integers x
    that have no factors in the range 2 to (x-1) inclusive.

Can you think of other interesting infinite lists we might explore? Please leave your suggestions (and Haskell source code!) in the comments below.

© University of Glasgow
This article is from the free online

Functional Programming in Haskell: Supercharge Your Coding

Created by
FutureLearn - Learning For Life

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education