1
00:00:00,179 --> 00:00:03,330
hey and welcome everybody to yet another

2
00:00:03,330 --> 00:00:07,730
FB 101 X a bit out you may have heard

3
00:00:07,730 --> 00:00:12,059
the and saying that developers

4
00:00:12,059 --> 00:00:15,250
are people that they learned coffee

5
00:00:15,250 --> 00:00:19,090
into goat well I'm a developer

6
00:00:19,090 --> 00:00:22,730
I turned coffee in the guard and in my
case also

7
00:00:22,730 --> 00:00:26,090
a ban on us an but here is a

8
00:00:26,090 --> 00:00:29,269
am string of cop coffee cups

9
00:00:29,269 --> 00:00:32,980
but yeah if you look at them like this

10
00:00:32,980 --> 00:00:36,800
this is looks like one object but what
we want

11
00:00:36,800 --> 00:00:40,270
is really don't want to have like one
object we won't

12
00:00:40,270 --> 00:00:44,300
to harsh this thing into

13
00:00:44,300 --> 00:00:47,360
a sequence of

14
00:00:47,360 --> 00:00:50,840
cups of coffee that we can drink

15
00:00:50,840 --> 00:00:55,489
such that we can go to bed right so here
you see them

16
00:00:55,489 --> 00:00:59,899
taking this thing that was one thing and
destructing it

17
00:00:59,899 --> 00:01:03,340
into its true meaning namely

18
00:01:03,340 --> 00:01:07,580
a whole bunch of coffee cups edge again
see

19
00:01:07,580 --> 00:01:12,479
right here an and what we're going to do
show you in this lecture

20
00:01:12,479 --> 00:01:16,640
how do not farce as strings of coffee
cups

21
00:01:16,640 --> 00:01:20,360
but we're going to parse strings of
characters

22
00:01:20,360 --> 00:01:24,009
into expressions alright so

23
00:01:24,009 --> 00:01:29,079
let's get going well there's a parser

24
00:01:29,079 --> 00:01:32,340
a parser is a program that

25
00:01:32,340 --> 00:01:35,640
analyzes a .pdf text to determine

26
00:01:35,640 --> 00:01:39,450
its syntactic structure show if we start
with two

27
00:01:39,450 --> 00:01:42,680
times three plus four what we want

28
00:01:42,680 --> 00:01:46,290
israel also have this to read it says
its due

29
00:01:46,290 --> 00:01:50,829
times to re plus for again

30
00:01:50,829 --> 00:01:55,619
last time show my string of topic

31
00:01:55,619 --> 00:01:59,340
go pick up here you see on the left
missus

32
00:01:59,340 --> 00:02:02,689
Justin unstructured think and then

33
00:02:02,689 --> 00:02:05,799
on the rides what we get is the

34
00:02:05,799 --> 00:02:09,679
real structure namely that it's the
coffee cups

35
00:02:09,679 --> 00:02:11,569
that where after

36
00:02:11,569 --> 00:02:15,800
K so the thing on the left has no
structure

37
00:02:15,800 --> 00:02:19,910
and the parser is trying to extract this
structure from that string

38
00:02:19,910 --> 00:02:23,319
and one of the nice things and

39
00:02:23,319 --> 00:02:28,049
of Haskell and in particular has
goal-less

40
00:02:28,049 --> 00:02:31,310
is that it's quiet and

41
00:02:31,310 --> 00:02:34,440
nice to ride parser it's quite elegant
show

42
00:02:34,440 --> 00:02:37,620
and it seems that every haskell
programmer

43
00:02:37,620 --> 00:02:41,150
at one point in her career will

44
00:02:41,150 --> 00:02:46,120
rides a partial to get that type of
parsers

45
00:02:46,120 --> 00:02:52,470
am that let formalized that show here we
have a function from string

46
00:02:52,470 --> 00:02:55,670
to to reach right that picture that we
showed

47
00:02:55,670 --> 00:02:59,620
to constrain and turned it into a tree
so we just defiant

