1
00:00:00,320 --> 00:00:03,449
everybody welcome back in there

2
00:00:03,449 --> 00:00:07,330
previous segment we looked as a simple
recursive types

3
00:00:07,330 --> 00:00:10,730
of natural numbers and this segment

4
00:00:10,730 --> 00:00:14,280
we're going to look at a couple of more
interesting

5
00:00:14,280 --> 00:00:17,760
rigors dives and in particular

6
00:00:17,760 --> 00:00:23,010
I like dis type and remember when we
were doing the parser

7
00:00:23,010 --> 00:00:26,099
we were trying to build 8

8
00:00:26,099 --> 00:00:29,689
abstraction text 3 that we were Britain
that

9
00:00:29,689 --> 00:00:32,719
re presented the structure of our string

10
00:00:32,719 --> 00:00:38,579
as 83 but when we were doing parsers we
didn't know yet

11
00:00:38,579 --> 00:00:42,120
how to define new types so instead

12
00:00:42,120 --> 00:00:46,270
we computed the value of the expression
as we were parsing

13
00:00:46,270 --> 00:00:50,059
but which recursive types we get defined

14
00:00:50,059 --> 00:00:54,360
else read data type of expressions and
then define various

15
00:00:54,360 --> 00:00:59,730
interesting functions overdose
expressions how would redefine

16
00:00:59,730 --> 00:01:03,780
expressions in Haskell well again

17
00:01:03,780 --> 00:01:06,780
we define sure base class expression

18
00:01:06,780 --> 00:01:11,049
and then three concrete Sep types simple
value

19
00:01:11,049 --> 00:01:14,380
multiplication and addition

20
00:01:14,380 --> 00:01:20,580
of expressions and we can now ride today
at three on the previous slide

21
00:01:20,580 --> 00:01:23,790
as follows: we add Swan to

22
00:01:23,790 --> 00:01:30,110
to times three again 13 half

23
00:01:30,110 --> 00:01:35,000
expressions like this we can t find
recursive functions

24
00:01:35,000 --> 00:01:40,060
over D's expressions and again they all
follow the same structure we better

25
00:01:40,060 --> 00:01:40,829
match

26
00:01:40,829 --> 00:01:44,479
over each case here did

27
00:01:44,479 --> 00:01:48,579
look at the definitions that just gets
better matches and then we do something

28
00:01:48,579 --> 00:01:48,960
here

29
00:01:48,960 --> 00:01:54,159
again and in this case I want to compute
the size of an expression we want to

30
00:01:54,159 --> 00:01:54,880
pound

31
00:01:54,880 --> 00:01:59,210
how many values appear in that
expression well

32
00:01:59,210 --> 00:02:02,500
if it's a value which one otherwise we
go

33
00:02:02,500 --> 00:02:06,640
recursively calculate the size the left
and the right hand side

34
00:02:06,640 --> 00:02:11,129
and add them up and in an
object-oriented language

35
00:02:11,129 --> 00:02:12,680
you would probably makes

36
00:02:12,680 --> 00:02:15,959
size into a virtual matted of

37
00:02:15,959 --> 00:02:19,540
the expression superclass and then
override

38
00:02:19,540 --> 00:02:23,439
that virtual method and each of the
concrete septic

39
00:02:23,439 --> 00:02:28,090
here's the evaluator for expressions are
the interpreter

40
00:02:28,090 --> 00:02:32,560
so what it does is it takes an
expression and calculates the integer

41
00:02:32,560 --> 00:02:33,230
value

42
00:02:33,230 --> 00:02:37,189
if you already have a value your dumb
otherwise

43
00:02:37,189 --> 00:02:40,650
you evaluate the left hand side and the
right hand side

44
00:02:40,650 --> 00:02:44,530
and if you have a happen to have an
addition you add them up

45
00:02:44,530 --> 00:02:48,049
any case you have a multiplication you
multiply them

46
00:02:48,049 --> 00:02:53,549
when you look at the structure of the
ocean

47
00:02:53,549 --> 00:02:56,950
functions what you see

48
00:02:56,950 --> 00:03:02,359
is dead all they're doing is they're
replacing the constructors

49
00:03:02,359 --> 00:03:06,019
respectively value at Anmol

50
00:03:06,019 --> 00:03:10,040
by other functions let's go back here
and check that

51
00:03:10,040 --> 00:03:13,849
so in this case I replaced the
constructor fell

52
00:03:13,849 --> 00:03:18,760
by the constant function mom here I
replace the constructor at

53
00:03:18,760 --> 00:03:23,180
by plus and mold by plus and forty
valuator

54
00:03:23,180 --> 00:03:27,349
me replace this constructor by the
identity

55
00:03:27,349 --> 00:03:31,669
at by plus and the constructor mal

56
00:03:31,669 --> 00:03:35,040
by times and guess what

57
00:03:35,040 --> 00:03:39,180
if he would be fine a fold are over
expressions

58
00:03:39,180 --> 00:03:43,639
then we don't have to write to recursive
functions we can do it once

59
00:03:43,639 --> 00:03:48,069
and in that case for example the evil
function

60
00:03:48,069 --> 00:03:51,109
simply reads as follows: be

61
00:03:51,109 --> 00:03:55,430
replace Val fell constructor by the
identity

62
00:03:55,430 --> 00:03:58,669
we replace the at

63
00:03:58,669 --> 00:04:01,689
constructor by plus and be replaced

64
00:04:01,689 --> 00:04:07,250
the multiplication constructor by times
okay

65
00:04:07,250 --> 00:04:10,319
next example binary tree's

66
00:04:10,319 --> 00:04:13,349
here's an picture of a binary tree

