K welcome back to our very last check
and above the very last lecture of
functional programming on a long and and this law
law segment I'm going to make up for some Kalani caught
that we're all its couple of lectures ago
I don't know if not I don't know if you remember
but when we were talking about list comprehension
the road a really really
really embarrassing version an
of a prime number generator and
we want to do better and that guards was not
the most beautiful code I've ridden my live show that's redeem ourselves
and rides a beautiful way to generate Bryant
that leverages lazy evaluation so here's a
recipe to generate and infinite less of primes
an in a very an
nice way so we start to with the list
of all natural numbers starting at two and then
we look initial list and we marked the first
value in that list as a prime
so the first Brian here is to the next thing we do
as we say okay every node at this thing is a prime
then all multiples of DAT
number are not brunch right show for example to
is I'm for is a multiple of 2
so we know that for is not a prime number
saw given that the first mark prime
we're going to delete we're going to filter out all the multiples of that
number from the list
and then me just yeah we note that dan
then next value is the prime and Mb
elite all the duplicate and saw now
this algorithm is really alt
a this algorithm was really invented before
any of us he was
for and this is difficult
this if affair Dustin s I K to dismiss
am invented by ancient Greek
mathematicians its draw a picture here
other you up the steps so we start here
with the list %uh natural numbers starting at 2
first number here is a prime
re-cross arts all the multiples of 2
show we cross eyed for six a tan 12
jethroe and now the first number
that's not grossed out three is a prime that's a prime
for us already crossed out five is not a multiple of 36 is a multiple of three
was already crossed out
not mine was not crossed our jet is a multiple of three so we cross that are
and we continue so now 5 is def
the next prime are going to remove all Multipla
multiples of five et cetera so here is she
that fairly easily we find the first
few prime numbers 2-3 5
7 and 11 let's
am translate this a into haskell alright
and the beauty of this is dead this
and algorithm is more or less directly translated
into haskell of course there's been
their again you know there's a you which
field of literature on different versions of this save and more efficient
versions
you can spend years researching that and
it's a beautiful area an but this is the gonna
this simplest version up this and to show you the power
ablaze evaluation and infinite lists to restart a radiant
lester natural numbers starting at two and that we're going to
civil out all these numbers just falling recipe
so how does this shit work well we start with the first number in the less that's
a prime
and what we do is we returned that number
and then we say
throw out all the multiples of P
from excess and then recursively
go back to step 2 save out all the numbers from there
her isn't a beautiful
I mean here's a glide impaired if them
description return to Step 2 but what we see here
is that return to Step 2 is really
this recursive call here alright so we started
numbers from to an up the first number must be prime
we remove all the numbers that are duplicate
and then we just see if the result that must now start with the next prime
we're going to up with that don't keep that
and then save out the rest at setter are you can also see
why they're more efficient versions and we already saw that here
biggest an multiples of 2
are eliminated and here multiples of 20 are eliminated and so
you know there's many ways you can do this sieve
you know in a more efficient way with gonna reels in
whatever again I would just google for
several pair Dawson as you will find
a large collection of papers that describe
different variants of this that are much more efficient
and that use all gonna properties of natural numbers
to make this computation more efficient
day but every execute yes primes
this thing will just spew out an infinite lest
of prime numbers they will just continue and not sure I'll get slower and slower
because you know the prime numbers
there will be more space between them but yeah
you can just run it forever and if you have enough patience
you know you will find the prime number that you're looking for
now again says this is an infinite list
it's not really an infinite lest because it's again it's a recipe for generating
inflation
only take the first 10 prime numbers
ish function will terminate
and just give us 10 first and prime numbers wont first compute all prime
numbers now
it will just do enough work to give you the first then
prime numbers or if we want to take div prime numbers that are less than 15
weekend do you stake while and again
just enough am work will be done
to do that now if imagine that your
bird language not are in a strict language
now you have to choose whether you want to take the first
rhymes or you want it takes primes up to a certain number
an because you cannot do this in this modular way
she cannot first computer primes are have a promise to compute the primes
and then take the first and and then used that very same
description of computing primes and then take
all the ones that are less 10-15
yes immediately fuse and
me see if I can as
do hearts to God you're not stand in front but
you want if you wish take down with prime said to one function
and take while less than a certain value with bribes
to get one function if you don't have a lazy valuation
and very nice paper to read here
is John use paper by functional programming matters that as many more
examples
of this from defected lazy evaluation
make sure go to more modular okay
that was the ants up to lecture series
I enjoyed it enormously
an I hope you did show to am
and police dried to
use everything you learned here to become
better programmer and I'm pretty sure that is the case
and I hope to see you in another MOOC
and at another time thank you so much
and again see you soon
bye bye