1
00:00:01,480 --> 00:00:04,240
welcome back I hope that your

2
00:00:04,240 --> 00:00:08,620
and mantle stack is not overblown
because of all the recursion

3
00:00:08,620 --> 00:00:13,070
so and the second part in or keep it
very light

4
00:00:13,070 --> 00:00:17,240
an an in particular I will help you

5
00:00:17,240 --> 00:00:20,810
wit some of the exercises an that

6
00:00:20,810 --> 00:00:24,410
are and on the website for this chapter

7
00:00:24,410 --> 00:00:28,730
am and the very first lecture we showed

8
00:00:28,730 --> 00:00:33,680
very quickly an and implementation of
quick short

9
00:00:33,680 --> 00:00:37,620
and Haskell an what we will do now is
really well

10
00:00:37,620 --> 00:00:40,680
and look is little bit more detail

11
00:00:40,680 --> 00:00:44,940
at quick chart and Haskell and quick
short

12
00:00:44,940 --> 00:00:49,440
a.m. the idea richard is to sort a list

13
00:00:49,440 --> 00:00:53,590
recursively by decomposing the list
somehow

14
00:00:53,590 --> 00:00:57,120
an recursively shorting those less

15
00:00:57,120 --> 00:01:01,690
and then combining the results to God
and every

16
00:01:01,690 --> 00:01:04,909
think about that for a little bit began
say I

17
00:01:04,909 --> 00:01:08,700
if I have the empty list it's already
shorted

18
00:01:08,700 --> 00:01:11,939
an and now how do we

19
00:01:11,939 --> 00:01:16,200
recurse a.m. how do we break up that
list

20
00:01:16,200 --> 00:01:19,759
into two parts that we can recursively
short

21
00:01:19,759 --> 00:01:23,860
and then easily combine the results to
get a short list

22
00:01:23,860 --> 00:01:28,619
well what we do is if we can take a look
at the head of the list

23
00:01:28,619 --> 00:01:32,990
and break this list into Wong with all
the values that are

24
00:01:32,990 --> 00:01:38,740
last or equal than the hat wong that all
the values that are greater than the hat

25
00:01:38,740 --> 00:01:42,119
then we can just you know recursively
short

26
00:01:42,119 --> 00:01:45,310
those two last and inject they had

27
00:01:45,310 --> 00:01:48,479
in the middle and we're done and that's
the

28
00:01:48,479 --> 00:01:51,590
kind of the algorithmic and as Sens

29
00:01:51,590 --> 00:01:55,159
of quick short am but as I already
warned you

30
00:01:55,159 --> 00:01:58,610
in the real implementation you're not
creating new list

31
00:01:58,610 --> 00:02:00,600
you're really mutating

32
00:02:00,600 --> 00:02:03,650
the data structure in place to schwab

33
00:02:03,650 --> 00:02:07,750
the elements and that's in aspect that
this version of quick short

34
00:02:07,750 --> 00:02:12,360
an doesn't show but it does show in this
country girls if

35
00:02:12,360 --> 00:02:15,650
structure alright here's the

36
00:02:15,650 --> 00:02:19,130
in implementation of quick chart an

37
00:02:19,130 --> 00:02:22,160
similar to the very first lecture

38
00:02:22,160 --> 00:02:25,550
and only now it's called quick short
instead of

39
00:02:25,550 --> 00:02:30,440
after and so what we do when we have the
empty last

40
00:02:30,440 --> 00:02:34,170
it's already sordid when we all dish or
the list

41
00:02:34,170 --> 00:02:37,300
acts goals access

42
00:02:37,300 --> 00:02:42,300
we create list with all the elements
that are smaller

43
00:02:42,300 --> 00:02:48,250
then a smaller equal the next and for
that

44
00:02:48,250 --> 00:02:52,680
we use the list comprehension me create
a list of all the elements that are

45
00:02:52,680 --> 00:02:54,069
larger than X

46
00:02:54,069 --> 00:02:58,030
we sort well love dollars and we put