48
00:02:59,620 --> 00:03:04,410
a type synonym here barger that's a
function that takes a string

49
00:03:04,410 --> 00:03:08,780
and readers 83 now

50
00:03:08,780 --> 00:03:12,160
we're going to generalize this type

51
00:03:12,160 --> 00:03:17,840
a little bit and to to make it easier to
construct departures first ball

52
00:03:17,840 --> 00:03:22,880
and when we parse a string we might not
need

53
00:03:22,880 --> 00:03:26,859
the complete string so there might be
some string leftover maybe

54
00:03:26,859 --> 00:03:30,019
now where r an string of coffee cups

55
00:03:30,019 --> 00:03:34,590
after two or three cups of coffee now it
might get some heartburn are

56
00:03:34,590 --> 00:03:37,849
we might be do a little bit too hyped up
Sol

57
00:03:37,849 --> 00:03:41,049
there will be some coffee cup select
alright so

58
00:03:41,049 --> 00:03:44,790
the diver parsers we're going to
refinance a little bit

59
00:03:44,790 --> 00:03:49,680
me say it will take a strained and it
will return a pair of 83

60
00:03:49,680 --> 00:03:53,540
and the rest of the story now

61
00:03:53,540 --> 00:03:58,400
what we can also do in general is that
when we take a string

62
00:03:58,400 --> 00:04:02,489
it can be parsed in many ways hey
there's no the unique waved if the

63
00:04:02,489 --> 00:04:03,840
grammars ambiguous

64
00:04:03,840 --> 00:04:09,400
or maybe I'm you know this string cannot
be parsed into a tree

65
00:04:09,400 --> 00:04:14,930
and and in that case am what we want to
do is we want to return a list

66
00:04:14,930 --> 00:04:20,250
of bears of treason strange okay sure
these are all the possible ways

67
00:04:20,250 --> 00:04:23,440
no I can parse the string

68
00:04:23,440 --> 00:04:28,319
into a bear of 83 and the remainder of
the string

69
00:04:28,319 --> 00:04:32,940
an and that list can be anti in case
there is no bars

70
00:04:32,940 --> 00:04:36,080
or even ambiguous an it can

71
00:04:36,080 --> 00:04:39,440
contain many pairs or if it's in

72
00:04:39,440 --> 00:04:42,560
if it's an honor and a good grammar it
will either be

73
00:04:42,560 --> 00:04:46,099
and list that as a single element or D&D
list

74
00:04:46,099 --> 00:04:50,319
and by the way that's another Haskell
Indian haskell

75
00:04:50,319 --> 00:04:55,360
we often usually lasts where other
languages would use the maybe died

76
00:04:55,360 --> 00:04:59,129
may be tied to something as either
nothing or a single value

77
00:04:59,129 --> 00:05:02,389
and the list can be 0 wall or more
values

78
00:05:02,389 --> 00:05:05,389
and has college very core a.m.

79
00:05:05,389 --> 00:05:08,780
common to just use a list for both and

80
00:05:08,780 --> 00:05:11,889
and the reason is that you know you can
use

81
00:05:11,889 --> 00:05:16,289
all the list operator schweid easily and
when you use lists

82
00:05:16,289 --> 00:05:20,400
and if you're super statically typed

83
00:05:20,400 --> 00:05:25,310
then you know it's not as precise but I
like that back trial which typically use

84
00:05:25,310 --> 00:05:27,129
less tied I'm not a big fan

85
00:05:27,129 --> 00:05:32,110
of using maybe type alright tonight the
next thing is dead

86
00:05:32,110 --> 00:05:37,120
really it doesn't matter whether we want
to return it three or not

87
00:05:37,120 --> 00:05:40,990
so we're going to Brammer dries die
parser

88
00:05:40,990 --> 00:05:44,029
over a and a can beat three

89
00:05:44,029 --> 00:05:48,110
it can be whatever we don't care so the
final diaper

90
00:05:48,110 --> 00:05:52,199
barger takes a string and returns a list
of bears

