CS计算机代考程序代写 ocaml compiler Java Polymorphic Higher-Order Programming

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