1
00:00:01,350 --> 00:00:03,629
welcome back in the previous section

2
00:00:03,629 --> 00:00:07,629
we talked about higher are two functions
functions that take

3
00:00:07,629 --> 00:00:11,059
functions as arguments are returned from
chance results

4
00:00:11,059 --> 00:00:15,719
and in particular really looked at to a
higher-order functions over lists

5
00:00:15,719 --> 00:00:18,800
filter and Matt and we

6
00:00:18,800 --> 00:00:23,039
indicated that these two functions had a
very similar structure

7
00:00:23,039 --> 00:00:26,800
they were both defiant inductively over
the structure

8
00:00:26,800 --> 00:00:30,880
of the list and since we are lazy
programmers

9
00:00:30,880 --> 00:00:35,770
we want to capture that pattern into yet
another higher order to function that we

10
00:00:35,770 --> 00:00:36,780
can then use

11
00:00:36,780 --> 00:00:42,730
to define filter and Matt or in fact as
many functions over lists as possible

12
00:00:42,730 --> 00:00:47,050
that function that captures recursively

13
00:00:47,050 --> 00:00:50,160
descending over to search herbalist is
gold

14
00:00:50,160 --> 00:00:54,760
fold are now there's also a function for

15
00:00:54,760 --> 00:00:58,920
al an them but this is Alan army mouth
full

16
00:00:58,920 --> 00:01:03,710
army fault from the right and just like
when we say that the winds

17
00:01:03,710 --> 00:01:07,610
in order went comes from the north full
dried

18
00:01:07,610 --> 00:01:11,229
is a fault that comes from the right
okay

19
00:01:11,229 --> 00:01:15,680
so it comes from the ride and so it
starts with EMT less and then folds

20
00:01:15,680 --> 00:01:18,820
from there here

21
00:01:18,820 --> 00:01:22,049
is an the definition of old R

22
00:01:22,049 --> 00:01:25,770
so as I said fold our captures the
essence

23
00:01:25,770 --> 00:01:29,090
of recursion over alleged and

24
00:01:29,090 --> 00:01:32,479
what what triggers and over list well
the F two cases

25
00:01:32,479 --> 00:01:36,259
once you're on the list is empty and
launch and the list

26
00:01:36,259 --> 00:01:39,290
is compost Ave list with

27
00:01:39,290 --> 00:01:42,899
value and in the front so in case

28
00:01:42,899 --> 00:01:47,710
we have an empty list well then be
applied is regarded function

29
00:01:47,710 --> 00:01:50,990
we have to pick a value for dnt let cell

30
00:01:50,990 --> 00:01:54,750
that say that values the so ever the
empty list is v

31
00:01:54,750 --> 00:01:58,850
now when we do ask applied to ex-cons

32
00:01:58,850 --> 00:02:02,939
Texas well we recursively collapse on
excess that was the whole goal

33
00:02:02,939 --> 00:02:07,070
and now we have to take the result is
recursive in for gation

34
00:02:07,070 --> 00:02:10,979
and combine it with the value on top and
we use

35
00:02:10,979 --> 00:02:13,560
the operator plus for that

36
00:02:13,560 --> 00:02:17,050
cell as maps dnt last to

37
00:02:17,050 --> 00:02:21,630
some value v and it managed matched a
non-empty list

38
00:02:21,630 --> 00:02:26,970
to some function plus and applies that
function plus to the head of the list

39
00:02:26,970 --> 00:02:31,690
axe and two the recursive call of the
function to its tail

40
00:02:31,690 --> 00:02:34,940
in some sense you can see what this
function after us

41
00:02:34,940 --> 00:02:40,270
as it traverses the list and replaces
the empty list ready

42
00:02:40,270 --> 00:02:44,380
and that replaces every OCR combs with
plush

43
00:02:44,380 --> 00:02:48,590
so it remains the structure shown other
way to say this is that

44
00:02:48,590 --> 00:02:54,020
after a home a morphism over list it
respects the structure of the list

45
00:02:54,020 --> 00:02:59,680
and that's got what where after him here
are a couple of

46
00:02:59,680 --> 00:03:02,730
and examples of using

47
00:03:02,730 --> 00:03:07,020
functions are of functions that are
defined recursively

48
00:03:07,020 --> 00:03:10,760
over less for example some takes

49
00:03:10,760 --> 00:03:14,070
the empty last return 0

50
00:03:14,070 --> 00:03:17,650
and when I some the list ex-cons excess
I

