everybody welcome back in there
previous segment we looked as a simple recursive types
of natural numbers and this segment
we're going to look at a couple of more interesting
rigors dives and in particular
I like dis type and remember when we were doing the parser
we were trying to build 8
abstraction text 3 that we were Britain that
re presented the structure of our string
as 83 but when we were doing parsers we didn't know yet
how to define new types so instead
we computed the value of the expression as we were parsing
but which recursive types we get defined
else read data type of expressions and then define various
interesting functions overdose expressions how would redefine
expressions in Haskell well again
we define sure base class expression
and then three concrete Sep types simple value
multiplication and addition
of expressions and we can now ride today at three on the previous slide
as follows: we add Swan to
to times three again 13 half
expressions like this we can t find recursive functions
over D's expressions and again they all follow the same structure we better
match
over each case here did
look at the definitions that just gets better matches and then we do something
here
again and in this case I want to compute the size of an expression we want to
pound
how many values appear in that expression well
if it's a value which one otherwise we go
recursively calculate the size the left and the right hand side
and add them up and in an object-oriented language
you would probably makes
size into a virtual matted of
the expression superclass and then override
that virtual method and each of the concrete septic
here's the evaluator for expressions are the interpreter
so what it does is it takes an expression and calculates the integer
value
if you already have a value your dumb otherwise
you evaluate the left hand side and the right hand side
and if you have a happen to have an addition you add them up
any case you have a multiplication you multiply them
when you look at the structure of the ocean
functions what you see
is dead all they're doing is they're replacing the constructors
respectively value at Anmol
by other functions let's go back here and check that
so in this case I replaced the constructor fell
by the constant function mom here I replace the constructor at
by plus and mold by plus and forty valuator
me replace this constructor by the identity
at by plus and the constructor mal
by times and guess what
if he would be fine a fold are over expressions
then we don't have to write to recursive functions we can do it once
and in that case for example the evil function
simply reads as follows: be
replace Val fell constructor by the identity
we replace the at
constructor by plus and be replaced
the multiplication constructor by times okay
next example binary tree's
here's an picture of a binary tree
and we will deal that binary tree's
that values in the notes and values
delete and that leads to the following recursive definition
83 as either a leaf with an integer
origin note with to ship to reach
an integer right there and
the picture of the previous slide it comes this
we had a note with five at the root
and two ship knowledge they had three and seven respectively
et cetera so this value here
represents that picture is easy easy 537
on 469 an
357 Wong for
69 that sounds like a telephone number okay
now just like on expressions we can define
recursive functions on the structure of binary to reach
so for example weekend sure urge if they given
integer is present
in this binary tree and then we will or return a boolean
and we have two cases
if we have a leaf and we checked that FL you had to leave
is the same as the value that were looking for and that's the result of the
ball in the hole recursive invocation
when we have no we
check rather than value-added note
is the younger looking for or
we check either the value occurs in the left subtree
or we check weather at appears
and right ship $3 okay
but when the integer does not occur in the three
we will traverse the whole 3
thats an
the an algorithm there
now let's look at another front in here
let's try to and find it in a different way so let's first day we take the three
B-flat turn it into a list again
so when we have a leaf be returned a single the list
when we have a three wit left and the right subtree and a note
we first flat in the last Sep 23 which lies in that
value and then we append there right ship $3
okay now we shaded three is a search tree
if when the flattened duelist it is
shorted so our example
is a search tree big us
when we fly to net we get
a short at the Swan 3 for 5679
alright so now we can define
occurs I'm as follows:
if we have a search tree we can check whether it's
leaf when we have no we check whether it's
you know the values are the same we were joined true not all
says we know more about the structure we
only traverse one-pot down the tree
so we don't have to say if Id is not the same we're checking this
or rejecting that no we know that if
and much less than an if the number that were searching for
is less than the nodes here then we only have to search in the left subtree
if this gentlemen here
is larger than an damn we only have to search
in the right three so now we don't have to go if
sure to hold three because we have exploited
the fact that the values ended three
are in a certain relation and redefined thats relation by saying
when you flatten the three the result is a sorted list
okay happy hacking
and see you next week