Polymorphic Higher-Order Programming
Polymorphic Higher-Order
Programming
slides copyright 2017, 2018, 2019, 2020, 2021
Author David Walker, updated by Amy Felty
permission granted to reuse these slides for non-commercial educational purposes
Some Design & Coding Rules
3
• 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?
Some Design & Coding Rules
4
• 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.
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)
5
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!
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)
7
Factoring Code in OCaml
A higher-order function captures the recursion pattern:
Uses of the function:
let rec map (f:int->int) (xs:int list) : int list =
match xs with
| [] -> []
| hd::tl -> (f hd)::(map f tl)
let inc x = x+1
let inc_all xs = map inc xs
8
Factoring Code in OCaml
A higher-order function captures the recursion pattern:
Uses of the function:
let rec map (f:int->int) (xs:int list) : int list =
match xs with
| [] -> []
| hd::tl -> (f hd)::(map f tl)
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
9
map is a pain.
Factoring Code in OCaml
Uses of the function:
let inc_all xs = map (fun x -> x + 1) xs
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
anonymous
function
instead. Originally,
Church wrote
this function
using Α instead
10
of fun:
(Αx. x+1) or
(Αy. y*y)
let square_all xs = map (fun y -> y * y) xs
Here’s an annoying thing
What if I want to increment a list of floats?
Alas, I can’t just call this map. It works on ints!
let rec map (f:int->int) (xs:int list) : int list =
match xs with
| [] -> []
| hd::tl -> (f hd)::(map f tl);;
11
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);;
12
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”]
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
14
Type of the undecorated map?
14
Read as:
• for any types ‘a and ‘b,
• if you give map a function from ‘a to ‘b,
• it will return a function
– which when given a list of ‘a values
– returns a list of ‘b values.
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.
We can say this explicitly
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)
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
15
Summary
18
• 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
Polymorphic Higher-Order Programming
Some Design & Coding Rules
Some Design & Coding Rules
Factoring Code in OCaml
Factoring Code in OCaml
Factoring Code in OCaml
Factoring Code in OCaml
Factoring Code in OCaml
Factoring Code in OCaml
Here’s an annoying thing
Here’s an annoying thing
Turns out
Type of the undecorated map?
Type of the undecorated map?
We can say this explicitly
Summary