91
00:05:52,199 --> 00:05:56,250
of a that's the value that we're trying
to extract from the string

92
00:05:56,250 --> 00:06:01,050
and the rest of the string that way
don't use okay

93
00:06:01,050 --> 00:06:04,960
and in this case I'm as I mentioned

94
00:06:04,960 --> 00:06:08,740
we're going to keep things really simple
and we're going to

95
00:06:08,740 --> 00:06:11,759
only consider parsers that either
succeed

96
00:06:11,759 --> 00:06:14,879
with a single value or fail

97
00:06:14,879 --> 00:06:20,349
with an MTV value traditionalist if the
bar she succeeds will always be a single

98
00:06:20,349 --> 00:06:20,819
dumbest

99
00:06:20,819 --> 00:06:24,250
but we're not going to use the maybe
type right you can

100
00:06:24,250 --> 00:06:27,349
if you if you love the maybe type you
can take this at

101
00:06:27,349 --> 00:06:31,129
and chapter and rewrite everything using
a maybe type

102
00:06:31,129 --> 00:06:35,360
and well I think what you will discover

103
00:06:35,360 --> 00:06:39,400
is that it's not more elegant then using
lists

104
00:06:39,400 --> 00:06:43,380
and in fact I think lists with a code
word list

105
00:06:43,380 --> 00:06:47,229
will be more Alicante a ride

106
00:06:47,229 --> 00:06:52,280
now in order to build the complicated
part here's what we're going to do is

107
00:06:52,280 --> 00:06:54,970
we're going to go first create simple
bars

108
00:06:54,970 --> 00:06:58,259
and here's the simplest partially that
we can imagine

109
00:06:58,259 --> 00:07:01,490
that will just farce a single character

110
00:07:01,490 --> 00:07:05,520
K so this is a parser that will take a
string

111
00:07:05,520 --> 00:07:09,169
and return a pair Ave character

112
00:07:09,169 --> 00:07:13,090
and the rest of the string if the input
string

113
00:07:13,090 --> 00:07:16,199
is empty well

114
00:07:16,199 --> 00:07:19,220
then I cannot extracted

115
00:07:19,220 --> 00:07:23,419
a character from that shrinks and the
only thing I can do is returned

116
00:07:23,419 --> 00:07:26,930
the anti list but if the end to it is of
the form

117
00:07:26,930 --> 00:07:29,949
ex-cons excess then I can

118
00:07:29,949 --> 00:07:33,099
take the pair of the first character

119
00:07:33,099 --> 00:07:37,080
and the rest of the string and returned
a single the less of the result

120
00:07:37,080 --> 00:07:40,320
not notice here that we are not using

121
00:07:40,320 --> 00:07:44,020
kinda better matching on the left hand
side so we don't define

122
00:07:44,020 --> 00:07:47,580
item here using two clauses but we're
using

123
00:07:47,580 --> 00:07:51,490
along the expression read a case
expression

124
00:07:51,490 --> 00:07:55,500
that has to better match he said this is
the first time that we've seen

125
00:07:55,500 --> 00:07:58,940
this syntactic constructs and in use

126
00:07:58,940 --> 00:08:03,650
and also I must say I like this very
much because again it conveys

127
00:08:03,650 --> 00:08:07,240
that a parser is a function that takes
the endpoint

128
00:08:07,240 --> 00:08:12,280
and returns a list of bears and here you
can also see that it

129
00:08:12,280 --> 00:08:16,139
really returns either a empty nest are a
single dentist

130
00:08:16,139 --> 00:08:20,030
okay well there's another

131
00:08:20,030 --> 00:08:24,479
simple bar sure that we can imagine up
that's a barge in and always fails

132
00:08:24,479 --> 00:08:28,669
I'm well there's a bar should always
fails well

133
00:08:28,669 --> 00:08:31,750
for any input its readers the empty list

134
00:08:31,750 --> 00:08:35,880
and then if we have two bars are not
always fails

