1
00:00:00,870 --> 00:00:03,980
K welcome back to our very last check

2
00:00:03,980 --> 00:00:07,020
and above the very last lecture of

3
00:00:07,020 --> 00:00:11,660
functional programming on a long and and
this law

4
00:00:11,660 --> 00:00:16,309
law segment I'm going to make up for
some Kalani caught

5
00:00:16,309 --> 00:00:19,600
that we're all its couple of lectures
ago

6
00:00:19,600 --> 00:00:22,820
I don't know if not I don't know if you
remember

7
00:00:22,820 --> 00:00:26,769
but when we were talking about list
comprehension

8
00:00:26,769 --> 00:00:30,210
the road a really really

9
00:00:30,210 --> 00:00:33,340
really embarrassing version an

10
00:00:33,340 --> 00:00:37,180
of a prime number generator and

11
00:00:37,180 --> 00:00:41,680
we want to do better and that guards was
not

12
00:00:41,680 --> 00:00:46,149
the most beautiful code I've ridden my
live show that's redeem ourselves

13
00:00:46,149 --> 00:00:50,000
and rides a beautiful way to generate
Bryant

14
00:00:50,000 --> 00:00:55,070
that leverages lazy evaluation so here's
a

15
00:00:55,070 --> 00:00:59,379
recipe to generate and infinite less of
primes

16
00:00:59,379 --> 00:01:02,620
an in a very an

17
00:01:02,620 --> 00:01:06,000
nice way so we start to with the list

18
00:01:06,000 --> 00:01:10,220
of all natural numbers starting at two
and then

19
00:01:10,220 --> 00:01:13,850
we look initial list and we marked the
first

20
00:01:13,850 --> 00:01:17,369
value in that list as a prime

21
00:01:17,369 --> 00:01:22,159
so the first Brian here is to the next
thing we do

22
00:01:22,159 --> 00:01:26,100
as we say okay every node at this thing
is a prime

23
00:01:26,100 --> 00:01:29,350
then all multiples of DAT

24
00:01:29,350 --> 00:01:34,180
number are not brunch right show for
example to

25
00:01:34,180 --> 00:01:37,829
is I'm for is a multiple of 2

26
00:01:37,829 --> 00:01:41,729
so we know that for is not a prime
number

27
00:01:41,729 --> 00:01:45,710
saw given that the first mark prime

28
00:01:45,710 --> 00:01:49,930
we're going to delete we're going to
filter out all the multiples of that

29
00:01:49,930 --> 00:01:51,159
number from the list

30
00:01:51,159 --> 00:01:55,670
and then me just yeah we note that dan

31
00:01:55,670 --> 00:01:59,380
then next value is the prime and Mb

32
00:01:59,380 --> 00:02:04,360
elite all the duplicate and saw now

33
00:02:04,360 --> 00:02:07,790
this algorithm is really alt

34
00:02:07,790 --> 00:02:12,129
a this algorithm was really invented
before

35
00:02:12,129 --> 00:02:13,370
any of us he was

36
00:02:13,370 --> 00:02:16,470
for and this is difficult

37
00:02:16,470 --> 00:02:20,290
this if affair Dustin s I K to dismiss

38
00:02:20,290 --> 00:02:23,799
am invented by ancient Greek

39
00:02:23,799 --> 00:02:27,900
mathematicians its draw a picture here

40
00:02:27,900 --> 00:02:31,590
other you up the steps so we start here

41
00:02:31,590 --> 00:02:35,239
with the list %uh natural numbers
starting at 2

42
00:02:35,239 --> 00:02:38,940
first number here is a prime

43
00:02:38,940 --> 00:02:42,340
re-cross arts all the multiples of 2

44
00:02:42,340 --> 00:02:45,629
show we cross eyed for six a tan 12

45
00:02:45,629 --> 00:02:49,590
jethroe and now the first number

46
00:02:49,590 --> 00:02:53,829
that's not grossed out three is a prime
that's a prime

47
00:02:53,829 --> 00:02:59,200
for us already crossed out five is not a
multiple of 36 is a multiple of three

48
00:02:59,200 --> 00:03:00,690
was already crossed out