51
00:03:17,650 --> 00:03:21,210
do X plus this summer fixes the brother

52
00:03:21,210 --> 00:03:24,740
is very similar instead of here all I
have long

53
00:03:24,740 --> 00:03:28,780
and this other largely used star and if
we want to

54
00:03:28,780 --> 00:03:32,930
and all the values over less 12 and we
replaced the endless by

55
00:03:32,930 --> 00:03:36,480
through and dick bones by

56
00:03:36,480 --> 00:03:39,530
by Aunt okay show here you see

57
00:03:39,530 --> 00:03:43,790
very very similar structures and in
particular began

58
00:03:43,790 --> 00:03:47,240
in station a jiffy and plus and very
simply

59
00:03:47,240 --> 00:03:52,000
and in the first case the empty list he
is replaced by zero

60
00:03:52,000 --> 00:03:55,780
and I'm gongs that was the funny plus

61
00:03:55,780 --> 00:04:01,510
is plus in the second case here we
replace the empty list by one so be it

62
00:04:01,510 --> 00:04:02,280
was wrong

63
00:04:02,280 --> 00:04:06,080
re replaced combs by multiplication so

64
00:04:06,080 --> 00:04:09,710
funny plus is times and the Los case

65
00:04:09,710 --> 00:04:13,820
simple we replace the empty list by true

66
00:04:13,820 --> 00:04:17,140
Sophie is true and be replaced

67
00:04:17,140 --> 00:04:20,739
Gaunce by and so funny plus

68
00:04:20,739 --> 00:04:25,860
is and alright so here we can define

69
00:04:25,860 --> 00:04:28,120
so I'm product or an aunt

70
00:04:28,120 --> 00:04:32,140
in terms of old are simply as for are
off plus

71
00:04:32,140 --> 00:04:36,420
and 0 brother this fall are of times and
long

72
00:04:36,420 --> 00:04:40,920
et cetera okay so look what we have done

73
00:04:40,920 --> 00:04:45,270
the look at these three functions and we
see that these are just

74
00:04:45,270 --> 00:04:49,270
instances up this fall our function with
a particular

75
00:04:49,270 --> 00:04:56,080
the and a particular plus okay

76
00:04:56,080 --> 00:04:59,900
now how do we define

77
00:04:59,900 --> 00:05:02,990
an fold our

78
00:05:02,990 --> 00:05:06,310
an biggest you know abe

79
00:05:06,310 --> 00:05:09,670
we define this pattern here so now we
have to define this thing

80
00:05:09,670 --> 00:05:13,760
itself as a higher-order functions okay
so we have to have a function

81
00:05:13,760 --> 00:05:17,830
that takes F MV as parameters and then

82
00:05:17,830 --> 00:05:21,930
you know captures the recursion so
here's a definition of old are as a

83
00:05:21,930 --> 00:05:23,400
higher-order function

84
00:05:23,400 --> 00:05:27,180
it takes first an operation that
replaces

85
00:05:27,180 --> 00:05:32,940
and gongs so that's a function of Taipei
Arabi Arabi

86
00:05:32,940 --> 00:05:36,170
the second parameter is the that's their

87
00:05:36,170 --> 00:05:39,960
function that where r using are
developing that we're replacing

88
00:05:39,960 --> 00:05:43,000
and the empty list with

89
00:05:43,000 --> 00:05:46,400
and then we get a function from list a
to be

90
00:05:46,400 --> 00:05:49,770
and the definition here is
straightforward

91
00:05:49,770 --> 00:05:53,250
fold are of FMV and the empty list that
loss

92
00:05:53,250 --> 00:05:57,720
FB and fold our of after MV and ex-cons
axis

93
00:05:57,720 --> 00:06:02,150
is the rigors its invocation of old R of
FNB

94
00:06:02,150 --> 00:06:06,780
and then we go at on x so instead of the
funny plus

95
00:06:06,780 --> 00:06:10,570
we use ass alright am

96
00:06:10,570 --> 00:06:15,080
but even though you know you can look at
this definition this year's

97
00:06:15,080 --> 00:06:18,090
recursive definition the easiest way

98
00:06:18,090 --> 00:06:21,280
to think about fold our is

99
00:06:21,280 --> 00:06:25,130
as I said is a function that replaces
everywhere

100
00:06:25,130 --> 00:06:28,330
the empty list by P and

101
00:06:28,330 --> 00:06:32,280
it replaces the bones