135
00:08:35,880 --> 00:08:39,630
we also need to bars are not always 6h

136
00:08:39,630 --> 00:08:43,300
but every want the bar should always
succeeds

137
00:08:43,300 --> 00:08:46,770
really needs to give it the value am

138
00:08:46,770 --> 00:08:49,130
with which it can succeed

139
00:08:49,130 --> 00:08:52,640
so the partial always 68 stakes
value-free

140
00:08:52,640 --> 00:08:56,470
and it takes the intuit it doesn't do
anything with the input

141
00:08:56,470 --> 00:08:59,480
just readers that value v when the input

142
00:08:59,480 --> 00:09:02,830
unchanged in a single to list ride

143
00:09:02,830 --> 00:09:06,220
and for reasons that we will see and
later

144
00:09:06,220 --> 00:09:10,390
is that this partial that always
succeeds its goal to return

145
00:09:10,390 --> 00:09:14,010
and dude large

146
00:09:14,010 --> 00:09:17,130
ol the M word and now my

147
00:09:17,130 --> 00:09:22,779
whole slide Scott all confused because I
mention the amber chill

148
00:09:22,779 --> 00:09:27,020
be very careful people when you mention
the M word

149
00:09:27,020 --> 00:09:30,240
biggest things will go spooky

150
00:09:30,240 --> 00:09:33,839
good so that was a partial always
exchange

151
00:09:33,839 --> 00:09:37,200
the parser not always fails and

152
00:09:37,200 --> 00:09:40,529
and now weekend look at some more

153
00:09:40,529 --> 00:09:43,950
and dressing barge so how do we take

154
00:09:43,950 --> 00:09:48,380
to parse errors and combine the results
so it's gonna be a we want to

155
00:09:48,380 --> 00:09:53,020
dry this parser and if that

156
00:09:53,020 --> 00:09:56,810
6h and we're done

157
00:09:56,810 --> 00:10:00,550
and otherwise we wanted ride at bars K

158
00:10:00,550 --> 00:10:05,100
so how do we find that swell we think
these two bar search

159
00:10:05,100 --> 00:10:08,140
we define a function and you

160
00:10:08,140 --> 00:10:13,040
fires are raging function takes the
input we try to parse the input

161
00:10:13,040 --> 00:10:16,170
using the first parser if that fails

162
00:10:16,170 --> 00:10:19,709
it will return the anti lest and which
case

163
00:10:19,709 --> 00:10:25,120
we tried the second parser on the input
and if the first bars are six each

164
00:10:25,120 --> 00:10:28,950
it will succeed when a single to left on
face value

165
00:10:28,950 --> 00:10:31,990
and the remainder of the input and we
just

166
00:10:31,990 --> 00:10:35,020
returned that same value alright

167
00:10:35,020 --> 00:10:38,390
so this thing here first dry spars RB

168
00:10:38,390 --> 00:10:42,579
a bit fails well thrive barger cue

169
00:10:42,579 --> 00:10:45,950
a departure B six each and well just

170
00:10:45,950 --> 00:10:49,300
return the result of that and then

171
00:10:49,300 --> 00:10:53,130
finally here we won't have a function
that takes a barger

172
00:10:53,130 --> 00:10:57,839
and a string and then oblige that barger
to industry show here

173
00:10:57,839 --> 00:11:00,810
you get a function from straying to

174
00:11:00,810 --> 00:11:03,550
a list a answering and

175
00:11:03,550 --> 00:11:07,380
well and just applies departure to the
input

176
00:11:07,380 --> 00:11:11,450
alright good thats

177
00:11:11,450 --> 00:11:15,250
I open up GEHA an

178
00:11:15,250 --> 00:11:19,050
and check out to the behavior of our
bars

179
00:11:19,050 --> 00:11:22,700
so that's headache and the a simple
parser

180
00:11:22,700 --> 00:11:25,920
and try to parse and the

181
00:11:25,920 --> 00:11:29,540
as something from the empty string that
doesn't work

