000 wat
cameras already a running sorry sorry guys
an so
functional programming with bananas
lenses the barbed wire
left at home and and blogs
is not something for hipsters an
a sexually style from show programming
where ry leverage higher-order functions
and that will be the topic of today's lecture
we've seen several higher
French is already but we never actually
named them specifically so hired a function
as a function that takes an argument a function as an argument
or reader readers and function as a result
as you get this function twice twice
is defined as follows: Trisha avonex goals
ass of at affects if we look at the type of two ice
and again remember this index tries double go along in stride has type
then on the right to be /c that it takes as the first parameter a function
from a2a and it returns a function
from a2a and if we look at the definition again with that type in mind
we see that the tights make sense twice
takes a function that function goes from a2a
then addiction argument of type A
attacks and then it returns a value of type they were on how does it do that it
applies everyone's
which detection a transform said and another a
showed the arguments to the second application %uh vast will also be of
type A
and you apply at the second time to return
value uptime of Taipei
so twice is a higher-order function
because it takes a function as its first argument
also notice how the brain disease are
used the brand to seize on the first argument
are explicit because it's a function from a2a and
records for function dives associate in the ride so we have to boot
the brand she's there but we don't have to put them
on the right hand side but if we would put all the branches is there
the dive would look a arrow a arrow
a arrow a why are
higher-order functions useful well there's this
think that programmers love to do and that's not to repeat yourself
don't repeat yourself and with higher order functions
we allow this thing to be encoded in the language because whenever we see
repetition
we abstracted pattern into higher-order function
and then weekend applied that higher-order function
with various arguments I'm to specify what is difference between
you know all the common uses of this common pattern
a show common programming idioms can be encoded as functions
written in the language itself and laziness here plays
a important role because if you don't have a lazy evaluation
arguments might be evaluated prematurely
and then the effect is not the same as the
an pattern where you instantiate the arguments
am for the parameters another
way to look at this is that we can define
domain-specific languages as collection of higher-order functions so in Haskell
people often talk about domain specific languages read a mean
API's and other way to say that
is these are embed domain-specific languages
and then the third a.m.
advantage of higher order functions is dead
these higher-order functions have algebraic properties
that we get used to reason about programs and these higher-order
properties
these properties of higher-order functions are these algebraic properties
they hold irrespective of how are you
which parameters you bastard them so you can
if I'm properties of these programs gonna in a general way
and then used them and all along and we will see
several of these examples as we go twice
may look like you know weird little weird to say maybe a little bit
syntactic
but I'm here's another higher-order functions that we use all the time
and this is the map function so map
takes a function an
then take Celeste and then applies that function to
every element of the list if you look at the type of map al-arabi
arrow less than a hour or less to be
you have very little choice then to apply that function
to every element of the list because it gonna do you know the type
really strongly suggests that the implementation
you have a function of type A to B you have a function
a lists mean values of Taipei and what you require
is a list mid-valley just I B well what can you do
well you just transform every element in the input list
using that function to get to the required output list
and that's exactly how map is defined
now that you're gonna application of map
so we map the sections and blush
function plus Wong remember the lecture
we had about sections so this is a function that
implicitly defined to be llame the axe express ROM
and we met that function over the last bomb 357
so this function will just adwan to every element of the list
and that's what you see there we get the result this 2468
am
weekend define the map function using list comprehension
very easy in some sense you can say list comprehension
are designed to define
map so map applies to the function ass
to every element in the list know there's the list comprehension I mean
it's like exactly the
what I said and atthe
steak every element Akshardham the list axis
apply f/2.8 and returned less
at short nap this am
but we can also define map recursively
and and some sense I prefer myself the recursive definition
and why do I prefer to recursive definition well we will see later
that when be defined map recursively
and we define other higher or the French is recursively
we see a pattern that we can abstract
again so we can abstract nap into a super high order to function
and that will be twofold function but for now let's look at the recursive
definition of just map
a map of the empty nest is the anti less
and map of the list axe
bombs access well what we do is we
first three gir simply map af over access
so we map at over the rest of the last and then re
concatenate Aframax two different a ride
so this is a recursive definition this inductive over the structure of the list
so we have
either the empty list re: at the case where the list
is build using axe gone axis
be recursively map app over the rest of the list
and and cons have a fax on top here's another
higher are to function filter so filter takes
a predicate fun shiver a tubal
that dick celeste every day there's another less the new list
where all the elements for rich that predicate
does not hold are removed at
that's why it's called filter show all these elements are filter the way
for instance everyone to filter
all the even numbers from the list values from Monte dam
we get all the even values 246
8 and then again
filter can be defined in two ways first long
is red list comprehension ce and
fairly simple so what we do is we say take every
element axe I have access and if
be a fax is true then you put action the result list
and that's it so the definition of filter using less comprehension
looks very simple but again I prefer
the recursive definition and the recursive definition has
very very similar structure to the map function
its defiant inductively on the structure of the list so
we have two cases either we have the anti lest
are we have lest ex-cons axis
and we filter a all the values for rich is spreading and does not hold from the
MPLS trial
the only thing we can do is return the empty list
every filter out all the values
for HP does not hold from the list ex-cons
Texas well they're still cases first
be a fix can be true so that's this case and then
this is the second casement be a fix is false well
it be a fix is true we filter
recursively the rest of the list and then we
concatenate X on top an otherwise we just forget about tax
and filtered the rest of the list so here you see it
its gonna are SM ball as the
list comprehension definition but the important thing
is dead this definition here follows exactly the same structure of Mac
and in the context of you know saying
don't repeat ourselves we should be able to abstract
that commonality between filter and map
is either both the recursively defined over
analysts we should be able to factor in and out
into another higher function and that higher
function is full bar and that will be the topic
of the neck
section thank you and see issue