102
00:06:32,280 --> 00:06:35,210
operator by

103
00:06:35,210 --> 00:06:38,350
is a so everywhere you see an empty list

104
00:06:38,350 --> 00:06:41,759
it becomes the everywhere easy calms

105
00:06:41,759 --> 00:06:44,889
it becomes ass okay and then

106
00:06:44,889 --> 00:06:48,520
just goes recursively like that an

107
00:06:48,520 --> 00:06:52,470
for example every and evaluate some

108
00:06:52,470 --> 00:06:58,000
123 and some is defined as for are off
plus an 0

109
00:06:58,000 --> 00:07:02,990
%uh 123 now we expanded the definition
of lest we know that

110
00:07:02,990 --> 00:07:06,800
want to dream each Wonka wants to comes
to on Sri

111
00:07:06,800 --> 00:07:10,210
on Santa lest and now you see again

112
00:07:10,210 --> 00:07:14,620
why the syntactic sugar for less show
useful because this would be very

113
00:07:14,620 --> 00:07:17,349
tedious the right we don't want the ride
is all the time so

114
00:07:17,349 --> 00:07:20,970
I'm super happy that has school has a
short and for lists

115
00:07:20,970 --> 00:07:24,820
that expanded in this case we have to
kind of think about it

116
00:07:24,820 --> 00:07:28,650
love it and now what happens is that
we're going to replace every occurrence

117
00:07:28,650 --> 00:07:29,690
of Commons

118
00:07:29,690 --> 00:07:34,710
by plus and every occurrence which is
one occurrence of the empty list

119
00:07:34,710 --> 00:07:39,300
by 0 let's do that

120
00:07:39,300 --> 00:07:42,320
so it becomes one place to place to
replace

121
00:07:42,320 --> 00:07:48,760
0 you see the structure of the list is
maintained fold our is a home a morphism

122
00:07:48,760 --> 00:07:49,669
over list

123
00:07:49,669 --> 00:07:53,490
structure is still the same just
replaces the constructors

124
00:07:53,490 --> 00:07:57,190
by another function if you're familiar

125
00:07:57,190 --> 00:08:02,530
with the Visitor pattern fault our
really very similar to this is a pattern

126
00:08:02,530 --> 00:08:06,349
visits the list and for every
constructor

127
00:08:06,349 --> 00:08:11,250
it applies to function and that function
is passed as the parameters to follow

128
00:08:11,250 --> 00:08:11,520
our

129
00:08:11,520 --> 00:08:15,229
and every evaluate one-plus to blustery

130
00:08:15,229 --> 00:08:18,370
assira the result 6

131
00:08:18,370 --> 00:08:21,389
now

132
00:08:21,389 --> 00:08:24,699
it's got obvious what happens with
brother 123

133
00:08:24,699 --> 00:08:28,699
we go to the same derivation product was
defined as

134
00:08:28,699 --> 00:08:31,770
times Wong on 234

135
00:08:31,770 --> 00:08:35,820
sure 123 we expand the list we've
replaced

136
00:08:35,820 --> 00:08:39,839
every ogres have columns by times and
every occurrence of the empty list by

137
00:08:39,839 --> 00:08:40,599
one

138
00:08:40,599 --> 00:08:45,050
we evaluate this expression

139
00:08:45,050 --> 00:08:49,050
and the result is six again and

140
00:08:49,050 --> 00:08:52,910
good now let's look at some other

141
00:08:52,910 --> 00:08:57,730
examples of fold our for example the
length of the list we can define the

142
00:08:57,730 --> 00:08:58,790
length of the list

143
00:08:58,790 --> 00:09:03,050
function that takes a less to pay for
all types a.m. readers and

144
00:09:03,050 --> 00:09:07,510
the length of the anti list 0 and the
length of the list

145
00:09:07,510 --> 00:09:10,899
ex-cons X's Wong plus the land of excess

146
00:09:10,899 --> 00:09:16,050
nah haskell programmers are lazy and
since you're not using X

147
00:09:16,050 --> 00:09:19,329
in the right hand side here we just

148
00:09:19,329 --> 00:09:22,829
use in underscore Forex so we don't have
to think about the name

149
00:09:22,829 --> 00:09:25,829
showed we remembered the underscore

150
00:09:25,829 --> 00:09:30,120
when be used at is really just means
this is a variable but we're not going

151
00:09:30,120 --> 00:09:32,020
to use that in the right hand side

