sounds impossible, but is actually quite natural and practical, and that's

programming with infinite data structures. And we're going to be using

Haskell for this, but it doesn't matter if you don't know anything about

Haskell, because I'm going to explain everything in a simple way as we go

along. The first thing we're going to do, is we're going to start up the Haskell

system which we're going to be using, which is called GHCi.

And if you'd like to try this stuff out for yourself, this is freely available

online - just search for the obvious thing. Before we start thinking about infinite

data structures, we're going to do a little bit of computation with a simple

finite data structure, which is a finite list. So here's a finite list in Haskell.

It's just a list of numbers between 1 and 20, and it's written 1..20. And if

we ask the Haskell system to evaluate that, and we'll just expand it out, to

give the numbers between 1 and 20. And then we can think, well what can we

actually do with the finite list? So, for example, we could sum the list up, and we

get the expected answer 210. We could say, well maybe we want to square all the

numbers between 1 and 20. So we can "map" the squaring function over the list from

1 to 20, and we get the first 20 squares. What else could we do? Well, maybe we want

to filter out the even numbers from the list between 1 and 20, and we can do that.

We just write "filter even" from 1 to 20. Or if we want to be a little bit more

fancy, we could combine everything we've done up to this point, and we could say:

what is the sum, of the squares, of all the even numbers between 1 and 20? And

hopefully 1,540 is the correct answer. So here's a little example of a finite list,

1 up to 20, and then we've seen four small examples of simple kinds of computation

which we could do on that finite list. But the video today is about infinite

data structures. In particular, we're going to be talking about infinite lists.

So how do we do infinite lists in a language like Haskell? Well, it's very

simple. Rather than writing something like 1..20, we just say 1.., and when

I press return, this will be the infinite list of all the natural numbers

beginning with 1. And this is going to go on forever, but I can interrupt and you

can see we've already got up to about 196,000 here. Okay, so it runs,

it runs quite quickly. So this is an infinite list. So what can we actually do

with an infinite list? So let's try some of the things which we tried before

first of all. So maybe we can sum it? So let's try summing the infinite list of

all the numbers beginning with one. And I press that, and of course this doesn't

actually work, because there's an infinite number of values in this list,

and we try and sum them - it's never going to finish. So I need to

interrupt this one here. Let's try something else. Maybe I can try filtering

the even numbers from an infinite list, and hopefully this will work?

And yes it does. What we get this time, is we get the infinite list of all the even

numbers. Okay so you can see there's no odd numbers in the list here. What we're

actually doing, is we're taking an infinite data structure as an input,

we're taking an infinite list, and we're processing it, and we're giving an

infinite data structure as an output. We're taking an infinite list in, and

giving an infinite list out, which is quite an interesting idea. So let's try

another example. Let's try filtering all the numbers less than 100, from the

infinite list beginning with 1. And this kind of works, but not quite. There's a

little problem at the end. So we get all the numbers from 1 up to 99, which is

exactly what we expect, But now it's just sitting here, and that's because it's

basically trying to find another number which is less than 100. And it will never

succeed with that, but it doesn't know it's not going to find one, so it will go

on forever. Ok, so I have to break out of this one. And this again illustrates the

idea that when you're programming with infinite data structures, you need to be

careful. We tried to sum an infinite data structure, and it didn't work,

it just went immediately into an infinite loop. We're trying to filter

here from an infinite data structure, and it gave us the expected results, but in

the end it just hung. So you need to be careful with this kind of thing. Let's

try one more example. Let's try taking 20 elements, from the infinite list

beginning with 1. And this of course works. We just get exactly what we expect,

we get the numbers between 1 and 20. We're taking an infinite data structure

as an input, we're taking the infinite list of all the values from 1 onwards,

and we're getting a finite data structure as the output, we're getting a

finite list of all the numbers between 1 and 20. How does

this kind of behavior actually work? And it's to do with the evaluation order

which you have in your programming language. Most languages are what's

called strict, or eager. And that means when you have a parameter, like this

infinite list, you completely evaluate that parameter

before you try and do anything with it. So if you're in an eager, or strict,

language and you try and run "take 20" of an infinite list, it's never going to get

anywhere, because it will just attempt to evaluate the infinite list, and that will

never stop, and you'll never actually get any result. But languages like Haskell are

lazy. When you have a parameter in Haskell, you only evaluate it on demand.

So, the demand here, is that we want to take 20 elements from the infinite list.

So the two parts here, "take 20" and the infinite list, they kind of collaborate

together and say, well, we only actually need to generate 20 elements to proceed,

so we don't actually generate the entire infinite list. So in Haskell, when we

write one up to infinity, it's not really an infinite list, it's a *potentially*

infinite list, which gets evaluated as much as required by the context in which

we use it. There's some small little examples. Let's maybe trying something a

bit more interesting now. Let's try and write a program which generates all the

prime numbers - the infinite list of all prime numbers. So let's remind yourself

what a prime number is. So a number is prime if it's only factors, so that's the

numbers that divide into it exactly, are 1 and itself. So for example 7 is prime,

because it's got two factors, 1 and 7, but 15 is not prime, because it's got four

factors. So let's write a program to do this. So first of all, we're going to

write a small function called "factors", which is going to return all the numbers

which divide exactly into a number. So if I give it a number like n, I'm going to

return all the values x, such the x comes from the list 1 up to n. And if I take

the remainder when I divide n by x, then that had better be 0. So this is just