47
00:02:58,030 --> 00:03:02,930
X in the middle this

48
00:03:02,930 --> 00:03:06,590
is a very simple implementation of
quicksort

49
00:03:06,590 --> 00:03:10,320
but again it's also a very simplistic

50
00:03:10,320 --> 00:03:14,790
implementation of quicksort but if you
want to understand the structure

51
00:03:14,790 --> 00:03:18,079
this is probably a very good
illustration

52
00:03:18,079 --> 00:03:21,620
an every 12

53
00:03:21,620 --> 00:03:26,470
demonstrate how this works and that's
abbreviate quick chart sq

54
00:03:26,470 --> 00:03:31,170
said said you know the slide doesn't
overblown so we want to short

55
00:03:31,170 --> 00:03:35,430
the alleged 32 415 what we're going to
do is we're

56
00:03:35,430 --> 00:03:39,519
dignity had three and we're going to
break up the rest of the list

57
00:03:39,519 --> 00:03:44,030
into the elements that are less than
equal to 3 and the launch that are

58
00:03:44,030 --> 00:03:47,410
larger than three and saw

59
00:03:47,410 --> 00:03:50,579
the elements that are last in this list
are too

60
00:03:50,579 --> 00:03:53,620
and Wong and the ones that are larger
are for

61
00:03:53,620 --> 00:03:57,609
and fuck showing GC so we recursively
short

62
00:03:57,609 --> 00:04:02,540
does and we inject an three in the
meadow

63
00:04:02,540 --> 00:04:05,980
an if me short the alleged

64
00:04:05,980 --> 00:04:09,079
21 retake the hat we split

65
00:04:09,079 --> 00:04:13,260
the remaining Leicester which is just
wrong into the values that are smaller

66
00:04:13,260 --> 00:04:16,350
and the values that are larger so are
the ones that are larger and that's the

67
00:04:16,350 --> 00:04:17,150
MD lest

68
00:04:17,150 --> 00:04:20,590
the ones that are smaller net Swan and
then

69
00:04:20,590 --> 00:04:23,820
and we drop to

70
00:04:23,820 --> 00:04:27,199
and the Middle and same on the right
hand side

71
00:04:27,199 --> 00:04:30,250
we take the first element

72
00:04:30,250 --> 00:04:33,280
and we split the remainder of the less
religious 5

73
00:04:33,280 --> 00:04:37,210
in the elements that are larger than for
SLs 5

74
00:04:37,210 --> 00:04:41,030
and the elements that are smaller which
is the empty list

75
00:04:41,030 --> 00:04:44,070
and we inject forked there

76
00:04:44,070 --> 00:04:47,530
in the middle again now an

77
00:04:47,530 --> 00:04:50,919
the anti lists here and here

78
00:04:50,919 --> 00:04:54,400
are already short it so nothing to do
there

79
00:04:54,400 --> 00:04:58,010
an we just have to short the lester
while

80
00:04:58,010 --> 00:05:02,840
element and you can verify that when you
sort the list of one element its readers

81
00:05:02,840 --> 00:05:07,449
that list itself and so if we

82
00:05:07,449 --> 00:05:11,229
make those recursive goals there and

83
00:05:11,229 --> 00:05:15,300
we get this list and I S E

84
00:05:15,300 --> 00:05:18,599
that's the result is Wong to

85
00:05:18,599 --> 00:05:22,070
3 for fight

86
00:05:22,070 --> 00:05:25,370
okay it just got to walk that three

87
00:05:25,370 --> 00:05:29,900
to I get the result okay

88
00:05:29,900 --> 00:05:33,169
that was quick chart and

89
00:05:33,169 --> 00:05:38,150
the exercises for this week there's a
log of exercises to define

90
00:05:38,150 --> 00:05:42,570
functions recursively am but I'm going
to

91
00:05:42,570 --> 00:05:46,620
do just got ball I of them here

92
00:05:46,620 --> 00:05:50,560
with you so let's look at the first one
here so it says

93
00:05:50,560 --> 00:05:55,210
for jews a list with and identical
Alamance saw

