CIS 500Software FoundationsFall 2006September 13AdministriviaBCP gone next weekII will b e out of town for all of next week.IMy office hours will be cancelled for the week.ILectures and recitations will continue as usual. Brian will givethe lectures.PolymorphismPolymorphismWe encountered the concept of polymorphism very briefly lasttime. Let’s look at it now in a bit more detail.# let rec last l =match l with[] -> raise Bad| [x] -> x| _::y -> last yWhat type should we give to the parameter l?Polymorphism# let rec last l =match l with[] -> raise Bad| [x] -> x| _::y -> last yIt do esn’t m atter what type of objects are stored in the list: wecould make it int list or bool list, and OCaml would notcomplain. However, if we chose one of these types, would not beable to apply last to the other.Instead, we can give l the type ’a list (pronounced “alpha”),standing for an arbitrary type. When we use the function, OCamlwill figure out what type we need.PolymorphismThis version of last is said to be polymorphic, because it can beapplied to many different types of arguments. (“Poly” = many,“morph” = shape.)Note that the type of the elements of l is ’a (pronounced“alpha”). This is a type variable, which can instantiated, eachtime we apply last, by replacing ’a with any type that we like.The instances of the type ’a list -> ’a includeint list -> intstring list -> stringint list list -> int listetc.In other words,last : ’a list -> ’acan be read, “last is a function that takes a list of elements ofany type alpha and returns an element of alpha.”A polymorphic append# let rec append (l1: ’a list) (l2: ’a list) =if l1 = [] then l2else List.hd l1 :: append (List.tl l1) l2;;val append : ’a list -> ’a list -> ’a list = <fun># append [4; 3; 2] [6; 6; 7];;- : int list = [4; 3; 2; 6; 6; 7]# append ["cat"; "in"] ["the"; "hat"];;- : string list = ["cat"; "in"; "the"; "hat"]A polymorphic rev# let rec revaux (l: ’a list) (res: ’a list) =if l = [] then reselse revaux (List.tl l) (List.hd l :: res);;val revaux : ’a list -> ’a list -> ’a list = <fun># let rev (l: ’a list) = revaux l [];;val rev : ’a list -> ’a list = <fun># rev ["cat"; "in"; "the"; "hat"];;- : string list = ["hat"; "the"; "in"; "cat"]# rev [false; true];;- : bool list = [true; false]Polymorphic repeat# (* A list of n copies of k *)let rec repeat (k:’a) (n:int) =if n = 0 then []else k :: repeat k (n-1);;# repeat 7 12;;- : int list = [7; 7; 7; 7; 7; 7; 7; 7; 7; 7; 7; 7]# repeat true 3;;- : bool list = [true; true; true]# repeat [6;7] 4;;- : int list list = [[6; 7]; [6; 7]; [6; 7]; [6; 7]]What is the type of repeat?PalindromesA palindrome is a word, sentence, or other sequence that readsthe same forwards and backwards.# let palindrome (l: ’a list) =l = (rev l);;val palindrome : ’a list -> bool = <fun># palindrome ["a";"b";"l";"e"; "w";"a";"s";"I"; "e";"r";"e"; "I";"s";"a";"w"; "e";"l";"b";"a"];;- : bool = true# palindrome [true; true; false];;- : bool = falseDigression: Approaches to TypingIA strongly typed language prevents programs from accessingprivate data, corrupting memory, crashing the machine, etc.IA weakly typed language does not.IA statically typed language p erforms type-consistency checksat when programs are first entered.IA dynamically typed language delays these checks untilprograms are executed.Weak StrongDynamic Lisp, SchemeStatic C, C++ ML, Java?, C]??Strictly sp eaking, Java and C] should be called “mostly static”Practice with TypesWhat are the types of the following functions?Ilet f (x:int) = x + 1Ilet f x = x + 1Ilet f (x:int) = [x]Ilet f x = [x]Ilet f x = xIlet f x = hd(tl x) :: [1.0]Ilet f x = hd(tl x) :: []Ilet f x = 1 :: xIlet f x y = x :: yIlet f x y = x :: []Ilet f x = x @ xIlet f x = x :: xIlet f x y z = if x>3 then y else zIlet f x y z = if x>3 then y else [z]And one more:let rec f x =if (tl x) = [] then xelse f (tl x)Programming With FunctionsFunctions as DataFunctions in OCaml are first class — they have the same rightsand privileges as values of any other types. E.g., they can beIpassed as arguments to other functionsIreturned as results from other functionsIstored in data structures such as tuples and listsIetc.map: “apply-to-each”OCaml has a predefined function List.map that takes a function fand a list l and produces another list by applying f to eachelement of l. We’ll soon see how to define List.map, but firstlet’s look at some e xamples.# List.map square [1; 3; 5; 9; 2; 21];;- : int list = [1; 9; 25; 81; 4; 441]# List.map not [false; false; true];;- : bool list = [true; true; false]Note that List.map is polymorphic: it works for lists of integers,strings, b ooleans, etc.More on mapAn interesting feature of List.map is its first argument is itself afunction. For this reason, we call List.map a higher-orderfunction.Natural uses for higher-order functions arise frequently inprogramming. One of OCaml’s strengths is that it makeshigher-order functions very easy to work with.In other languages such as Java, higher-order functions can be(and often are) simulated using objects.filterAnother useful higher-order function is List.filter. Whenapplied to a list l and a b oolean function p, it builds a list of theelements from l for which p returns true.# let rec even (n:int) =if n=0 then true else if n=1 then falseelse if n<0 then even (-n)else even (n-2);;val even : int -> bool = <fun># List.filter even [1; 2; 3; 4; 5; 6; 7; 8; 9];;- : int list = [2; 4; 6; 8]# List.filter palindrome[[1]; [1; 2; 3]; [1; 2; 1]; []];;- : int list list = [[1]; [1; 2; 1]; []]Note that, like map, List.filter is polymorphic—it works onlists of any type.Defining mapList.map comes predefined in the OCaml system, but there isnothing magic about it—we can easily define our own map functionwith the same behavior.let rec map (f: ’a->’b) (l: ’a list) =if l = [] then []else f (List.hd l) :: map f (List.tl l)val map : (’a -> ’b) -> ’a list -> ’b list = <fun>The type of map is probably even more polymorphic than youexp ec ted! The list that it returns can actually be of a differenttype from its argument:# map String.length ["The"; "quick"; "brown"; "fox"];;- : int list = [3; 5; 5; 3]Defining filterSimilarly, we can define our own filter that behaves the same asList.filter.# let rec filter (p: ’a->bool) (l: ’a list) =if l = [] then[]else if p (List.hd l) thenList.hd l :: filter p (List.tl l)elsefilter p (List.tl l)val filter : (’a -> bool) -> ’a