running over all the numbers between 1 and the given number, and I could be

clever here and write square root of n, but let's just keep it simple - you run

over all the numbers between 1 and the given number, and you just check is the

remainder when I divide one by the other zero. So for example, if I say what's the

factors of 7, I just get two factors one and 7, so that's a prime number.

And if I say what's the factors of 15, I get four factors, 1, 3, 5 and 15,

so that's not a prime number. And this tells us basically how we can

define a very simple program to check if a number is prime. I can say, a number n

is prime, if and only if, if I look at its factors, if I get back exactly the list 1

and n. So that's my definition of what it means to be a prime number. Now I can

check that this actually works. I can say is 7 a prime number? And it says true,

because it has exactly two factors. And I can say is 15 a prime number? And I get

false, because it's got more than two factors. Now we've got all we need to

actually generate the infinite list of all prime numbers. And we can use, you can

do this simply using the filter function. If we just now filter, all the prime

numbers from the infinite list beginning with one, then as soon as I hit return,

this thing will start generating the infinite list of all prime numbers, ok.

And you can see here, it's already gone quite far, we've got up to about 16,000,

and you can check that all of these numbers are actually prime. But actually

this is quite a modern laptop, we'd expect this program to run much faster

than this, so what we'd like to do now is see how we can take this simple means of

producing the infinite list of all the prime numbers, and actually make it go a

lot faster, by using a 2000 year old algorithm. Did they

have algorithms 2000 years ago? Yes they did, the ancient Greeks discovered

many things, including many interesting algorithms. So here is a 2000

year old algorithm, which is called the sieve of Eratosthenes, after a Greek

mathematician, and this is a very very simple algorithm for generating the

infinite list of all the prime numbers. So let's see how it actually works. The

first step, is we write down the infinite list, 2, 3, 4, all the way up to infinity.

The second step, is we mark the first value p, so that's going to be 2, as being

a prime number. And the third step is to remove all the multiples of p, so

initially that will be 2, from the list. And the fourth step, is that we go back

to the second step. So it's a very simple, four step process, for generating all the

prime numbers. And an interesting observation here, is that

infinity occurs all over the place in this algorithm. We're writing down an

infinite list at the beginning; we're removing an infinite number of elements

from an infinite list in step 3; and then, we're having an infinite loop in step 4,

because we're looping around here, forever. So let's see how this 2,000 year

old algorithm actually works in practice, with a little example. So the first step

in the algorithm was we write down all the numbers from 2 up to infinity. So

let's stop at 12, but of course, in principle, we go on forever here. Then the

next step is, we mark the first value in the list as being a prime number. So

we'll say 2 is our first prime number. Then we need to remove all the multiples

of 2 from the list, and let's do this by putting a small barrier under all the

multiples of 2, so that's the even numbers - oops, forgot 11 - and we'll think

of these barriers as kind of stopping these numbers falling down the page. So

we imagine the numbers trying to fall down the page now. So the 3 will fall

down, the 5 will fall down, and in general all the odd numbers will fall down,

because the even numbers are stopped by a little barrier. And you can think of

this as being a sieve. This is why it's called the sieve of Eratosthenes, because

you're blocking some numbers from coming down the page. And now we go back to the

start again. So 3 is a prime number, and then we put a small barrier under all

the multiples of 3. So 6 is already gone, 9 and 12, and then the numbers that are

not stopped by the barrier, or sieved out, they come down the page. So 5 comes down,

7 comes down, 11 comes down. And we continue. 5 is a prime number. We remove all the

multiples of 5; the numbers come down the page, and so on. So you can see the basic

idea here - we're generating, in a very simple way, all the prime numbers. We're

getting 2, 3, 5, 7, and eventually 11, and so on. So that's the algorithm. What we're

going to do now, is think how can we actually implement this in our a

programming language. And we'll see that we actually only need a two-line

program to implement this. It's a very direct translation of the

2000 year old algorithm into an actual working program. So let me start

up an editor, and we're going to write a program now. So we're going to generate

the infinite list of all the prime numbers, and I'm going to define that by

sieving the infinite list starting from 2.

So the first step of the algorithm, was we write down all numbers from 2 onwards.

So that's what we've got here, and then we're going to pass it into a function

called "sieve", which we haven't written yet, which is going to do all the other

steps for us. So what does sieve do? Well, sieve is going to take the list apart. So

p will be the first thing in the list, so that's initially going to be 2. And ps

will be everything else, so that's 3, 4, 5 etc, all the way up to infinity. And then

what we're going to do, on the right hand side, is we'll keep the first value, so

that's like marking the first number as being prime. And then we're going to

recursively sieve something. So what we're going to do, is we're going to sieve out

all the numbers which are multiples of p. What this part in the brackets here

does is, is it takes the infinite list of all the remaining numbers - so 3 all the

way up to infinity - and it's going to remove all the multiples of 2. So it's

just running over the list, and it's removing all the numbers which are

multiples of 2. So this will remove the 4, the 6, the 8, and the so on.

And then we just call ourselves recursively again. And this is the entire

program. So actually, the program is shorter than the English description we

had of the algorithm. It's useful to actually think, how does each step

actually get represented here? Well the first step was, we write down the numbers

from 2 up to infinity, which is here. The second step is, we mark the first value

as being prime, so that's the value p here. The third step is, we remove all the

multiples of p, so all the multiples of two initially from the list, and that's