94
00:05:55,210 --> 00:05:58,840
that's a function that takes an integer
which is

95
00:05:58,840 --> 00:06:02,520
the an and then it takes a value

96
00:06:02,520 --> 00:06:06,229
a and it should return a

97
00:06:06,229 --> 00:06:09,680
list of and call peace of

98
00:06:09,680 --> 00:06:14,530
and that value a so how do we do that

99
00:06:14,530 --> 00:06:19,610
well we do that by not to return volley
we don't regard

100
00:06:19,610 --> 00:06:22,969
over dish a and we have to build the
last

101
00:06:22,969 --> 00:06:26,849
so what we have to do is we have to
define this

102
00:06:26,849 --> 00:06:29,439
I'm recursively over the structure of
this

103
00:06:29,439 --> 00:06:32,520
integer so it again we have two cases

104
00:06:32,520 --> 00:06:37,990
and and equal 0 if I replicate an
element 0 dime

105
00:06:37,990 --> 00:06:42,389
on I get the anti les TSO that cases
easy

106
00:06:42,389 --> 00:06:45,610
so if I want to replicate a value

107
00:06:45,610 --> 00:06:49,750
and times what do i do I first
replicated

108
00:06:49,750 --> 00:06:53,409
and minus one-time so I get the list

109
00:06:53,409 --> 00:06:57,270
of and modernise wrong times ace and
then I cones

110
00:06:57,270 --> 00:07:01,060
a on top so that long is easy

111
00:07:01,060 --> 00:07:04,340
again you have to God look a little bit

112
00:07:04,340 --> 00:07:07,560
and the UCI I'm doing recursion

113
00:07:07,560 --> 00:07:12,009
over that guy there's two cases yeah he
just

114
00:07:12,009 --> 00:07:16,849
write them down and everything drop shot
here is

115
00:07:16,849 --> 00:07:21,629
a.m. another friend of us that we've
seen and previous lectures

116
00:07:21,629 --> 00:07:24,939
and their I warned you that in Haskell

117
00:07:24,939 --> 00:07:28,400
lists don't have constant I'm access and

118
00:07:28,400 --> 00:07:32,219
when we implement this function that
will be very clear

119
00:07:32,219 --> 00:07:36,520
so what we have to do is we have to take
a list and the number

120
00:07:36,520 --> 00:07:41,009
and then returned the element in that
list

121
00:07:41,009 --> 00:07:46,039
add that position of course we can do
this

122
00:07:46,039 --> 00:07:51,289
an using at a car drop or other
functions but their goal here is to

123
00:07:51,289 --> 00:07:52,089
define it

124
00:07:52,089 --> 00:07:55,819
using recursion and since we have here

125
00:07:55,819 --> 00:07:58,870
to rigors in structures the last

126
00:07:58,870 --> 00:08:02,039
and the integer we're going to

127
00:08:02,039 --> 00:08:05,629
defined this by Rick urging

128
00:08:05,629 --> 00:08:09,610
over both gang so how

129
00:08:09,610 --> 00:08:14,849
would that look well first thing is if
we want to have a busy road element

130
00:08:14,849 --> 00:08:18,400
of the list well that is the head of the
list

131
00:08:18,400 --> 00:08:22,060
are actually revivalist X cones excess

132
00:08:22,060 --> 00:08:25,270
and this one is zero then thats

133
00:08:25,270 --> 00:08:28,909
the elements for the first elements of
the list

134
00:08:28,909 --> 00:08:33,469
is the element at index 0 so that's and
a simple on

135
00:08:33,469 --> 00:08:37,310
if the list here is empty

136
00:08:37,310 --> 00:08:40,260
and

137
00:08:40,260 --> 00:08:41,919
well what do we do

138
00:08:41,919 --> 00:08:45,770
that's a good question show probably if
I want to index the

139
00:08:45,770 --> 00:08:49,200
and element of the empty list and

140
00:08:49,200 --> 00:08:52,920
that's going to give an error sorry
let's not worry about that we're going

