1
00:00:00,210 --> 00:00:04,500
hello everybody I am nd nm another TA
for other functional programming course

2
00:00:04,500 --> 00:00:08,029
they were gonna solve a.m. an exercise

3
00:00:08,029 --> 00:00:12,730
about higher order functions the in
particular an exercise about the

4
00:00:12,730 --> 00:00:17,190
church numerals whether church numerals
church numerous are just a a

5
00:00:17,190 --> 00:00:19,029
representation of natural numbers

6
00:00:19,029 --> 00:00:22,420
that uses functions and function
application a

7
00:00:22,420 --> 00:00:26,250
we represent the number as the the
application

8
00:00:26,250 --> 00:00:29,590
a function like a number n will be

9
00:00:29,590 --> 00:00:33,090
represented as the application over
function

10
00:00:33,090 --> 00:00:37,820
and I'm on some 0 element that will
define

11
00:00:37,820 --> 00:00:41,960
so let's start by looking at the type of
it a church numerous here we can see

12
00:00:41,960 --> 00:00:43,110
Church Ave

13
00:00:43,110 --> 00:00:47,020
is defined as a type that takes a
function from a two-way

14
00:00:47,020 --> 00:00:50,430
0 which would be the successor function

15
00:00:50,430 --> 00:00:53,969
as era element the second a and returns
it

16
00:00:53,969 --> 00:00:57,670
and a which will be there to our find a
representation of

17
00:00:57,670 --> 00:01:01,309
number now let's look how can we define
such numbers

18
00:01:01,309 --> 00:01:06,090
well it's only the findings 0 0 the just
the function

19
00:01:06,090 --> 00:01:09,340
that takes another function

20
00:01:09,340 --> 00:01:12,590
the successor function F here n

21
00:01:12,590 --> 00:01:16,060
which represent our base number and they
would just return

22
00:01:16,060 --> 00:01:20,040
n not doing anything so that will be our
0 much

23
00:01:20,040 --> 00:01:23,189
now the the representation of one

24
00:01:23,189 --> 00:01:26,970
as you can the as you can guess already

25
00:01:26,970 --> 00:01:32,150
the will apply the function the
successor function one-time

26
00:01:32,150 --> 00:01:36,790
on I'm on the base number the

27
00:01:36,790 --> 00:01:39,869
the representation of two will be
applied

28
00:01:39,869 --> 00:01:43,280
sometimes on the base number but now
sees

29
00:01:43,280 --> 00:01:47,060
we r haskell programmers we liken sizes
then

30
00:01:47,060 --> 00:01:51,829
we can see that we're represent to as on
the a function composition of

31
00:01:51,829 --> 00:01:55,470
so apply f2 times F composed at and we
can leave out the

32
00:01:55,470 --> 00:01:59,430
the base number we leave 3n6 for later

33
00:01:59,430 --> 00:02:03,540
because I will show you in some other
things and now lets

34
00:02:03,540 --> 00:02:04,350
the

35
00:02:04,350 --> 00:02:08,179
let's see how can we represent a church
number

36
00:02:08,179 --> 00:02:11,470
as an integer how can we convert from
I'll go from a church number

37
00:02:11,470 --> 00:02:14,850
to an integer well it's not that are

38
00:02:14,850 --> 00:02:18,410
we said a church number is a function
that takes

39
00:02:18,410 --> 00:02:21,780
a successor function and a base number
so for our

40
00:02:21,780 --> 00:02:25,600
natural numbers the those will be the
successor function

41
00:02:25,600 --> 00:02:28,800
last one the and the base number

42
00:02:28,800 --> 00:02:32,140
it will be 0 so if we have to if you
knew

43
00:02:32,140 --> 00:02:36,260
again yes let here then it'll be okay
let's apply

44
00:02:36,260 --> 00:02:40,910
plus one then let's play again plus one
on a base number that will be 0

45
00:02:40,910 --> 00:02:44,200
and that will give us to thats let us
now

46
00:02:44,200 --> 00:02:47,810
go the other way around and ago from an
integer

47
00:02:47,810 --> 00:02:51,320
to a church representation

48
00:02:51,320 --> 00:02:55,100
I am to do this we do but a matching

49
00:02:55,100 --> 00:02:58,370
and then we go by induction so we have

50
00:02:58,370 --> 00:03:02,600
the base case I'll is if you want to
convert 0

51
00:03:02,600 --> 00:03:06,070
and then we can just return the
representations ear that we defined

52
00:03:06,070 --> 00:03:09,100
appears this one the

53
00:03:09,100 --> 00:03:12,450
anything have a number n then

54
00:03:12,450 --> 00:03:16,239
we use the induction step and we say
okay let's

55
00:03:16,239 --> 00:03:20,070
how do we do it let's increment with
some

56
00:03:20,070 --> 00:03:23,380
in from in function that we will define
later its increment

57
00:03:23,380 --> 00:03:27,000
the a n -1 representation of the church
number

58
00:03:27,000 --> 00:03:30,980
and then we're occur simply call into
church now

59
00:03:30,980 --> 00:03:35,390
let's define Inc includes just
incrementing so

60
00:03:35,390 --> 00:03:38,970
is just saying OK let's at one to our

