The Infinite List of Prime Numbers and its Applications

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. This is the part where we remove all the non-prime numbers to leave us with just the primes.

The final step is we run the algorithm again from step two and that's calling the sieve function. So, we've got our program here, let's see it actually working so I'll start up the haskell system again. Good, we've got no errors which is good. Let's run the prime number program and here we get all the prime numbers again so it gives exactly the same results as the simpler algorithm which we wrote before but it does so a lot more quickly.

If you do some simple experiments for numbers up to this kind of size, it runs about 10 times faster than the simple algorithm which we had previously. What could we do with this well, uh, we could do a whole bunch of things so for example if I wanted a hundred prime numbers, I don't know now need to write a program which generates 100 prime numbers, I just take the infinite list of all the prime numbers and I take 100. So, I've kind of separated my control part which is taking a hundred numbers from my data part which is having an infinite list of primes.

This idea of separating control and data using infinite data structures is a very powerful way of thinking about programming and I can do other things as well so for example if I wanted to say give me all the prime numbers less than 100, I don't need to write a separate program for that now I just take my infinite list of all the prime numbers and I say take while less than 100. This is what's called laziness in programming.

It means that instead of evaluating expressions all at once, we only evaluate them when their values are needed, which can greatly improve performance. In this case, the expression `take while less than 100` will not be evaluated until I actually need to take 100 prime numbers from the list. And then, in many languages if you wanted to write these two separate programs, you'd need to write some separate programs. But if you can manipulate infinite data structures, you just have your infinite list of primes and then you can do whatever you want with them afterwards.

You can select what parts you like and that's the beauty of it. Let me do one final little example to do with what's called twin primes so twin primes are primes which differ by two so three and five are twins because they differ by two, five and seven are twins because they differ by two, but seven and eleven are not twins because they differ by four. How do we write a program using what we've already done that generates all the twin primes? So, first of all, let me say what it means to be a twin so I'll say a pair xy is a twin if y is x plus two.

So, for example, if I say is 3 and 5 a twin, it will say true and if I say is 7 and 11 a twin, then I get no. So, how do I use this to write a program that generates all the twin primes well, what I'm going to do is I'm going to generate the infinite list of all the twins and I'm going to simply filter twin from zip of primes and tail primes.

What does tail do so tail takes a list which could be infinite and removes the first thing. So if we write tail of primes, what we're going to do is take the infinite list of all prime numbers and throw the two away so we'll get 3, 5, 7, 11, etc. What zip does is it takes two lists and they can be finite or infinite so suppose I've got two lists of five numbers, what zip does is it pairs up the corresponding elements in the two lists.

So if we've got a list of prime numbers and another list that's just one number less than each of those primes, then zip will pair them up so we'll get 2 and 3, 3 and 5, 5 and 7, and so on. So what we're going to get coming out of this zip is an infinite list of pairs of each prime number and the next prime number.

So we'll get 2 and 3, 3 and 5, 5 and 7, etc. And then all we're going to do is take that infinite list of all of those pairs and filter the twins out of it. This is enough to generate all the twin primes so I can test this out.

Here's all the infinite lists of twin primes. And this is a one-line program to do this based on a two-line program which we had to generate the infinite list of all the prime numbers going back to where I started programming with infinite data structures sounds impossible, but it's not really so what's happening here is that we're using a technique called "lazy evaluation" or more specifically "monadic evaluation".

It means that instead of evaluating expressions all at once, we only evaluate them when their values are needed. And by doing it this way, we can use the same piece of code to generate both prime numbers and twin primes.

So, while it may seem like a trick, it's actually a very powerful technique for manipulating infinite data structures in programming.