182
00:11:29,540 --> 00:11:33,460
now let's try to parse the first value

183
00:11:33,460 --> 00:11:37,500
from the string ABC well in this case we
can

184
00:11:37,500 --> 00:11:40,730
extract the first a character from the
string

185
00:11:40,730 --> 00:11:44,090
and what you will see is that it will
return the list

186
00:11:44,090 --> 00:11:49,870
containing a pair the first value of
destroying the first character

187
00:11:49,870 --> 00:11:53,780
and the rest this ring and this is just
as redefine sorry

188
00:11:53,780 --> 00:11:57,320
verify here that our definition of the

189
00:11:57,320 --> 00:12:03,500
item parser works as expected let's try
departure that always fails

190
00:12:03,500 --> 00:12:06,650
so the bar so that always fails whatever
important we gave it

191
00:12:06,650 --> 00:12:10,790
it should fail should return the anti
lets show let's give it the input ABC

192
00:12:10,790 --> 00:12:14,010
and yes boom it returns the empty list

193
00:12:14,010 --> 00:12:17,450
let's try to parse are not always
six-eighths

194
00:12:17,450 --> 00:12:21,490
and in this case the parser net only six
each for the number one

195
00:12:21,490 --> 00:12:25,400
we applied that to the string ABC

196
00:12:25,400 --> 00:12:29,480
and guess what it succeeds by returning
a value on

197
00:12:29,480 --> 00:12:34,160
and leaving the and food and changed
okay

198
00:12:34,160 --> 00:12:38,050
now let's try to parse a nighttime

199
00:12:38,050 --> 00:12:41,990
and if that fails me images the

200
00:12:41,990 --> 00:12:45,340
return D so we used a barge in and
always succeed

201
00:12:45,340 --> 00:12:48,950
i'd soonish on ABC well since we can

202
00:12:48,950 --> 00:12:51,980
get the first element ABC

203
00:12:51,980 --> 00:12:55,510
that will succeed so we will just get
the result a

204
00:12:55,510 --> 00:12:59,200
BC alright and now

205
00:12:59,200 --> 00:13:02,240
and the Los example here

206
00:13:02,240 --> 00:13:07,160
is read/write departure that always
fails and if it fails

207
00:13:07,160 --> 00:13:10,490
we will try the bar so that always
six-eighths

208
00:13:10,490 --> 00:13:14,070
up this will fail

209
00:13:14,070 --> 00:13:18,240
initial succeed and it will succeed by
not consuming any input

210
00:13:18,240 --> 00:13:21,690
but just returning d and that's exactly
what

211
00:13:21,690 --> 00:13:28,110
Ghei well very fine for us alright

212
00:13:28,110 --> 00:13:31,970
the a bargain library by the way is
available all

213
00:13:31,970 --> 00:13:35,580
an from the at as go home page

214
00:13:35,580 --> 00:13:42,060
am notice that this parting is very
simple there's many many

215
00:13:42,060 --> 00:13:46,060
a more am advance parsing libraries are
there

216
00:13:46,060 --> 00:13:50,330
and as I mentioned the parser died here
that we have shown

217
00:13:50,330 --> 00:13:55,070
is an example of a long at an you know
you noticed when I mention the word

218
00:13:55,070 --> 00:13:55,810
orrin Hatch

219
00:13:55,810 --> 00:13:59,220
my clicker here went completely bizarre
work

220
00:13:59,220 --> 00:14:03,530
an so there's nothing really special
about Mon ads

221
00:14:03,530 --> 00:14:08,070
it's just a dime that has certain
operations on that

222
00:14:08,070 --> 00:14:12,100
so don't make a big deal of it because
when you make a big deal of it

223
00:14:12,100 --> 00:14:15,410
you will get into trouble like I did

224
00:14:15,410 --> 00:14:18,580
alright thanks let's take a short short
break

225
00:14:18,580 --> 00:14:22,580
and Xi'an after the break for part two

226
00:14:22,580 --> 00:14:23,220
on bars