61
00:03:38,970 --> 00:03:41,989
X number that we get okay now

62
00:03:41,989 --> 00:03:45,489
the what is the next step well we need
to

63
00:03:45,489 --> 00:03:49,090
define this ed because we don't have it
so how do we add

64
00:03:49,090 --> 00:03:52,480
a.m. to church numerals well

65
00:03:52,480 --> 00:03:56,370
the base idea the the basic idea is

66
00:03:56,370 --> 00:04:00,870
that of apply at why times

67
00:04:00,870 --> 00:04:04,329
and then apply the result representation
of that

68
00:04:04,329 --> 00:04:08,940
Eckstein's so then we'll have the first
flight times and then we'll play it

69
00:04:08,940 --> 00:04:09,480
again

70
00:04:09,480 --> 00:04:12,849
a X times and then we have X plus I'm

71
00:04:12,849 --> 00:04:17,150
why and here we can see

72
00:04:17,150 --> 00:04:19,970
so we apply I

73
00:04:19,970 --> 00:04:24,060
okay this we apply and why times

74
00:04:24,060 --> 00:04:27,810
at on the base number

75
00:04:27,810 --> 00:04:31,320
the result of this will be again a
church in a row

76
00:04:31,320 --> 00:04:34,600
and then which would be the
representation of our the

77
00:04:34,600 --> 00:04:38,290
base number and then we apply this on

78
00:04:38,290 --> 00:04:41,440
Eckstein's again and diesel give us the
addition

79
00:04:41,440 --> 00:04:45,150
now let's try the addition an

80
00:04:45,150 --> 00:04:48,760
you so first they want to show you in
states

81
00:04:48,760 --> 00:04:52,830
okay see if it works we have we want to

82
00:04:52,830 --> 00:04:55,830
the transform

83
00:04:55,830 --> 00:04:58,900
the 1337

84
00:04:58,900 --> 00:05:02,580
into a church representation then we
want to transform it back

85
00:05:02,580 --> 00:05:07,210
into an integer and if around this we
see that get the integer back

86
00:05:07,210 --> 00:05:10,730
and now want to try the addition the and
its

87
00:05:10,730 --> 00:05:15,160
you so we say okay let's ed their turf
representation of 2&3

88
00:05:15,160 --> 00:05:20,310
and then less transform into an integer
so we can actually see

89
00:05:20,310 --> 00:05:24,500
on the command line and we have five and
it works yes

90
00:05:24,500 --> 00:05:28,310
the now let's go on multiplication

91
00:05:28,310 --> 00:05:32,220
let's start by here okay so let's look
at three

92
00:05:32,220 --> 00:05:35,540
let's say we want to a multiply 3

93
00:05:35,540 --> 00:05:39,490
by two so we had three its stakes G

94
00:05:39,490 --> 00:05:42,750
any the composes G

95
00:05:42,750 --> 00:05:46,430
three times now what we can see is that

96
00:05:46,430 --> 00:05:50,330
we can just look down here to have six

97
00:05:50,330 --> 00:05:54,960
we need to replace these G by a
composition

98
00:05:54,960 --> 00:05:58,060
as every time have the G we want

99
00:05:58,060 --> 00:06:01,590
to have to as well so we replaces G

100
00:06:01,590 --> 00:06:05,520
with the representation of two which
would be

101
00:06:05,520 --> 00:06:11,000
F composed F as you can see up here and
then a for composite three times we will

102
00:06:11,000 --> 00:06:11,970
see that we have

103
00:06:11,970 --> 00:06:16,820
F a.m. six times and will have the
representation of

104
00:06:16,820 --> 00:06:20,040
of six now how do people do this

105
00:06:20,040 --> 00:06:23,390
well let's see here the definition we
have

106
00:06:23,390 --> 00:06:26,620
I multiply X&Y let's look at them first
one

107
00:06:26,620 --> 00:06:28,289
which is the explicit one then

108
00:06:28,289 --> 00:06:31,499
we can remove the perimeters and the
right to a composition

109
00:06:31,499 --> 00:06:35,229
so again multiplication its
representation

110
00:06:35,229 --> 00:06:38,979
a church in were also land that an
function

111
00:06:38,979 --> 00:06:42,229
that what it does it

112
00:06:42,229 --> 00:06:46,199
applies to X the result

113
00:06:46,199 --> 00:06:49,490
of applying F on why so

114
00:06:49,490 --> 00:06:52,539
its sup instead of using F on X

115
00:06:52,539 --> 00:06:56,210
it uses wise over F which is

116
00:06:56,210 --> 00:06:59,349
basically what I was saying so it gets

117
00:06:59,349 --> 00:07:03,409
the G any subsidies with the
representation of the other number

118
00:07:03,409 --> 00:07:07,439
there for creating the modification now

119
00:07:07,439 --> 00:07:10,879
this is only an a an example we can
actually from

120
00:07:10,879 --> 00:07:16,330
define other operations for example
exponentiation we can define of church

121
00:07:16,330 --> 00:07:21,309
booleans another things nice things that

122
00:07:21,309 --> 00:07:24,409
we will leave you as as an exercise

123
00:07:24,409 --> 00:07:27,959
and this was all thank you very much for
listening and happy acting