1 00:00:14,280 --> 00:00:15,510 000 wat 2 00:00:15,510 --> 00:00:18,939 cameras already a running sorry sorry guys 3 00:00:18,939 --> 00:00:25,939 an so 4 00:00:26,289 --> 00:00:29,659 functional programming with bananas 5 00:00:29,659 --> 00:00:32,829 lenses the barbed wire 6 00:00:32,829 --> 00:00:36,200 left at home and and blogs 7 00:00:36,200 --> 00:00:40,320 is not something for hipsters an 8 00:00:40,320 --> 00:00:43,480 a sexually style from show programming 9 00:00:43,480 --> 00:00:47,020 where ry leverage higher-order functions 10 00:00:47,020 --> 00:00:50,780 and that will be the topic of today's lecture 11 00:00:50,780 --> 00:00:55,790 we've seen several higher 12 00:00:55,790 --> 00:00:59,250 French is already but we never actually 13 00:00:59,250 --> 00:01:03,739 named them specifically so hired a function 14 00:01:03,739 --> 00:01:08,740 as a function that takes an argument a function as an argument 15 00:01:08,740 --> 00:01:12,409 or reader readers and function as a result 16 00:01:12,409 --> 00:01:16,829 as you get this function twice twice 17 00:01:16,829 --> 00:01:20,670 is defined as follows: Trisha avonex goals 18 00:01:20,670 --> 00:01:25,600 ass of at affects if we look at the type of two ice 19 00:01:25,600 --> 00:01:30,450 and again remember this index tries double go along in stride has type 20 00:01:30,450 --> 00:01:35,509 then on the right to be /c that it takes as the first parameter a function 21 00:01:35,509 --> 00:01:39,319 from a2a and it returns a function 22 00:01:39,319 --> 00:01:44,270 from a2a and if we look at the definition again with that type in mind 23 00:01:44,270 --> 00:01:47,319 we see that the tights make sense twice 24 00:01:47,319 --> 00:01:50,779 takes a function that function goes from a2a 25 00:01:50,779 --> 00:01:53,850 then addiction argument of type A 26 00:01:53,850 --> 00:01:58,549 attacks and then it returns a value of type they were on how does it do that it 27 00:01:58,549 --> 00:01:59,909 applies everyone's 28 00:01:59,909 --> 00:02:04,109 which detection a transform said and another a 29 00:02:04,109 --> 00:02:08,360 showed the arguments to the second application %uh vast will also be of 30 00:02:08,360 --> 00:02:09,099 type A 31 00:02:09,099 --> 00:02:12,200 and you apply at the second time to return 32 00:02:12,200 --> 00:02:15,190 value uptime of Taipei 33 00:02:15,190 --> 00:02:17,920 so twice is a higher-order function 34 00:02:17,920 --> 00:02:21,560 because it takes a function as its first argument 35 00:02:21,560 --> 00:02:25,290 also notice how the brain disease are 36 00:02:25,290 --> 00:02:28,560 used the brand to seize on the first argument 37 00:02:28,560 --> 00:02:32,569 are explicit because it's a function from a2a and 38 00:02:32,569 --> 00:02:37,750 records for function dives associate in the ride so we have to boot 39 00:02:37,750 --> 00:02:41,260 the brand she's there but we don't have to put them 40 00:02:41,260 --> 00:02:45,010 on the right hand side but if we would put all the branches is there 41 00:02:45,010 --> 00:02:48,530 the dive would look a arrow a arrow 42 00:02:48,530 --> 00:02:53,459 a arrow a why are 43 00:02:53,459 --> 00:02:57,790 higher-order functions useful well there's this 44 00:02:57,790 --> 00:03:01,519 think that programmers love to do and that's not to repeat yourself 45 00:03:01,519 --> 00:03:05,060 don't repeat yourself and with higher order functions 46 00:03:05,060 --> 00:03:09,859 we allow this thing to be encoded in the language because whenever we see 47 00:03:09,859 --> 00:03:10,920 repetition 48 00:03:10,920 --> 00:03:14,489 we abstracted pattern into higher-order function 49 00:03:14,489 --> 00:03:18,140 and then weekend applied that higher-order function 50 00:03:18,140 --> 00:03:23,579 with various arguments I'm to specify what is difference between 51 00:03:23,579 --> 00:03:26,599 you know all the common uses of this common pattern 52 00:03:26,599 --> 00:03:31,700 a show common programming idioms can be encoded as functions 53 00:03:31,700 --> 00:03:34,989 written in the language itself and laziness here plays 54 00:03:34,989 --> 00:03:39,290 a important role because if you don't have a lazy evaluation 55 00:03:39,290 --> 00:03:43,000 arguments might be evaluated prematurely 56 00:03:43,000 --> 00:03:46,560 and then the effect is not the same as the 57 00:03:46,560 --> 00:03:50,389 an pattern where you instantiate the arguments 58 00:03:50,389 --> 00:03:53,940 am for the parameters another 59 00:03:53,940 --> 00:03:57,180 way to look at this is that we can define 60 00:03:57,180 --> 00:04:02,280 domain-specific languages as collection of higher-order functions so in Haskell 61 00:04:02,280 --> 00:04:06,440 people often talk about domain specific languages read a mean 62 00:04:06,440 --> 00:04:09,930 API's and other way to say that 63 00:04:09,930 --> 00:04:13,190 is these are embed domain-specific languages 64 00:04:13,190 --> 00:04:16,209 and then the third a.m. 65 00:04:16,209 --> 00:04:20,269 advantage of higher order functions is dead 66 00:04:20,269 --> 00:04:23,520 these higher-order functions have algebraic properties 67 00:04:23,520 --> 00:04:27,000 that we get used to reason about programs and these higher-order 68 00:04:27,000 --> 00:04:27,900 properties 69 00:04:27,900 --> 00:04:31,639 these properties of higher-order functions are these algebraic properties 70 00:04:31,639 --> 00:04:35,370 they hold irrespective of how are you 71 00:04:35,370 --> 00:04:39,030 which parameters you bastard them so you can 72 00:04:39,030 --> 00:04:43,020 if I'm properties of these programs gonna in a general way 73 00:04:43,020 --> 00:04:46,470 and then used them and all along and we will see 74 00:04:46,470 --> 00:04:51,770 several of these examples as we go twice 75 00:04:51,770 --> 00:04:56,009 may look like you know weird little weird to say maybe a little bit 76 00:04:56,009 --> 00:04:56,880 syntactic 77 00:04:56,880 --> 00:05:01,100 but I'm here's another higher-order functions that we use all the time 78 00:05:01,100 --> 00:05:04,460 and this is the map function so map 79 00:05:04,460 --> 00:05:07,479 takes a function an 80 00:05:07,479 --> 00:05:11,380 then take Celeste and then applies that function to 81 00:05:11,380 --> 00:05:16,800 every element of the list if you look at the type of map al-arabi 82 00:05:16,800 --> 00:05:19,800 arrow less than a hour or less to be 83 00:05:19,800 --> 00:05:24,340 you have very little choice then to apply that function 84 00:05:24,340 --> 00:05:28,820 to every element of the list because it gonna do you know the type 85 00:05:28,820 --> 00:05:31,949 really strongly suggests that the implementation 86 00:05:31,949 --> 00:05:35,590 you have a function of type A to B you have a function 87 00:05:35,590 --> 00:05:39,789 a lists mean values of Taipei and what you require 88 00:05:39,789 --> 00:05:43,180 is a list mid-valley just I B well what can you do 89 00:05:43,180 --> 00:05:46,659 well you just transform every element in the input list 90 00:05:46,659 --> 00:05:50,130 using that function to get to the required output list 91 00:05:50,130 --> 00:05:53,630 and that's exactly how map is defined 92 00:05:53,630 --> 00:05:57,139 now that you're gonna application of map 93 00:05:57,139 --> 00:06:00,990 so we map the sections and blush 94 00:06:00,990 --> 00:06:04,870 function plus Wong remember the lecture 95 00:06:04,870 --> 00:06:08,260 we had about sections so this is a function that 96 00:06:08,260 --> 00:06:12,220 implicitly defined to be llame the axe express ROM 97 00:06:12,220 --> 00:06:15,960 and we met that function over the last bomb 357 98 00:06:15,960 --> 00:06:20,500 so this function will just adwan to every element of the list 99 00:06:20,500 --> 00:06:24,870 and that's what you see there we get the result this 2468 100 00:06:24,870 --> 00:06:27,960 am 101 00:06:27,960 --> 00:06:31,690 weekend define the map function using list comprehension 102 00:06:31,690 --> 00:06:35,699 very easy in some sense you can say list comprehension 103 00:06:35,699 --> 00:06:38,810 are designed to define 104 00:06:38,810 --> 00:06:42,370 map so map applies to the function ass 105 00:06:42,370 --> 00:06:46,570 to every element in the list know there's the list comprehension I mean 106 00:06:46,570 --> 00:06:48,040 it's like exactly the 107 00:06:48,040 --> 00:06:51,720 what I said and atthe 108 00:06:51,720 --> 00:06:54,970 steak every element Akshardham the list axis 109 00:06:54,970 --> 00:06:58,310 apply f/2.8 and returned less 110 00:06:58,310 --> 00:07:01,340 at short nap this am 111 00:07:01,340 --> 00:07:05,260 but we can also define map recursively 112 00:07:05,260 --> 00:07:10,600 and and some sense I prefer myself the recursive definition 113 00:07:10,600 --> 00:07:14,820 and why do I prefer to recursive definition well we will see later 114 00:07:14,820 --> 00:07:18,010 that when be defined map recursively 115 00:07:18,010 --> 00:07:21,350 and we define other higher or the French is recursively 116 00:07:21,350 --> 00:07:24,550 we see a pattern that we can abstract 117 00:07:24,550 --> 00:07:29,740 again so we can abstract nap into a super high order to function 118 00:07:29,740 --> 00:07:34,120 and that will be twofold function but for now let's look at the recursive 119 00:07:34,120 --> 00:07:35,800 definition of just map 120 00:07:35,800 --> 00:07:39,260 a map of the empty nest is the anti less 121 00:07:39,260 --> 00:07:42,669 and map of the list axe 122 00:07:42,669 --> 00:07:46,169 bombs access well what we do is we 123 00:07:46,169 --> 00:07:50,320 first three gir simply map af over access 124 00:07:50,320 --> 00:07:54,550 so we map at over the rest of the last and then re 125 00:07:54,550 --> 00:07:58,460 concatenate Aframax two different a ride 126 00:07:58,460 --> 00:08:02,930 so this is a recursive definition this inductive over the structure of the list 127 00:08:02,930 --> 00:08:03,510 so we have 128 00:08:03,510 --> 00:08:06,789 either the empty list re: at the case where the list 129 00:08:06,789 --> 00:08:10,130 is build using axe gone axis 130 00:08:10,130 --> 00:08:13,600 be recursively map app over the rest of the list 131 00:08:13,600 --> 00:08:18,580 and and cons have a fax on top here's another 132 00:08:18,580 --> 00:08:22,680 higher are to function filter so filter takes 133 00:08:22,680 --> 00:08:25,690 a predicate fun shiver a tubal 134 00:08:25,690 --> 00:08:29,460 that dick celeste every day there's another less the new list 135 00:08:29,460 --> 00:08:32,789 where all the elements for rich that predicate 136 00:08:32,789 --> 00:08:35,849 does not hold are removed at 137 00:08:35,849 --> 00:08:39,080 that's why it's called filter show all these elements are filter the way 138 00:08:39,080 --> 00:08:43,020 for instance everyone to filter 139 00:08:43,020 --> 00:08:47,180 all the even numbers from the list values from Monte dam 140 00:08:47,180 --> 00:08:51,420 we get all the even values 246 141 00:08:51,420 --> 00:08:54,420 8 and then again 142 00:08:54,420 --> 00:08:57,990 filter can be defined in two ways first long 143 00:08:57,990 --> 00:09:01,019 is red list comprehension ce and 144 00:09:01,019 --> 00:09:04,550 fairly simple so what we do is we say take every 145 00:09:04,550 --> 00:09:08,139 element axe I have access and if 146 00:09:08,139 --> 00:09:12,290 be a fax is true then you put action the result list 147 00:09:12,290 --> 00:09:18,300 and that's it so the definition of filter using less comprehension 148 00:09:18,300 --> 00:09:21,760 looks very simple but again I prefer 149 00:09:21,760 --> 00:09:25,690 the recursive definition and the recursive definition has 150 00:09:25,690 --> 00:09:29,980 very very similar structure to the map function 151 00:09:29,980 --> 00:09:34,529 its defiant inductively on the structure of the list so 152 00:09:34,529 --> 00:09:38,410 we have two cases either we have the anti lest 153 00:09:38,410 --> 00:09:41,480 are we have lest ex-cons axis 154 00:09:41,480 --> 00:09:47,149 and we filter a all the values for rich is spreading and does not hold from the 155 00:09:47,149 --> 00:09:48,199 MPLS trial 156 00:09:48,199 --> 00:09:52,300 the only thing we can do is return the empty list 157 00:09:52,300 --> 00:09:56,279 every filter out all the values 158 00:09:56,279 --> 00:09:59,339 for HP does not hold from the list ex-cons 159 00:09:59,339 --> 00:10:02,949 Texas well they're still cases first 160 00:10:02,949 --> 00:10:07,010 be a fix can be true so that's this case and then 161 00:10:07,010 --> 00:10:10,370 this is the second casement be a fix is false well 162 00:10:10,370 --> 00:10:13,640 it be a fix is true we filter 163 00:10:13,640 --> 00:10:16,740 recursively the rest of the list and then we 164 00:10:16,740 --> 00:10:21,199 concatenate X on top an otherwise we just forget about tax 165 00:10:21,199 --> 00:10:24,490 and filtered the rest of the list so here you see it 166 00:10:24,490 --> 00:10:28,510 its gonna are SM ball as the 167 00:10:28,510 --> 00:10:32,130 list comprehension definition but the important thing 168 00:10:32,130 --> 00:10:37,480 is dead this definition here follows exactly the same structure of Mac 169 00:10:37,480 --> 00:10:40,850 and in the context of you know saying 170 00:10:40,850 --> 00:10:44,980 don't repeat ourselves we should be able to abstract 171 00:10:44,980 --> 00:10:49,889 that commonality between filter and map 172 00:10:49,889 --> 00:10:53,819 is either both the recursively defined over 173 00:10:53,819 --> 00:10:56,920 analysts we should be able to factor in and out 174 00:10:56,920 --> 00:11:00,410 into another higher function and that higher 175 00:11:00,410 --> 00:11:03,930 function is full bar and that will be the topic 176 00:11:03,930 --> 00:11:05,220 of the neck 177 00:11:05,220 --> 00:11:07,420 section thank you and see issue