141
00:08:52,920 --> 00:08:54,830
to put that as the Los gloss

142
00:08:54,830 --> 00:08:58,060
all rights so now we can issue that

143
00:08:58,060 --> 00:09:01,640
this run is not zero and this one is not
empty

144
00:09:01,640 --> 00:09:06,150
an if that 110 we're done if that one
was empty

145
00:09:06,150 --> 00:09:11,100
and this ron is not zero then we have an
error so now they're both non-zero sure

146
00:09:11,100 --> 00:09:11,840
what we do

147
00:09:11,840 --> 00:09:15,050
is me say okay if this is

148
00:09:15,050 --> 00:09:19,420
ex-cons excess and this is an what we do

149
00:09:19,420 --> 00:09:23,340
as we take the index of the still up the
list

150
00:09:23,340 --> 00:09:27,240
and the and -1 and next so

151
00:09:27,240 --> 00:09:31,910
simple recursion to it's just that we
have to be a little careful

152
00:09:31,910 --> 00:09:37,910
about the base case and the loss
function we're going to be fine

153
00:09:37,910 --> 00:09:41,630
using recursion here an the sides

154
00:09:41,630 --> 00:09:45,330
if a given value is a member

155
00:09:45,330 --> 00:09:48,980
on the list am of course

156
00:09:48,980 --> 00:09:52,590
we could cheat air and not using
recursion again

157
00:09:52,590 --> 00:09:55,820
easily use filter our list comprehension

158
00:09:55,820 --> 00:09:59,740
are something but the the goal here is
to define dish

159
00:09:59,740 --> 00:10:03,570
function using regurgitate and in this
case

160
00:10:03,570 --> 00:10:07,070
there's an obvious candidate to do you
regard

161
00:10:07,070 --> 00:10:11,430
over that this Celeste so ever looking
for an element a

162
00:10:11,430 --> 00:10:14,540
in the empty nest that's false

163
00:10:14,540 --> 00:10:19,070
that element is not in the list ever
looking

164
00:10:19,070 --> 00:10:23,870
for an element a and the list ex-cons
axis

165
00:10:23,870 --> 00:10:27,070
well we have to check whether the head
of the list

166
00:10:27,070 --> 00:10:30,360
is equal to the value that you're
looking

167
00:10:30,360 --> 00:10:35,350
if that's the case we return true if
that's not the case

168
00:10:35,350 --> 00:10:39,480
then we just shirts for that element in
the tail of the list

169
00:10:39,480 --> 00:10:43,180
and eventually detailed alleged will be
empty

170
00:10:43,180 --> 00:10:48,170
so we will head the base case ever done
now you see here that since word

171
00:10:48,170 --> 00:10:51,550
checking equality on dish element

172
00:10:51,550 --> 00:10:55,010
each hat of the list until we find it

173
00:10:55,010 --> 00:10:58,190
did Taipei must support

174
00:10:58,190 --> 00:11:01,269
equality and that's what you see here in
the type so

175
00:11:01,269 --> 00:11:04,839
weekend only search for value in the
list

176
00:11:04,839 --> 00:11:08,899
if the types of the list support
equality

177
00:11:08,899 --> 00:11:13,100
and that's why we get this constraint
here so a must be

178
00:11:13,100 --> 00:11:16,130
a member update type class EQIP

179
00:11:16,130 --> 00:11:19,690
great so I hope that the dish

180
00:11:19,690 --> 00:11:23,070
helped station a.m. additional exercises

181
00:11:23,070 --> 00:11:26,570
and as I said and the on the web side

182
00:11:26,570 --> 00:11:30,029
there's a lot of exercises you are you
well and

183
00:11:30,029 --> 00:11:34,279
do recursion an and if you get stock

184
00:11:34,279 --> 00:11:38,490
try eating a banana and maybe it helps

185
00:11:38,490 --> 00:11:42,269
are maybe in town you can eat do but not
much

186
00:11:42,269 --> 00:11:45,170
and that will work even better see you
next week