welcome back in the previous section
we talked about higher are two functions functions that take
functions as arguments are returned from chance results
and in particular really looked at to a higher-order functions over lists
filter and Matt and we
indicated that these two functions had a very similar structure
they were both defiant inductively over the structure
of the list and since we are lazy programmers
we want to capture that pattern into yet another higher order to function that we
can then use
to define filter and Matt or in fact as many functions over lists as possible
that function that captures recursively
descending over to search herbalist is gold
fold are now there's also a function for
al an them but this is Alan army mouth full
army fault from the right and just like when we say that the winds
in order went comes from the north full dried
is a fault that comes from the right okay
so it comes from the ride and so it starts with EMT less and then folds
from there here
is an the definition of old R
so as I said fold our captures the essence
of recursion over alleged and
what what triggers and over list well the F two cases
once you're on the list is empty and launch and the list
is compost Ave list with
value and in the front so in case
we have an empty list well then be applied is regarded function
we have to pick a value for dnt let cell
that say that values the so ever the empty list is v
now when we do ask applied to ex-cons
Texas well we recursively collapse on excess that was the whole goal
and now we have to take the result is recursive in for gation
and combine it with the value on top and we use
the operator plus for that
cell as maps dnt last to
some value v and it managed matched a non-empty list
to some function plus and applies that function plus to the head of the list
axe and two the recursive call of the function to its tail
in some sense you can see what this function after us
as it traverses the list and replaces the empty list ready
and that replaces every OCR combs with plush
so it remains the structure shown other way to say this is that
after a home a morphism over list it respects the structure of the list
and that's got what where after him here are a couple of
and examples of using
functions are of functions that are defined recursively
over less for example some takes
the empty last return 0
and when I some the list ex-cons excess I
do X plus this summer fixes the brother
is very similar instead of here all I have long
and this other largely used star and if we want to
and all the values over less 12 and we replaced the endless by
through and dick bones by
by Aunt okay show here you see
very very similar structures and in particular began
in station a jiffy and plus and very simply
and in the first case the empty list he is replaced by zero
and I'm gongs that was the funny plus
is plus in the second case here we replace the empty list by one so be it
was wrong
re replaced combs by multiplication so
funny plus is times and the Los case
simple we replace the empty list by true
Sophie is true and be replaced
Gaunce by and so funny plus
is and alright so here we can define
so I'm product or an aunt
in terms of old are simply as for are off plus
and 0 brother this fall are of times and long
et cetera okay so look what we have done
the look at these three functions and we see that these are just
instances up this fall our function with a particular
the and a particular plus okay
now how do we define
an fold our
an biggest you know abe
we define this pattern here so now we have to define this thing
itself as a higher-order functions okay so we have to have a function
that takes F MV as parameters and then
you know captures the recursion so here's a definition of old are as a
higher-order function
it takes first an operation that replaces
and gongs so that's a function of Taipei Arabi Arabi
the second parameter is the that's their
function that where r using are developing that we're replacing
and the empty list with
and then we get a function from list a to be
and the definition here is straightforward
fold are of FMV and the empty list that loss
FB and fold our of after MV and ex-cons axis
is the rigors its invocation of old R of FNB
and then we go at on x so instead of the funny plus
we use ass alright am
but even though you know you can look at this definition this year's
recursive definition the easiest way
to think about fold our is
as I said is a function that replaces everywhere
the empty list by P and
it replaces the bones
operator by
is a so everywhere you see an empty list
it becomes the everywhere easy calms
it becomes ass okay and then
just goes recursively like that an
for example every and evaluate some
123 and some is defined as for are off plus an 0
%uh 123 now we expanded the definition of lest we know that
want to dream each Wonka wants to comes to on Sri
on Santa lest and now you see again
why the syntactic sugar for less show useful because this would be very
tedious the right we don't want the ride is all the time so
I'm super happy that has school has a short and for lists
that expanded in this case we have to kind of think about it
love it and now what happens is that we're going to replace every occurrence
of Commons
by plus and every occurrence which is one occurrence of the empty list
by 0 let's do that
so it becomes one place to place to replace
0 you see the structure of the list is maintained fold our is a home a morphism
over list
structure is still the same just replaces the constructors
by another function if you're familiar
with the Visitor pattern fault our really very similar to this is a pattern
visits the list and for every constructor
it applies to function and that function is passed as the parameters to follow
our
and every evaluate one-plus to blustery
assira the result 6
now
it's got obvious what happens with brother 123
we go to the same derivation product was defined as
times Wong on 234
sure 123 we expand the list we've replaced
every ogres have columns by times and every occurrence of the empty list by
one
we evaluate this expression
and the result is six again and
good now let's look at some other
examples of fold our for example the length of the list we can define the
length of the list
function that takes a less to pay for all types a.m. readers and
the length of the anti list 0 and the length of the list
ex-cons X's Wong plus the land of excess
nah haskell programmers are lazy and since you're not using X
in the right hand side here we just
use in underscore Forex so we don't have to think about the name
showed we remembered the underscore
when be used at is really just means this is a variable but we're not going
to use that in the right hand side
well it's obvious here that length
is another instance of all our we're placing the empty list with zero
amber replacing calms with
the function that throws away axe
and then adds wrong to the recursive invocation
of fold are on the list I'll
let's make this explicit so we and
do like the wanted three that's the same as lange
long columns to gone streak on sandy less
this is a much one-plus one-plus
120 I just three
so if we've replaced combs with the function
London underscore an one plus an
and ENT list by zero we get exactly
what we want is a so Kalmus is replaced
in this an step here by the function
that throws away the first argument so we don't ride
it and then it takes a second argument and at 12 it
you see exactly that is what happens in that state
so what we have found is at length can be defined
as fold our on loan to underscore an
one plus an and 0 let's look at another example
reverse reverse up the ante less
is the empty nest and reverse up ex-cons excess
is reversed excess abante
red the singleton list affects and
by now we should be drains to see this pattern
ride to BC two cases the empty list
and the list ex-cons excess and on the right hand side
we see that function reverse applied to the rest of the list
plus some function you know involving acts that we do
that we applied to the result of
and this regard to the invocation K and in this case
the reverse is a bit tricky because you know the
recursive call appears here on the left
instead of with length where it appeared and the recursive call
let's go back to length here where the recursive call
appeared on the right an
but me this wrong for us %ah that's just simple
and no worries so let's go get reverse reverse 133
again that's the same as reverse wants to
const regan's empty last and
which is the same as empty list
concatenated 23 concatenated 22
concatenated 21 which is 321
so what function IRI
using to replace combs and what function
are reusing to replace the emptiness okay
CEC hear that things are good reversed but
that shouldn't fool us because we see here
ear that the parentheses are right so we are doing something with Wong
and the recursive call defected you know this is reversed
that is not important okay so if we replace
comments with the function X
X's goes to X's
gone check so there you see that's what
the action appears to the left here and to the right here
and we replace and the list with the empty nest and it all works out
alright so we can define
reverse as follow our %uh
this function Murray replaced columns by the function
combs takes a value and something else and we put
X to the right because we're reversing the list
and the anti list is already reverse out
so now our every a ride this
in .3 style an we can ride this
a little bit shorter and and ride it as
yeah the offending wise
2d and is the same as folding
combs width wise alright so
if you want to attend the function I'm really replace
if I want to attend the list I'm just replacing the empty list by that list
and I'm leaving all the
gone up okay
so why is fall are useful well
many recursive functions on lists its like some
and some
products and or and are
quite simple to define using follow our we have seal and to address a little bit
harder
and reverse red rose even a little bit harder
but still very simple now and the exercises
you will have to and define map and filter
in times of old R an
so we leave that to the exercises but said she had seen these examples that
should be easy
but the nice thing is that we can t find
properties an of all our
suggest fusion and a banana split room
that's why I was eating a banana
earlier on and and we can use these
properties to calculate more efficient programs in particular fusion means
it I have two functions one that's gonna be used for all the hard to get
surgery first one less than return other lest and if I do another folder
are on the result of that I confuse these two together says that the
intermediate lesson never
an constructed so programs can be optimized
if you ride them in this higher order patterns okay so don't forget to do the
exercises
and part of them will be to define
map and filter in terms of old R
but by now that should be easy and you can do that
while you're enjoying a nice ban on thank you
and see a next time