Today 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, 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
the part here. And then the final step is, we run the algorithm again from step 2,
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 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 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 a hundred. 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 "takeWhile" 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 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 3 and 5 are twins, because they differ by two; 5 and 7 are
twins, because they differ by two; 7 and 11 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 (x,y) is a twin, if y is x+2. 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 2 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 the infinite list 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. That's all because Haskell is lazy?
Yeah it's 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 and there's...