welcome back I hope that your
and mantle stack is not overblown because of all the recursion
so and the second part in or keep it very light
an an in particular I will help you
wit some of the exercises an that
are and on the website for this chapter
am and the very first lecture we showed
very quickly an and implementation of quick short
and Haskell an what we will do now is really well
and look is little bit more detail
at quick chart and Haskell and quick short
a.m. the idea richard is to sort a list
recursively by decomposing the list somehow
an recursively shorting those less
and then combining the results to God and every
think about that for a little bit began say I
if I have the empty list it's already shorted
an and now how do we
recurse a.m. how do we break up that list
into two parts that we can recursively short
and then easily combine the results to get a short list
well what we do is if we can take a look at the head of the list
and break this list into Wong with all the values that are
last or equal than the hat wong that all the values that are greater than the hat
then we can just you know recursively short
those two last and inject they had
in the middle and we're done and that's the
kind of the algorithmic and as Sens
of quick short am but as I already warned you
in the real implementation you're not creating new list
you're really mutating
the data structure in place to schwab
the elements and that's in aspect that this version of quick short
an doesn't show but it does show in this country girls if
structure alright here's the
in implementation of quick chart an
similar to the very first lecture
and only now it's called quick short instead of
after and so what we do when we have the empty last
it's already sordid when we all dish or the list
acts goals access
we create list with all the elements that are smaller
then a smaller equal the next and for that
we use the list comprehension me create a list of all the elements that are
larger than X
we sort well love dollars and we put
X in the middle this
is a very simple implementation of quicksort
but again it's also a very simplistic
implementation of quicksort but if you want to understand the structure
this is probably a very good illustration
an every 12
demonstrate how this works and that's abbreviate quick chart sq
said said you know the slide doesn't overblown so we want to short
the alleged 32 415 what we're going to do is we're
dignity had three and we're going to break up the rest of the list
into the elements that are less than equal to 3 and the launch that are
larger than three and saw
the elements that are last in this list are too
and Wong and the ones that are larger are for
and fuck showing GC so we recursively short
does and we inject an three in the meadow
an if me short the alleged
21 retake the hat we split
the remaining Leicester which is just wrong into the values that are smaller
and the values that are larger so are the ones that are larger and that's the
MD lest
the ones that are smaller net Swan and then
and we drop to
and the Middle and same on the right hand side
we take the first element
and we split the remainder of the less religious 5
in the elements that are larger than for SLs 5
and the elements that are smaller which is the empty list
and we inject forked there
in the middle again now an
the anti lists here and here
are already short it so nothing to do there
an we just have to short the lester while
element and you can verify that when you sort the list of one element its readers
that list itself and so if we
make those recursive goals there and
we get this list and I S E
that's the result is Wong to
3 for fight
okay it just got to walk that three
to I get the result okay
that was quick chart and
the exercises for this week there's a log of exercises to define
functions recursively am but I'm going to
do just got ball I of them here
with you so let's look at the first one here so it says
for jews a list with and identical Alamance saw
that's a function that takes an integer which is
the an and then it takes a value
a and it should return a
list of and call peace of
and that value a so how do we do that
well we do that by not to return volley we don't regard
over dish a and we have to build the last
so what we have to do is we have to define this
I'm recursively over the structure of this
integer so it again we have two cases
and and equal 0 if I replicate an element 0 dime
on I get the anti les TSO that cases easy
so if I want to replicate a value
and times what do i do I first replicated
and minus one-time so I get the list
of and modernise wrong times ace and then I cones
a on top so that long is easy
again you have to God look a little bit
and the UCI I'm doing recursion
over that guy there's two cases yeah he just
write them down and everything drop shot here is
a.m. another friend of us that we've seen and previous lectures
and their I warned you that in Haskell
lists don't have constant I'm access and
when we implement this function that will be very clear
so what we have to do is we have to take a list and the number
and then returned the element in that list
add that position of course we can do this
an using at a car drop or other functions but their goal here is to
define it
using recursion and since we have here
to rigors in structures the last
and the integer we're going to
defined this by Rick urging
over both gang so how
would that look well first thing is if we want to have a busy road element
of the list well that is the head of the list
are actually revivalist X cones excess
and this one is zero then thats
the elements for the first elements of the list
is the element at index 0 so that's and a simple on
if the list here is empty
and
well what do we do
that's a good question show probably if I want to index the
and element of the empty list and
that's going to give an error sorry let's not worry about that we're going
to put that as the Los gloss
all rights so now we can issue that
this run is not zero and this one is not empty
an if that 110 we're done if that one was empty
and this ron is not zero then we have an error so now they're both non-zero sure
what we do
is me say okay if this is
ex-cons excess and this is an what we do
as we take the index of the still up the list
and the and -1 and next so
simple recursion to it's just that we have to be a little careful
about the base case and the loss function we're going to be fine
using recursion here an the sides
if a given value is a member
on the list am of course
we could cheat air and not using recursion again
easily use filter our list comprehension
are something but the the goal here is to define dish
function using regurgitate and in this case
there's an obvious candidate to do you regard
over that this Celeste so ever looking for an element a
in the empty nest that's false
that element is not in the list ever looking
for an element a and the list ex-cons axis
well we have to check whether the head of the list
is equal to the value that you're looking
if that's the case we return true if that's not the case
then we just shirts for that element in the tail of the list
and eventually detailed alleged will be empty
so we will head the base case ever done now you see here that since word
checking equality on dish element
each hat of the list until we find it
did Taipei must support
equality and that's what you see here in the type so
weekend only search for value in the list
if the types of the list support equality
and that's why we get this constraint here so a must be
a member update type class EQIP
great so I hope that the dish
helped station a.m. additional exercises
and as I said and the on the web side
there's a lot of exercises you are you well and
do recursion an and if you get stock
try eating a banana and maybe it helps
are maybe in town you can eat do but not much
and that will work even better see you next week