程序代写代做代考 Java ocaml compiler Polymorphic Higher-Order Programming

Polymorphic Higher-Order Programming
CSI 3120
Amy Felty University of Ottawa
slides copyright 2017, 2018 David Walker, Amy Felty permission granted to reuse these slides for non-commercial educational purposes

Some Design & Coding Rules • Laziness can be a really good force in design.
• Never write the same code twice.
– factor out the common bits into a reusable procedure.
– better, use someone else’s (well-tested, well-documented, and well-maintained) procedure.
• Why is this a good idea?
– why don’t we just cut-and-paste snippets of code using the editor instead of creating new functions?
2

Factoring Code in OCaml Consider these definitions:
let rec inc_all (xs:int list) : int list = match xs with
| [] -> []
| hd::tl -> (hd+1)::(inc_all tl)
let rec square_all (xs:int list) : int list = match xs with
| [] -> []
| hd::tl -> (hd*hd)::(square_all tl)
4

Factoring Code in OCaml
A higher-order function captures the recursion pattern:
let rec map (f:int->int) (xs:int list) : int list = match xs with
| [] -> []
| hd::tl -> (f hd)::(map f tl)
6

Factoring Code in OCaml
A higher-order function captures the recursion pattern:
let rec map (f:int->int) (xs:int list) : int list = match xs with
| [] -> []
| hd::tl -> (f hd)::(map f tl)
Uses of the function:
Writing little functions like inc just so we can call map is a pain.
let inc x = x+1
let inc_all xs = map inc xs
let square y = y*y
let square_all xs = map square xs
8

Factoring Code in OCaml
A higher-order function captures the recursion pattern:
let rec map (f:int->int) (xs:int list) : int list = match xs with
| [] -> []
| hd::tl -> (f hd)::(map f tl);;We can use an
Uses of the function:
function instead.
Originally, Church wrote this function using λ instead of fun: (λx. x+1)or (λy. y*y)
let inc_all xs = map (fun x -> x + 1) xs let square_all xs = map (fun y -> y * y) xs
anonymous
9

Here’s an annoying thing
let rec map (f:int->int) (xs:int list) : int list = match xs with
| [] -> []
| hd::tl -> (f hd)::(map f tl);;
What if I want to increment a list of floats? Alas, I can’t just call this map. It works on ints!
let rec mapfloat (f:float->float) (xs:float list) : float list =
match xs with
| [] -> []
| hd::tl -> (f hd)::(mapfloat f tl);;
11

let rec map f xs =
match xs with
| [] -> []
| hd::tl -> (f hd)::(map f tl)
Turns out
let ints = map (fun x -> x + 1) [1; 2; 3; 4]
let floats = map (fun x -> x +. 2.0) [3.1415; 2.718]
let strings = map String.uppercase [“sarah”; “joe”]
12

Type of the undecorated map?
let rec map f xs =
match xs with
| [] -> []
| hd::tl -> (f hd)::(map f tl)
map : (‘a -> ‘b) -> ‘a list -> ‘b list
13

Type of the undecorated map?
let rec map f xs =
match xs with
| [] -> []
| hd::tl -> (f hd)::(map f tl)
map : (‘a -> ‘b) -> ‘a list -> ‘b list
We often use greek letters like α or β to represent type variables.
Read as:
• foranytypes’aand’b,
• ifyougivemapafunctionfrom’ato’b,
• itwillreturnafunction
– which when given a list of ‘a values – returns a list of ‘b values.
14

We can say this explicitly
let rec map (f:’a -> ‘b) (xs:’a list) : ‘b list = match xs with
| [] -> []
| hd::tl -> (f hd)::(map f tl)
map : (‘a -> ‘b) -> ‘a list -> ‘b list
The OCaml compiler is smart enough to figure out that this is the most general type that you can assign to the code.
We say map is polymorphic in the types ‘a and ‘b – just a fancy way to say map can be used on any types ‘a and ‘b.
Java generics derived from ML-style polymorphism (but added after the fact and more complicated due to subtyping)
15

More realistic polymorphic functions
let rec merge (lt:’a->’a->bool) (xs:’a list) (ys:’a list) : ‘a list = match (xs,ys) with
| ([],_) -> ys
| (_,[]) -> xs
| (x::xst, y::yst) ->
if lt x y then x::(merge lt xst ys)
else y::(merge lt xs yst)
let rec split (xs:’a list)(ys:’a list)(zs:’a list) : ‘a list * ‘a list = match xs with
| [] -> (ys, zs)
| x::rest -> split rest zs (x::ys)
let rec mergesort (lt:’a->’a->bool) (xs:’a list) : ‘a list = match xs with
| ([] | _::[]) -> xs
| _ -> let (first,second) = split xs [] [] in
merge lt (mergesort lt first) (mergesort lt second)
16

More realistic polymorphic functions
mergesort : (‘a->’a->bool) -> ‘a list -> ‘a list mergesort (<) [3;2;7;1] == [1;2;3;7] mergesort (>) [2; 3; 42]
== [42 ; 3; 2]
mergesort (fun x y -> String.compare x y < 0) [“Hi”; “Bi”] == [“Bi”; “Hi”] let int_sort = mergesort (<) let int_sort_down = mergesort (>)
let str_sort = mergesort (fun x y -> String.compare x y < 0) 17 Summary • Map is a higher-order function that captures a very common recursion pattern • We can write clear, terse, reusable code by exploiting: – higher-order functions – anonymous functions – first-class functions – polymorphism 18 Practice Problems Using map, write a function that takes a list of pairs of integers, and produces a list of the sums of the pairs. – e.g., list_add [(1,3); (4,2); (3,0)] = [4; 6; 3] – Write list_add directly using reduce. Using map, write a function that takes a list of pairs of integers, and produces their quotient if it exists. – e.g., list_div [(1,3); (4,2); (3,0)] = [Some 0; Some 2; None] – Write list_div directly using reduce. Using reduce, write a function that takes a list of optional integers, and filters out all of the None’s. – e.g., filter_none [Some 0; Some 2; None; Some 1] = [0;2;1] – Why can’t we directly use filter? How would you generalize filter so that you can compute filter_none? Alternatively, rig up a solution using filter + map. Using reduce, write a function to compute the sum of squares of a list of numbers. – e.g., sum_squares = [3,5,2] = 38 19

Related Posts