Skip main navigation

New lower prices! Get up to 50% off 1000s of courses. 

Explore courses

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

Reach your personal and professional goals

Unlock access to hundreds of expert online courses and degrees from top universities and educators to gain accredited qualifications and professional CV-building certificates.

Join over 18 million learners to launch, switch or build upon your career, all at your own pace, across a wide range of topic areas.

Start Learning now