152
00:09:32,020 --> 00:09:35,820
well it's obvious here that length

153
00:09:35,820 --> 00:09:40,649
is another instance of all our we're
placing the empty list with zero

154
00:09:40,649 --> 00:09:44,459
amber replacing calms with

155
00:09:44,459 --> 00:09:47,520
the function that throws away axe

156
00:09:47,520 --> 00:09:50,899
and then adds wrong to the recursive
invocation

157
00:09:50,899 --> 00:09:54,790
of fold are on the list I'll

158
00:09:54,790 --> 00:09:58,430
let's make this explicit so we and

159
00:09:58,430 --> 00:10:01,810
do like the wanted three that's the same
as lange

160
00:10:01,810 --> 00:10:04,930
long columns to gone streak on sandy
less

161
00:10:04,930 --> 00:10:08,690
this is a much one-plus one-plus

162
00:10:08,690 --> 00:10:12,029
120 I just three

163
00:10:12,029 --> 00:10:16,110
so if we've replaced combs with the
function

164
00:10:16,110 --> 00:10:19,750
London underscore an one plus an

165
00:10:19,750 --> 00:10:23,269
and ENT list by zero we get exactly

166
00:10:23,269 --> 00:10:27,180
what we want is a so Kalmus is replaced

167
00:10:27,180 --> 00:10:31,690
in this an step here by the function

168
00:10:31,690 --> 00:10:34,420
that throws away the first argument so
we don't ride

169
00:10:34,420 --> 00:10:37,920
it and then it takes a second argument
and at 12 it

170
00:10:37,920 --> 00:10:41,600
you see exactly that is what happens in
that state

171
00:10:41,600 --> 00:10:46,700
so what we have found is at length can
be defined

172
00:10:46,700 --> 00:10:50,200
as fold our on loan to underscore an

173
00:10:50,200 --> 00:10:56,070
one plus an and 0 let's look at another
example

174
00:10:56,070 --> 00:10:59,470
reverse reverse up the ante less

175
00:10:59,470 --> 00:11:03,730
is the empty nest and reverse up ex-cons
excess

176
00:11:03,730 --> 00:11:07,029
is reversed excess abante

177
00:11:07,029 --> 00:11:11,010
red the singleton list affects and

178
00:11:11,010 --> 00:11:14,160
by now we should be drains to see this
pattern

179
00:11:14,160 --> 00:11:17,500
ride to BC two cases the empty list

180
00:11:17,500 --> 00:11:22,079
and the list ex-cons excess and on the
right hand side

181
00:11:22,079 --> 00:11:26,310
we see that function reverse applied to
the rest of the list

182
00:11:26,310 --> 00:11:32,000
plus some function you know involving
acts that we do

183
00:11:32,000 --> 00:11:35,630
that we applied to the result of

184
00:11:35,630 --> 00:11:39,760
and this regard to the invocation K and
in this case

185
00:11:39,760 --> 00:11:42,910
the reverse is a bit tricky because you
know the

186
00:11:42,910 --> 00:11:46,110
recursive call appears here on the left

187
00:11:46,110 --> 00:11:51,180
instead of with length where it appeared
and the recursive call

188
00:11:51,180 --> 00:11:55,490
let's go back to length here where the
recursive call

189
00:11:55,490 --> 00:11:58,829
appeared on the right an

190
00:11:58,829 --> 00:12:03,040
but me this wrong for us %ah that's just
simple

191
00:12:03,040 --> 00:12:08,040
and no worries so let's go get reverse
reverse 133

192
00:12:08,040 --> 00:12:11,649
again that's the same as reverse wants
to

193
00:12:11,649 --> 00:12:15,230
const regan's empty last and

194
00:12:15,230 --> 00:12:18,990
which is the same as empty list

195
00:12:18,990 --> 00:12:23,459
concatenated 23 concatenated 22

196
00:12:23,459 --> 00:12:28,100
concatenated 21 which is 321

197
00:12:28,100 --> 00:12:31,139
so what function IRI

198
00:12:31,139 --> 00:12:34,889
using to replace combs and what function

199
00:12:34,889 --> 00:12:38,600
are reusing to replace the emptiness
okay

200
00:12:38,600 --> 00:12:42,250
CEC hear that things are good reversed
but

201
00:12:42,250 --> 00:12:44,310
that shouldn't fool us because we see
here

202
00:12:44,310 --> 00:12:48,650
ear that the parentheses are right so we
are doing something with Wong

