hello everybody I am nd nm another TA for other functional programming course
they were gonna solve a.m. an exercise
about higher order functions the in particular an exercise about the
church numerals whether church numerals church numerous are just a a
representation of natural numbers
that uses functions and function application a
we represent the number as the the application
a function like a number n will be
represented as the application over function
and I'm on some 0 element that will define
so let's start by looking at the type of it a church numerous here we can see
Church Ave
is defined as a type that takes a function from a two-way
0 which would be the successor function
as era element the second a and returns it
and a which will be there to our find a representation of
number now let's look how can we define such numbers
well it's only the findings 0 0 the just the function
that takes another function
the successor function F here n
which represent our base number and they would just return
n not doing anything so that will be our 0 much
now the the representation of one
as you can the as you can guess already
the will apply the function the successor function one-time
on I'm on the base number the
the representation of two will be applied
sometimes on the base number but now sees
we r haskell programmers we liken sizes then
we can see that we're represent to as on the a function composition of
so apply f2 times F composed at and we can leave out the
the base number we leave 3n6 for later
because I will show you in some other things and now lets
the
let's see how can we represent a church number
as an integer how can we convert from I'll go from a church number
to an integer well it's not that are
we said a church number is a function that takes
a successor function and a base number so for our
natural numbers the those will be the successor function
last one the and the base number
it will be 0 so if we have to if you knew
again yes let here then it'll be okay let's apply
plus one then let's play again plus one on a base number that will be 0
and that will give us to thats let us now
go the other way around and ago from an integer
to a church representation
I am to do this we do but a matching
and then we go by induction so we have
the base case I'll is if you want to convert 0
and then we can just return the representations ear that we defined
appears this one the
anything have a number n then
we use the induction step and we say okay let's
how do we do it let's increment with some
in from in function that we will define later its increment
the a n -1 representation of the church number
and then we're occur simply call into church now
let's define Inc includes just incrementing so
is just saying OK let's at one to our
X number that we get okay now
the what is the next step well we need to
define this ed because we don't have it so how do we add
a.m. to church numerals well
the base idea the the basic idea is
that of apply at why times
and then apply the result representation of that
Eckstein's so then we'll have the first flight times and then we'll play it
again
a X times and then we have X plus I'm
why and here we can see
so we apply I
okay this we apply and why times
at on the base number
the result of this will be again a church in a row
and then which would be the representation of our the
base number and then we apply this on
Eckstein's again and diesel give us the addition
now let's try the addition an
you so first they want to show you in states
okay see if it works we have we want to
the transform
the 1337
into a church representation then we want to transform it back
into an integer and if around this we see that get the integer back
and now want to try the addition the and its
you so we say okay let's ed their turf representation of 2&3
and then less transform into an integer so we can actually see
on the command line and we have five and it works yes
the now let's go on multiplication
let's start by here okay so let's look at three
let's say we want to a multiply 3
by two so we had three its stakes G
any the composes G
three times now what we can see is that
we can just look down here to have six
we need to replace these G by a composition
as every time have the G we want
to have to as well so we replaces G
with the representation of two which would be
F composed F as you can see up here and then a for composite three times we will
see that we have
F a.m. six times and will have the representation of
of six now how do people do this
well let's see here the definition we have
I multiply X&Y let's look at them first one
which is the explicit one then
we can remove the perimeters and the right to a composition
so again multiplication its representation
a church in were also land that an function
that what it does it
applies to X the result
of applying F on why so
its sup instead of using F on X
it uses wise over F which is
basically what I was saying so it gets
the G any subsidies with the representation of the other number
there for creating the modification now
this is only an a an example we can actually from
define other operations for example exponentiation we can define of church
booleans another things nice things that
we will leave you as as an exercise
and this was all thank you very much for listening and happy acting