Polymorphic Higher-Order Programming
CSI 3120
Amy Felty University of Ottawa
slides copyright 2017, 2018, 2019, 2020 Author David Walker, updated by 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
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?
– find and fix a bug in one copy, have to fix in all of them.
– decide to change the functionality, have to track down all of the places where it gets used.
3
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 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)
The code is almost identical – factor it out!
5
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:
let inc x = x+1
let inc_all xs = map inc xs
7
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:
let inc x = x+1
let inc_all xs = map inc xs
let square y = y*y
let square_all xs = map square xs
Writing little functions like inc just so we can call map is a pain.
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:
anonymous
function instead.
Originally, Church wrote this function using l instead of fun: (lx. x+1) or (ly. y*y)
let inc_all xs = map (fun x -> x + 1) xs let square_all xs = map (fun y -> y * y) xs
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!
10
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
Turns out
let rec map f xs =
match xs with
| [] -> []
| hd::tl -> (f hd)::(map f tl)
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_ascii [“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
Read as:
• foranytypes’aand’b,
• ifyougivemapafunctionfrom’ato’b, • itwillreturnafunction
– which when given a list of ‘a values – returns a list of ‘b values.
We often use greek letters like a or b to represent type variables.
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
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