49
00:03:00,690 --> 00:03:05,209
not mine was not crossed our jet is a
multiple of three so we cross that are

50
00:03:05,209 --> 00:03:09,840
and we continue so now 5 is def

51
00:03:09,840 --> 00:03:13,090
the next prime are going to remove all
Multipla

52
00:03:13,090 --> 00:03:16,470
multiples of five et cetera so here is
she

53
00:03:16,470 --> 00:03:20,690
that fairly easily we find the first

54
00:03:20,690 --> 00:03:23,750
few prime numbers 2-3 5

55
00:03:23,750 --> 00:03:27,260
7 and 11 let's

56
00:03:27,260 --> 00:03:30,799
am translate this a into haskell alright

57
00:03:30,799 --> 00:03:34,069
and the beauty of this is dead this

58
00:03:34,069 --> 00:03:39,319
and algorithm is more or less directly
translated

59
00:03:39,319 --> 00:03:42,459
into haskell of course there's been

60
00:03:42,459 --> 00:03:45,590
their again you know there's a you which

61
00:03:45,590 --> 00:03:50,480
field of literature on different
versions of this save and more efficient

62
00:03:50,480 --> 00:03:51,099
versions

63
00:03:51,099 --> 00:03:54,549
you can spend years researching that and

64
00:03:54,549 --> 00:03:58,120
it's a beautiful area an but this is the
gonna

65
00:03:58,120 --> 00:04:02,579
this simplest version up this and to
show you the power

66
00:04:02,579 --> 00:04:07,389
ablaze evaluation and infinite lists to
restart a radiant

67
00:04:07,389 --> 00:04:11,199
lester natural numbers starting at two
and that we're going to

68
00:04:11,199 --> 00:04:15,220
civil out all these numbers just falling
recipe

69
00:04:15,220 --> 00:04:19,560
so how does this shit work well we start
with the first number in the less that's

70
00:04:19,560 --> 00:04:20,310
a prime

71
00:04:20,310 --> 00:04:23,560
and what we do is we returned that
number

72
00:04:23,560 --> 00:04:25,530
and then we say

73
00:04:25,530 --> 00:04:28,870
throw out all the multiples of P

74
00:04:28,870 --> 00:04:33,010
from excess and then recursively

75
00:04:33,010 --> 00:04:37,340
go back to step 2 save out all the
numbers from there

76
00:04:37,340 --> 00:04:40,340
her isn't a beautiful

77
00:04:40,340 --> 00:04:43,610
I mean here's a glide impaired if them

78
00:04:43,610 --> 00:04:48,890
description return to Step 2 but what we
see here

79
00:04:48,890 --> 00:04:52,040
is that return to Step 2 is really

80
00:04:52,040 --> 00:04:56,700
this recursive call here alright so we
started

81
00:04:56,700 --> 00:05:01,480
numbers from to an up the first number
must be prime

82
00:05:01,480 --> 00:05:05,150
we remove all the numbers that are
duplicate

83
00:05:05,150 --> 00:05:10,620
and then we just see if the result that
must now start with the next prime

84
00:05:10,620 --> 00:05:13,630
we're going to up with that don't keep
that

85
00:05:13,630 --> 00:05:17,930
and then save out the rest at setter are
you can also see

86
00:05:17,930 --> 00:05:22,060
why they're more efficient versions and
we already saw that here

87
00:05:22,060 --> 00:05:25,150
biggest an multiples of 2

88
00:05:25,150 --> 00:05:29,680
are eliminated and here multiples of 20
are eliminated and so

89
00:05:29,680 --> 00:05:33,230
you know there's many ways you can do
this sieve

90
00:05:33,230 --> 00:05:36,590
you know in a more efficient way with
gonna reels in

91
00:05:36,590 --> 00:05:40,630
whatever again I would just google for

92
00:05:40,630 --> 00:05:43,820
several pair Dawson as you will find

93
00:05:43,820 --> 00:05:48,020
a large collection of papers that
describe

94
00:05:48,020 --> 00:05:52,250
different variants of this that are much
more efficient

95
00:05:52,250 --> 00:05:56,040
and that use all gonna properties of
natural numbers

96
00:05:56,040 --> 00:05:59,150
to make this computation more efficient

