CS 320 : Functional
Programming in Ocaml
(based on slides from David Walker, Princeton, Lukasz Ziarek, Buffalo and myself.)
Marco Gaboardi MSC 116 gaboardi@bu.edu
Announcements
Homework Assignment #1 is due Tuesday, February 11 (Today!), no later than 11:59 pm.
Homework Assignment #2 is posted Tuesday, February 11 (Today!), and due Friday, February 21.
Please do not wait until February 19-20 to start working on homework Assignment #2!
Learning Goals for Today
More on functional programming: more complex functions
higher-order functions code factoring currying
More on polymorphism
Functional programming
Factoring Code in OCaml Consider these definiKons:
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)
22
Factoring Code in OCaml Consider these definiKons:
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 idenKcal – factor it out!
23
Factoring Code in OCaml
A higher-order funcKon captures the recursion paRern:
let rec map (f:int->int) (xs:int list) : int list = match xs with
| [] -> []
| hd::tl -> (f hd)::(map f tl)
24
Factoring Code in OCaml
A higher-order funcKon captures the recursion paRern:
let rec map (f:int->int) (xs:int list) : int list = match xs with
| [] -> []
| hd::tl -> (f hd)::(map f tl)
Uses of the funcKon:
let inc x = x+1
let inc_all xs = map inc xs
25
Factoring Code in OCaml
A higher-order funcKon captures the recursion paRern:
let rec map (f:int->int) (xs:int list) : int list = match xs with
| [] -> []
| hd::tl -> (f hd)::(map f tl)
Uses of the funcKon:
let inc x = x+1
let inc_all xs = map inc xs
let square y = y*y
let square_all xs = map square xs
WriKng liRle funcKons like inc just so we call map is a pain.
26
Factoring Code in OCaml
A higher-order funcKon captures the recursion paRern:
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 funcKon:
anonymous
funcKon instead.
Originally, Church wrote this funcKon using λ instead of fun: (λx. x+1) or (λx. x*x)
let inc_all xs = map (fun x -> x + 1) xs let square_all xs = map (fun y -> y * y) xs
27
TopHat Q1-Q8
Another example
let rec sum (xs:int list) : int = match xs with
| [] -> 0
| hd::tl -> hd + (sum tl)
let rec prod (xs:int list) : int =
match xs with
| [] -> 1
| hd::tl -> hd * (prod tl)
‘-
Goal: Create a funcKon called reduce that when supplied with a few arguments
can implement both sum and prod. Define sum2 and prod2 using reduce.
Goal: If you finish early, use map and reduce together to find the sum of the squares of the elements of a list.
(Try it)
(Try it)
25
28
Another example
let rec sum (xs:int list) : int = match xs with
| [] -> b
| hd::tl -> hd + (sum tl)
let rec prod (xs:int list) : int =
match xs with
| [] -> b
| hd::tl -> hd * (prod tl)
‘-
26
29
Another example
let rec sum (xs:int list) : int =
match xs with
| [] -> b
| hd::tl -> hd OP (RECURSIVE CALL ON tl)
let rec prod (xs:int list) : int =
match xs with
| [] -> b
| hd::tl -> hd OP (RECURSIVE CALL ON tl)
‘-
27
30
Another example
let rec sum (xs:int list) : int =
match xs with
| [] -> b
| hd::tl -> f hd (RECURSIVE CALL ON tl)
let rec prod (xs:int list) : int =
match xs with
| [] -> b
| hd::tl -> f hd (RECURSIVE CALL ON tl)
‘-
28
31
A generic reducer
let add x y = x + y let mul x y = x * y
let rec reduce (f:int->int->int) (b:int) (xs:int list) : int = match xs with
| [] -> b
| hd::tl -> f hd (reduce f b tl)
let sum xs = reduce add 0 xs let prod xs = reduce mul 1 xs
‘-
29
32
A generic reducer
let add x y = x + y let mul x y = x * y
let rec reduce (f:int->int->int) (b:int) (xs:int list) : int = match xs with
| [] -> b
| hd::tl -> f hd (reduce f b tl)
let sum xs = reduce add 0 xs let prod xs = reduce mul 1 xs
‘-
29
32
reduce add 0 [1;2;3] ⇒
add 1 (reduce add 0 [2;3]) ⇒
add 1 (add 2 (reduce add 0 [3])) ⇒
add 1 (add 2 (add 3 (reduce add 0 []))) ⇒ add1(add2(add30)) ⇒ add1(add23) ⇒
add15 ⇒
6
Using Anonymous FuncKons
let rec reduce (f:int->int->int) (b:int) (xs:int list) : int = match xs with
| [] -> b
| hd::tl -> f hd (reduce f b tl)
let sum xs = reduce (fun x y -> x+y) 0 xs let prod xs = reduce (fun x y -> x*y) 1 xs
‘-
30
33
Using Anonymous FuncKons
let rec reduce (f:int->int->int) (b:int) (xs:int list) : int = match xs with
| [] -> b
| hd::tl -> f hd (reduce f b tl)
let sum xs = reduce (fun x y -> x+y) 0 xs let prod xs = reduce (fun x y -> x*y) 1 xs
let sum_of_squares xs = sum (map (fun x -> x * x) xs) let pairify xs = map (fun x -> (x,x)) xs
‘-
31
34
Using Anonymous FuncKons
let rec reduce (f:int->int->int) (b:int) (xs:int list) : int = match xs with
| [] -> b
| hd::tl -> f hd (reduce f b tl)
let sum xs = reduce (+) 0 xs let prod xs = reduce ( * ) 1 xs
let sum_of_squares xs = sum (map (fun x -> x * x) xs) let pairify xs = map (fun x -> (x,x)) xs
‘-
32
35
Using Anonymous FuncKons
let rec reduce (f:int->int->int) (b:int) (xs:int list) : int = match xs with
| [] -> b
| hd::tl -> f hd (reduce f b tl)
let sum xs = reduce (+) 0 xs let prod xs = reduce (*) 1 xs
‘-
let sum_of_squares xs = sum (map (fun x -> x * x) xs) let pairify xs = map (fun x -> (x,x)) xs
wrong
33
36
Using Anonymous FuncKons
let rec reduce (f:int->int->int) (b:int) (xs:int list) : int = match xs with
| [] -> b
| hd::tl -> f hd (reduce f b tl)
let sum xs = reduce (+) 0 xs let prod xs = reduce (*) 1 xs
‘-
let sum_of_squares xs = sum (map (fun x -> x * x) xs) let pairify xs = map (fun x -> (x,x)) xs
wrong — creates a comment! ug. OCaml -0.1
34
37
More on Anonymous FuncKons FuncKon declaraKons:
are syntacAc sugar for:
let square = (fun x -> x*x)
let add = (fun x y -> x+y)
In other words, funcAons are values we can bind to a variable, just like 3 or “moo” or true.
FuncKons are 2nd class no more!
let square x = x*x
let add x y = x+y
‘-
35
38
One argument, one result Simplifying further:
let add = (fun x y -> x+y)
is shorthand for:
‘-
let add = (fun x -> (fun y -> x+y))
That is, add is a funcKon which:
– when given a value x, returns a funcAon (fun y -> x+y) which: • when given a value y, returns x+y.
36
39
Curried FuncKons
Currying: verb. gerund or present parAciple (1) to prepare or flavor with hot-tasKng spices
(2) to encode a mulK-argument funcKon using nested, higher-order funcKons.
(1)
fun x -> (fun y -> x+y)(* curried *) fun x y -> x + y (* curried *) fun (x,y) -> x+y (* uncurried *)
(2)
40
What is the type of add?
let add = (fun x -> (fun y -> x+y))
Add’s type is:
which we can write as:
int -> (int -> int)
int -> int -> int
That is, the arrow type is right-associaKve.
42
What’s so good about Currying?
In addiKon to simplifying the language, currying funcKons so that they only take one argument leads to two major wins:
1. We can parAally apply a funcKon.
2. We can more easily compose funcKons.
43
ParKal ApplicaKon
let add = (fun x -> (fun y -> x+y))
Curried funcKons allow defs of new, parAally applied funcKons: Equivalent to wriKng:
which is equivalent to wriKng: also:
let inc = add 1
let inc = (fun y -> 1+y)
let inc y = 1+y
let inc2 = add 2
let inc3 = add 3
44
TopHat Q9-Q12
Polymorphism
‘-
42
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!
43
63
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);;
44
64
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 [“sarah”; “joe”]
‘-
45
65
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
‘-
46
66
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:
• for any types ‘a and ‘b,
• if you give map a funcKon from ‘a to ‘b,
• it will return a funcKon
– which when given a list of ‘a values – returns a list of ‘b values.
We owen use greek leRers like α or β to represent type variables.
47
67
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
awer the fact and more complicated due to subtyping)
48
68
More realisKc polymorphic funcKons
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)
‘-
49
69
More realisKc polymorphic funcKons
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)
50
70
Another InteresKng FuncKon
let comp f g x = f (g x)
let mystery = comp (add 1) square
let comp = fun f -> (fun g -> (fun x -> f (g x)))
let mystery = comp (add 1) square
‘-
let mystery =
(fun f -> (fun g -> (fun x -> f (g x)))) (add 1) square
let mystery = fun x -> (add 1) (square x)
let mystery x = add 1 (square x)
51
71