67
00:04:13,349 --> 00:04:16,530
and we will deal that binary tree's

68
00:04:16,530 --> 00:04:20,430
that values in the notes and values

69
00:04:20,430 --> 00:04:26,030
delete and that leads to the following
recursive definition

70
00:04:26,030 --> 00:04:29,170
83 as either a leaf with an integer

71
00:04:29,170 --> 00:04:32,310
origin note with to ship to reach

72
00:04:32,310 --> 00:04:35,520
an integer right there and

73
00:04:35,520 --> 00:04:39,050
the picture of the previous slide it
comes this

74
00:04:39,050 --> 00:04:42,290
we had a note with five at the root

75
00:04:42,290 --> 00:04:48,140
and two ship knowledge they had three
and seven respectively

76
00:04:48,140 --> 00:04:52,580
et cetera so this value here

77
00:04:52,580 --> 00:04:56,320
represents that picture is easy easy 537

78
00:04:56,320 --> 00:04:59,540
on 469 an

79
00:04:59,540 --> 00:05:02,910
357 Wong for

80
00:05:02,910 --> 00:05:07,700
69 that sounds like a telephone number
okay

81
00:05:07,700 --> 00:05:11,570
now just like on expressions we can
define

82
00:05:11,570 --> 00:05:16,010
recursive functions on the structure of
binary to reach

83
00:05:16,010 --> 00:05:20,090
so for example weekend sure urge if they
given

84
00:05:20,090 --> 00:05:23,530
integer is present

85
00:05:23,530 --> 00:05:27,320
in this binary tree and then we will or
return a boolean

86
00:05:27,320 --> 00:05:30,460
and we have two cases

87
00:05:30,460 --> 00:05:35,310
if we have a leaf and we checked that FL
you had to leave

88
00:05:35,310 --> 00:05:40,500
is the same as the value that were
looking for and that's the result of the

89
00:05:40,500 --> 00:05:42,540
ball in the hole recursive invocation

90
00:05:42,540 --> 00:05:45,880
when we have no we

91
00:05:45,880 --> 00:05:48,880
check rather than value-added note

92
00:05:48,880 --> 00:05:52,200
is the younger looking for or

93
00:05:52,200 --> 00:05:56,500
we check either the value occurs in the
left subtree

94
00:05:56,500 --> 00:05:59,530
or we check weather at appears

95
00:05:59,530 --> 00:06:03,669
and right ship $3 okay

96
00:06:03,669 --> 00:06:07,040
but when the integer does not occur in
the three

97
00:06:07,040 --> 00:06:10,260
we will traverse the whole 3

98
00:06:10,260 --> 00:06:13,880
thats an

99
00:06:13,880 --> 00:06:16,960
the an algorithm there

100
00:06:16,960 --> 00:06:20,229
now let's look at another front in here

101
00:06:20,229 --> 00:06:26,850
let's try to and find it in a different
way so let's first day we take the three

102
00:06:26,850 --> 00:06:30,020
B-flat turn it into a list again

103
00:06:30,020 --> 00:06:33,490
so when we have a leaf be returned a
single the list

104
00:06:33,490 --> 00:06:38,640
when we have a three wit left and the
right subtree and a note

105
00:06:38,640 --> 00:06:42,210
we first flat in the last Sep 23 which
lies in that

106
00:06:42,210 --> 00:06:45,300
value and then we append there right
ship $3

107
00:06:45,300 --> 00:06:51,020
okay now we shaded three is a search
tree

108
00:06:51,020 --> 00:06:54,690
if when the flattened duelist it is

109
00:06:54,690 --> 00:06:57,750
shorted so our example

110
00:06:57,750 --> 00:07:01,170
is a search tree big us

111
00:07:01,170 --> 00:07:04,330
when we fly to net we get

112
00:07:04,330 --> 00:07:08,750
a short at the Swan 3 for 5679

113
00:07:08,750 --> 00:07:13,840
alright so now we can define

114
00:07:13,840 --> 00:07:18,580
occurs I'm as follows:

115
00:07:18,580 --> 00:07:22,240
if we have a search tree we can check
whether it's

116
00:07:22,240 --> 00:07:26,810
leaf when we have no we check whether
it's

117
00:07:26,810 --> 00:07:31,510
you know the values are the same we were
joined true not all

118
00:07:31,510 --> 00:07:34,690
says we know more about the structure we

119
00:07:34,690 --> 00:07:38,510
only traverse one-pot down the tree

120
00:07:38,510 --> 00:07:42,500
so we don't have to say if Id is not the
same we're checking this

121
00:07:42,500 --> 00:07:45,790
or rejecting that no we know that if

122
00:07:45,790 --> 00:07:49,710
and much less than an if the number that
were searching for

123
00:07:49,710 --> 00:07:56,570
is less than the nodes here then we only
have to search in the left subtree

124
00:07:56,570 --> 00:08:00,980
if this gentlemen here

125
00:08:00,980 --> 00:08:05,080
is larger than an damn we only have to
search

126
00:08:05,080 --> 00:08:08,360
in the right three so now we don't have
to go if

127
00:08:08,360 --> 00:08:11,720
sure to hold three because we have
exploited

128
00:08:11,720 --> 00:08:15,710
the fact that the values ended three

129
00:08:15,710 --> 00:08:21,310
are in a certain relation and redefined
thats relation by saying

130
00:08:21,310 --> 00:08:25,380
when you flatten the three the result is
a sorted list

131
00:08:25,380 --> 00:08:29,300
okay happy hacking

132
00:08:29,300 --> 00:08:30,400
and see you next week