97
00:05:59,150 --> 00:06:03,420
day but every execute yes primes

98
00:06:03,420 --> 00:06:08,010
this thing will just spew out an
infinite lest

99
00:06:08,010 --> 00:06:13,140
of prime numbers they will just continue
and not sure I'll get slower and slower

100
00:06:13,140 --> 00:06:15,180
because you know the prime numbers

101
00:06:15,180 --> 00:06:18,660
there will be more space between them
but yeah

102
00:06:18,660 --> 00:06:22,110
you can just run it forever and if you
have enough patience

103
00:06:22,110 --> 00:06:25,630
you know you will find the prime number
that you're looking for

104
00:06:25,630 --> 00:06:30,540
now again says this is an infinite list

105
00:06:30,540 --> 00:06:35,860
it's not really an infinite lest because
it's again it's a recipe for generating

106
00:06:35,860 --> 00:06:36,940
inflation

107
00:06:36,940 --> 00:06:40,130
only take the first 10 prime numbers

108
00:06:40,130 --> 00:06:43,910
ish function will terminate

109
00:06:43,910 --> 00:06:48,919
and just give us 10 first and prime
numbers wont first compute all prime

110
00:06:48,919 --> 00:06:49,750
numbers now

111
00:06:49,750 --> 00:06:53,160
it will just do enough work to give you
the first then

112
00:06:53,160 --> 00:06:58,210
prime numbers or if we want to take div
prime numbers that are less than 15

113
00:06:58,210 --> 00:07:01,280
weekend do you stake while and again

114
00:07:01,280 --> 00:07:04,990
just enough am work will be done

115
00:07:04,990 --> 00:07:08,360
to do that now if imagine that your

116
00:07:08,360 --> 00:07:11,850
bird language not are in a strict
language

117
00:07:11,850 --> 00:07:14,870
now you have to choose whether you want
to take the first

118
00:07:14,870 --> 00:07:19,199
rhymes or you want it takes primes up to
a certain number

119
00:07:19,199 --> 00:07:23,150
an because you cannot do this in this
modular way

120
00:07:23,150 --> 00:07:27,900
she cannot first computer primes are
have a promise to compute the primes

121
00:07:27,900 --> 00:07:31,669
and then take the first and and then
used that very same

122
00:07:31,669 --> 00:07:35,160
description of computing primes and then
take

123
00:07:35,160 --> 00:07:38,320
all the ones that are less 10-15

124
00:07:38,320 --> 00:07:41,720
yes immediately fuse and

125
00:07:41,720 --> 00:07:46,419
me see if I can as

126
00:07:46,419 --> 00:07:49,520
do hearts to God you're not stand in
front but

127
00:07:49,520 --> 00:07:54,190
you want if you wish take down with
prime said to one function

128
00:07:54,190 --> 00:07:58,080
and take while less than a certain value
with bribes

129
00:07:58,080 --> 00:08:01,630
to get one function if you don't have a
lazy valuation

130
00:08:01,630 --> 00:08:04,720
and very nice paper to read here

131
00:08:04,720 --> 00:08:09,150
is John use paper by functional
programming matters that as many more

132
00:08:09,150 --> 00:08:09,979
examples

133
00:08:09,979 --> 00:08:13,099
of this from defected lazy evaluation

134
00:08:13,099 --> 00:08:17,630
make sure go to more modular okay

135
00:08:17,630 --> 00:08:21,500
that was the ants up to lecture series

136
00:08:21,500 --> 00:08:25,479
I enjoyed it enormously

137
00:08:25,479 --> 00:08:28,860
an I hope you did show to am

138
00:08:28,860 --> 00:08:32,000
and police dried to

139
00:08:32,000 --> 00:08:35,150
use everything you learned here to
become

140
00:08:35,150 --> 00:08:38,430
better programmer and I'm pretty sure
that is the case

141
00:08:38,430 --> 00:08:41,529
and I hope to see you in another MOOC

142
00:08:41,529 --> 00:08:44,660
and at another time thank you so much

143
00:08:44,660 --> 00:08:47,680
and again see you soon

144
00:08:47,680 --> 00:08:47,940
bye bye