203
00:12:48,650 --> 00:12:52,420
and the recursive call defected you know
this is reversed

204
00:12:52,420 --> 00:12:56,640
that is not important okay so if we
replace

205
00:12:56,640 --> 00:13:00,210
comments with the function X

206
00:13:00,210 --> 00:13:03,240
X's goes to X's

207
00:13:03,240 --> 00:13:06,570
gone check so there you see that's what

208
00:13:06,570 --> 00:13:10,980
the action appears to the left here and
to the right here

209
00:13:10,980 --> 00:13:15,430
and we replace and the list with the
empty nest and it all works out

210
00:13:15,430 --> 00:13:18,750
alright so we can define

211
00:13:18,750 --> 00:13:22,470
reverse as follow our %uh

212
00:13:22,470 --> 00:13:25,970
this function Murray replaced columns by
the function

213
00:13:25,970 --> 00:13:30,110
combs takes a value and something else
and we put

214
00:13:30,110 --> 00:13:33,279
X to the right because we're reversing
the list

215
00:13:33,279 --> 00:13:38,250
and the anti list is already reverse out

216
00:13:38,250 --> 00:13:42,130
so now our every a ride this

217
00:13:42,130 --> 00:13:45,960
in .3 style an we can ride this

218
00:13:45,960 --> 00:13:49,030
a little bit shorter and and ride it as

219
00:13:49,030 --> 00:13:52,300
yeah the offending wise

220
00:13:52,300 --> 00:13:56,080
2d and is the same as folding

221
00:13:56,080 --> 00:13:59,190
combs width wise alright so

222
00:13:59,190 --> 00:14:02,400
if you want to attend the function I'm
really replace

223
00:14:02,400 --> 00:14:06,760
if I want to attend the list I'm just
replacing the empty list by that list

224
00:14:06,760 --> 00:14:08,339
and I'm leaving all the

225
00:14:08,339 --> 00:14:12,060
gone up okay

226
00:14:12,060 --> 00:14:15,490
so why is fall are useful well

227
00:14:15,490 --> 00:14:19,750
many recursive functions on lists its
like some

228
00:14:19,750 --> 00:14:23,480
and some

229
00:14:23,480 --> 00:14:26,839
products and or and are

230
00:14:26,839 --> 00:14:31,730
quite simple to define using follow our
we have seal and to address a little bit

231
00:14:31,730 --> 00:14:32,380
harder

232
00:14:32,380 --> 00:14:35,490
and reverse red rose even a little bit
harder

233
00:14:35,490 --> 00:14:40,040
but still very simple now and the
exercises

234
00:14:40,040 --> 00:14:44,010
you will have to and define map and
filter

235
00:14:44,010 --> 00:14:47,510
in times of old R an

236
00:14:47,510 --> 00:14:51,430
so we leave that to the exercises but
said she had seen these examples that

237
00:14:51,430 --> 00:14:52,910
should be easy

238
00:14:52,910 --> 00:14:55,500
but the nice thing is that we can t find

239
00:14:55,500 --> 00:14:59,360
properties an of all our

240
00:14:59,360 --> 00:15:02,460
suggest fusion and a banana split room

241
00:15:02,460 --> 00:15:05,600
that's why I was eating a banana

242
00:15:05,600 --> 00:15:08,980
earlier on and and we can use these

243
00:15:08,980 --> 00:15:14,100
properties to calculate more efficient
programs in particular fusion means

244
00:15:14,100 --> 00:15:18,060
it I have two functions one that's gonna
be used for all the hard to get

245
00:15:18,060 --> 00:15:22,480
surgery first one less than return other
lest and if I do another folder

246
00:15:22,480 --> 00:15:26,390
are on the result of that I confuse
these two together says that the

247
00:15:26,390 --> 00:15:28,180
intermediate lesson never

248
00:15:28,180 --> 00:15:32,700
an constructed so programs can be
optimized

249
00:15:32,700 --> 00:15:37,320
if you ride them in this higher order
patterns okay so don't forget to do the

250
00:15:37,320 --> 00:15:38,300
exercises

251
00:15:38,300 --> 00:15:41,900
and part of them will be to define

252
00:15:41,900 --> 00:15:45,070
map and filter in terms of old R

253
00:15:45,070 --> 00:15:49,130
but by now that should be easy and you
can do that

254
00:15:49,130 --> 00:15:52,650
while you're enjoying a nice ban on
thank you

255
00:15:52,650 --> 00:15:54,320
and see a next time