"WEBVTTKind: captionsLanguage: entoday we're going to do some live coding and we're going to do something which 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 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 can we do well maybe we want to filter out the even numbers from the list between 1 and 20. we can do that we just write filter even from 1 to 20. or if you 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 1540 is the correct answer so here's a little example of a finite list one 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 one dot dot and when i press return this will be the infinite list of all the natural numbers beginning with one 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 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 all 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 one 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 okay 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 one 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 one 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 try 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 ourselves 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 one and itself so for example seven is prime because it's got two factors one and seven 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 that 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 it could be clever here and write square root of n but let's just keep it simple you run over all the numbers between one 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 seven i just get two factors one and seven so that's a prime number and if i say what's the factors of 15 i get 4 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's 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 we hit return this thing will start generating the infinite list of all prime numbers okay and you can see here it's already gone quite far we've got up to about 16 000 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 2 000 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 here is a 2 000 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 the third step is to remove all the multiples of p so initially that will be two 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 three and then we're having an infinite loop in step four because we're looping around here forever so let's see how this 2000 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 two 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 three will fall down the five will fall down and in general all the odd numbers will fall down because the even numbers are stopped by the little barrier and you can think of this as being a sieve this is why it's called the civil era tustin is because we're blocking some numbers from coming down the page now we go back to the start again so three is a prime number and then we put a small barrier under all the multiples of three so six is already gone nine and twelve and then the numbers that are not stopped by the barrier are sieved out they come down the page so 5 comes down 7 comes down 11 comes down 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 we'll get 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 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 the 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 p's 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 not multiples of p what this part in the brackets here does is it takes the infinite list of all the remaining numbers so three all the way up to infinity and it's going to remove all the multiples of two so it's just running over the list and it's removing all the numbers which are multiples of two so this will remove the four the six the eight 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 two 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 the part here and then the final step is we run the algorithm again from step two and that's calling the sieve function so we've got our program here so let's see it actually working so let me start up the haskell system again good we've got no errors which is good so let's run the prime number program and here we get all the prime numbers again so it gives exactly the same results as the simpler algorithm which we wrote before but it does so a lot more quickly and if you do some simple experiments for numbers up to this kind of size it runs about 10 times faster than the simple algorithm which we had previously so what could we do with this well uh we could do a whole bunch of things so for example if i wanted a hundred prime numbers i don't now need to write a program which generates 100 prime numbers i just take the infinite list of all the prime numbers and i take 100. so i've kind of separated my control part which is taking a hundred numbers from my data part which is having an infinite list of primes and this idea of separating control and data using infinite data structures is a very powerful way of thinking about programming and i can do other things as well so for example if i wanted to say give me all the prime numbers less than 100 i don't need to write a separate program for that now i just take my infinite list of all the prime numbers and i say take while less than 100 and i get that and in many languages if you wanted to write these two separate programs you'd need to write some some separate programs basically but if you can manipulate infinite data structures you just have your infinite list of primes and then you can do whatever you want with them afterwards you can select what parts you like just to conclude let me do one final little example to do with what's called twin primes so twin primes are primes which differ by two so three and five are twins because they differ by two five and seven are twins because they differ by two seven and eleven are not twins because they differ by four so how do we write a program using what we've already done that generates all the twin primes so first of all let me say what it means to be a twin so i'll say a pair xy is a twin if y is x plus two so for example if i say is 3 and 5 a twin it will say true and if i say is 7 and 11 a twin then i get no so how do i use this to write a program that generates all the twin primes well what i'm going to do is i'm going to generate the infinite list of all the twins and i'm going to simply filter twin from zip of primes and tail primes so there's a couple of bits we haven't seen before here what does tail do so tail takes a list which could be infinite and removes the first thing so if we write tail of primes what we're going to do is take the infinite list of all prime numbers and throw the two away so we'll get 3 5 7 11 etc what zip does is it takes two lists and they can be finite or infinite so suppose i've got two lists of five numbers what zip does is it pairs up the corresponding elements in the two lists so it pairs up the first thing the second third fourth and fifth so what it's going to do here with the infinite lists is we're going to zip the infinite list of all the prime numbers with the infinite list of all the prime numbers apart from the first one so what we're going to get coming out of this zip is an infinite list of pairs of each prime number and the next prime number so we'll get 2 and 3 3 and 5 and so on and so on and then all we're going to do is take that infinite list of all of those pairs and filter the twins out of it and this is enough to generate all the twin primes so i can test this out here's all the infinite lists of twin primes and this is a one line program to do this based on a two-line program which we had to generate the infinite list of all the prime numbers going back to where i started programming with infinite data structures sounds impossible but as we've seen today and i hope to have convinced you it's actually quite simple and natural and practical okay that's all because haskell's lazy yes because of laziness so you can do this in other programming languages but essentially you need to fake lazy evaluation in some way and languages are providing a bit more support these days for doing that there's there's kind oftoday we're going to do some live coding and we're going to do something which 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 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 can we do well maybe we want to filter out the even numbers from the list between 1 and 20. we can do that we just write filter even from 1 to 20. or if you 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 1540 is the correct answer so here's a little example of a finite list one 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 one dot dot and when i press return this will be the infinite list of all the natural numbers beginning with one 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 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 all 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 one 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 okay 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 one 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 one 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 try 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 ourselves 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 one and itself so for example seven is prime because it's got two factors one and seven 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 that 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 it could be clever here and write square root of n but let's just keep it simple you run over all the numbers between one 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 seven i just get two factors one and seven so that's a prime number and if i say what's the factors of 15 i get 4 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's 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 we hit return this thing will start generating the infinite list of all prime numbers okay and you can see here it's already gone quite far we've got up to about 16 000 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 2 000 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 here is a 2 000 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 the third step is to remove all the multiples of p so initially that will be two 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 three and then we're having an infinite loop in step four because we're looping around here forever so let's see how this 2000 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 two 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 three will fall down the five will fall down and in general all the odd numbers will fall down because the even numbers are stopped by the little barrier and you can think of this as being a sieve this is why it's called the civil era tustin is because we're blocking some numbers from coming down the page now we go back to the start again so three is a prime number and then we put a small barrier under all the multiples of three so six is already gone nine and twelve and then the numbers that are not stopped by the barrier are sieved out they come down the page so 5 comes down 7 comes down 11 comes down 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 we'll get 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 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 the 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 p's 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 not multiples of p what this part in the brackets here does is it takes the infinite list of all the remaining numbers so three all the way up to infinity and it's going to remove all the multiples of two so it's just running over the list and it's removing all the numbers which are multiples of two so this will remove the four the six the eight 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 two 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 the part here and then the final step is we run the algorithm again from step two and that's calling the sieve function so we've got our program here so let's see it actually working so let me start up the haskell system again good we've got no errors which is good so let's run the prime number program and here we get all the prime numbers again so it gives exactly the same results as the simpler algorithm which we wrote before but it does so a lot more quickly and if you do some simple experiments for numbers up to this kind of size it runs about 10 times faster than the simple algorithm which we had previously so what could we do with this well uh we could do a whole bunch of things so for example if i wanted a hundred prime numbers i don't now need to write a program which generates 100 prime numbers i just take the infinite list of all the prime numbers and i take 100. so i've kind of separated my control part which is taking a hundred numbers from my data part which is having an infinite list of primes and this idea of separating control and data using infinite data structures is a very powerful way of thinking about programming and i can do other things as well so for example if i wanted to say give me all the prime numbers less than 100 i don't need to write a separate program for that now i just take my infinite list of all the prime numbers and i say take while less than 100 and i get that and in many languages if you wanted to write these two separate programs you'd need to write some some separate programs basically but if you can manipulate infinite data structures you just have your infinite list of primes and then you can do whatever you want with them afterwards you can select what parts you like just to conclude let me do one final little example to do with what's called twin primes so twin primes are primes which differ by two so three and five are twins because they differ by two five and seven are twins because they differ by two seven and eleven are not twins because they differ by four so how do we write a program using what we've already done that generates all the twin primes so first of all let me say what it means to be a twin so i'll say a pair xy is a twin if y is x plus two so for example if i say is 3 and 5 a twin it will say true and if i say is 7 and 11 a twin then i get no so how do i use this to write a program that generates all the twin primes well what i'm going to do is i'm going to generate the infinite list of all the twins and i'm going to simply filter twin from zip of primes and tail primes so there's a couple of bits we haven't seen before here what does tail do so tail takes a list which could be infinite and removes the first thing so if we write tail of primes what we're going to do is take the infinite list of all prime numbers and throw the two away so we'll get 3 5 7 11 etc what zip does is it takes two lists and they can be finite or infinite so suppose i've got two lists of five numbers what zip does is it pairs up the corresponding elements in the two lists so it pairs up the first thing the second third fourth and fifth so what it's going to do here with the infinite lists is we're going to zip the infinite list of all the prime numbers with the infinite list of all the prime numbers apart from the first one so what we're going to get coming out of this zip is an infinite list of pairs of each prime number and the next prime number so we'll get 2 and 3 3 and 5 and so on and so on and then all we're going to do is take that infinite list of all of those pairs and filter the twins out of it and this is enough to generate all the twin primes so i can test this out here's all the infinite lists of twin primes and this is a one line program to do this based on a two-line program which we had to generate the infinite list of all the prime numbers going back to where i started programming with infinite data structures sounds impossible but as we've seen today and i hope to have convinced you it's actually quite simple and natural and practical okay that's all because haskell's lazy yes because of laziness so you can do this in other programming languages but essentially you need to fake lazy evaluation in some way and languages are providing a bit more support these days for doing that there's there's kind of\n"