CS 421 – Spring 2007Lecture Notes Set 9:HOFs and RecordsElsa L. Gunter1Transcribed by: Pooja MathurCorresponding to Slides: 04-05-hof (slides 28 - end) 06-userdef (slides 1 - 15)Made available: February 5, 2007Revision 1.01 Change Log1.0 Initial Release.2 Upcoming exam (04-05-hof slides 36-end)Here are some things that you should have an understanding of for the upcoming exam.• Writing functions with recursion– Recursion over integers– Recursion over lists– Tail recursion vs. Forward recursion• Using higher order functions• Writing the environment at different points in the code• Writing the closure for a function (only for non-recursive functions)• Writing enumeration types and functions over those types (which we will get to today)There are problems on in the lecture slides that are likened to something you may see on an exam. Also, moreinformation on the exam can be found on the website where there is a sample exam as well as a much more detailedstudy guide.3 Other Higher Order Functions - continued3.1 Mapping (04-05-hof slides 28-31)Recall from previous lectures that we have fold left, which is an example of tail recursion or iteration. And we havefold right, which is an example of forward recursion or primative recursion. An instance of primative recursion that isoften used is map.Last time, we started to talk about the example inclist.# let rec inclist list = match list with [] → []| x :: xs → (1 + x) :: inclist xs;;1c 2007, Share and Enjoy1val inclist : int list → int list = <fun>This is a function that takes a list and adds 1 to each element of the list, transforming it into a new list. That isbasically what map does, it maps one list to another one. Each element in the new list was directly derived from thecorresponding element in the original list.Since map is basically doing the exact function we want to do in inclist, we can rewrite the function as:# let inclist = map ((+) 1);;val inclist : int list → int list = <fun>The newly rewritten function does exactly what we were doing before, but now, there is much less code. Inclistwill take a list and perform the addition operation on each element with the value 1.Earlier, it was mentioned that map is a form of primative recursion. That means that we can also write map usingfold right. To do this we need to know the usual three things, the base case, the operation being performed on the listand how it is being recursed. Well, the recursion is obvious; it is primative recursion so we know that means fold right.We know the base case is the empty list. The operation is that we are performing some function on each element andwe are cons-ing that new value to the rest of the list. With that information we can get map to look like:# let map f list =fold right (fun x y → f x :: y) list [];;val map : (’a → ’b) → ’a list → ’b list = <fun>3.2 Possible applications of HOFsOne possible use of an HOF would be to see if given a list which of the elements after being run under a test were trueor false. You could do this easily with map (or as we have just seen, fold right as well.Now, if you wanted to know if all the elements of the list passed the test, this could be done with either of the foldfunctions. Fold left would be optimal because you can recurse over the list as long as the test is returning true. Onceyou get a false, you can immediately stop, even if the very first element of a million element list. All you need is onefalse to enable you to stop recursing. With fold right, you would have to recurse to the very end no matter what andthen check the test. So with the million element list, if only the very first element was false, you wouldn’t know thatuntil you returned all the way to the head of the list. You would not use map because map returns a list and we arelooking for a single value.3.3 Zipping (slides 32-35)Another useful function is the zip function. It does exactly what it sounds, it ’zips’ two lists together. But you onlywant to do this when there are elements in both lists to do this with. So the zip function only does work when there issomething in both lists. That is, we cut off the longer list if there are two lists of different lengths.# let rec zip list1 list2 =match (list1,list2) with ([], ) → []| ( , []) → []| (x::xs, y::ys) → (x,y)::zip xs ys;;val zip : ’a list → ’b list → (’a * ’b) list = <fun>Here is an example of running the zip function. Note that if either of the two lists had more element (and onestayed the same as it is now) then we would still get the same exact return value, because the extra part of one list getscut off.# zip [1;2;3] [4;5;6];;- : (int * int) list = [(1, 4); (2, 5); (3, 6)]Now, let’s take zip a little further. Here we have the function zipwith. What zipwith does is takes the elements ofthe two lists and uses them as arguments to a function. Of course the function has to take two arguments. The resultsof applying the function on the elements of the two lists gets returned as a new list. So the type of the function issaying, we take a function that takes two arguments of type ’a and ’b and returns a value of type ’c. That function isan argument of zipwith, as well as a list of ’a and a list of ’b and that whole thing returns a list of type ’c. Looking atthis, like the zip function, our base cases throw away anything extra in either list. Our recursive case pulls off the headof the lists and performs in the input function on them and cons-es that onto the recursive call on the tail lists.2# let rec zipwith f list1 list2 =match (list1,list2) with ([], ) → []| ( , []) → []| (x::xs, y::ys) → f x y ::zipwith f xs ys;;val zipwith : (’a → ’b → ’c) → ’a list → ’b list → ’c list = <fun>The zipwith function is similar to map in that you are using a function to make a transformation between lists, onlyhere, you are taking two lists instead of one. The transformation involves creating a combination of the two lists.Note that zip with is simply a more general version of zip. That is, zip can be written with zipwith. Basically, theidea when doing this is that your function that you give as input is shifting things from curried to uncurried. The namefor which is pairing. This is what it may look like:# let zip = zipwith (fun x y → (x,y));;val zip : ’ a list → ’ b list → (’ a * ’ b) list = <fun>4 User Defined TypesSo far we have been using types that come directly from the
View Full Document
Unlocking...