程序代写代做代考 ocaml C data structure CS 320 : Functional

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
 Solution for homework Assignment #1 will be posted on Piazza.
 Homework Assignment #2 is already posted and will be due on Friday,
February 21, by 11:59 pm.
 Please do not wait until February 19-20 to start working on homework Assignment #2!

TopHat Q0.1 – Q0.3

Learning Goals for Today
 More on functional programming: more complex functions
higher-order functions code factoring anonymous functions currying
 More on polymorphism
 Data types, inductive data types

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)
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)
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)
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)
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
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
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
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
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
35

TopHat Q1-Q6

Data Types

26
OCaml So Far
• We have seen a number of basic types: – int
– float – char – string – bool
• We have seen a few structured types: – pairs
– tuples – opFons – lists
• In this lecture, we will see some more general ways to define our own new types and data structures

27
Type AbbreviaFons
• We have already seen some type abbreviaFons:
type point = float * float

Type AbbreviaFons
• We have already seen some type abbreviaFons:
type point = float * float
• These abbreviaFons can be helpful documentaFon:
28
let distance (p1:point) (p2:point) : float =
let square x = x *. x in
let (x1,y1) = p1 in
let (x2,y2) = p2 in
sqrt (square (x2 -. x1) +. square (y2 -. y1))
• But they add nothing of substance to the language – they are equal in every way to an exisFng type

Type AbbreviaFons
• We have already seen some type abbreviaFons:
type point = float * float
• As far as OCaml is concerned, you could have wri`en:
• Since the types are equal, you can subs3tute the definiFon for the name wherever you want
29
let distance (p1:float*float)
(p2:float*float) : float =
let square x = x *. x in
let (x1,y1) = p1 in
let (x2,y2) = p2 in
sqrt (square (x2 -. x1) +. square (y2 -. y1))
– we have not added any new data structures

31
Data types
• OCaml provides a general mechanism called a data type for defining new data structures that consist of many alternaFves
type my_bool = Tru | Fal
a value with type my_bool is one of two things:
• Tru, or
• Fal
read the “|” as “or”

Data types
• OCaml provides a general mechanism called a data type for defining new data structures that consist of many alternaFves
type my_bool = Tru | Fal
32
a value with type my_bool is one of two things:
• Tru, or
• Fal
Tru and Fal are called “constructors”
read the “|” as “or”

33
Data types
• OCaml provides a general mechanism called a data type for defining new data structures that consist of many alternaFves
type my_bool = Tru | Fal
type color = Blue | Yellow | Green | Red
there’s no need to stop
at 2 cases; define as many alternaFves as you want

Data types
• OCaml provides a general mechanism called a data type for defining new data structures that consist of many alternaFves
type my_bool = Tru | Fal
• CreaFng values:
34
type color = Blue | Yellow | Green | Red
let b1 : my_bool = Tru
let b2 : my_bool = Fal
let c1 : color = Yellow
let c2 : color = Red
use constructors to create values

35
Data types
type color = Blue | Yellow | Green | Red
let c1 : color = Yellow
let c2 : color = Red
• Using data type values:
let print_color (c:color) : unit =
match c with
| Blue ->
| Yellow ->
| Green ->
| Red ->
use pa`ern matching to determine which color you have; act accordingly

• Using data type values:
Data types
36
type color = Blue | Yellow | Green | Red
let c1 : color = Yellow
let c2 : color = Red
let print_color (c:color) : unit =
match c with
| Blue -> print_string “blue”
| Yellow -> print_string “yellow”
| Green -> print_string “green”
| Red -> print_string “red”

Data types
• Using data type values:
Why not just use strings to represent colors instead of defining a new type?
37
type color = Blue | Yellow | Green | Red
let c1 : color = Yellow
let c2 : color = Red
let print_color (c:color) : unit =
match c with
| Blue -> print_string “blue”
| Yellow -> print_string “yellow”
| Green -> print_string “green”
| Red -> print_string “red”

38
Data types
type color = Blue | Yellow | Green | Red oops!:
let print_color (c:color) : unit =
match c with
| Blue -> print_string “blue”
| Yellow -> print_string “yellow”
| Red -> print_string “red”
Warning 8: this pa`ern-matching is not exhausFve. Here is an example of a value that is not matched: Green

39
Data types
type color = Blue | Yellow | Green | Red oops!:
let print_color (c:color) : unit =
match c with
| Blue -> print_string “blue”
| Yellow -> print_string “yellow”
| Red -> print_string “red”
Warning 8: this pa`ern-matching is not exhausFve. Here is an example of a value that is not matched: Green
OCaml’s datatype mechanism allow you to create types that contain precisely the values you want!

TopHat Q7-Q9

Inductive Data Types

55
InducFve data types
• We can use data types to define inducFve data
• A binary tree is:
– a Leaf containing no data
– a Node containing a key, a value, a leP subtree and a right subtree

56
InducFve data types
• We can use data types to define inducFve data
• A binary tree is:
– a Leaf containing no data
– a Node containing a key, a value, a leP subtree and a right subtree
type key = string
type value = int
type tree =
Leaf
| Node of key * value * tree * tree

InducFve data types
57
type key = int
type value = string
type tree =
Leaf
| Node of key * value * tree * tree
let rec insert (t:tree) (k:key) (v:value) : tree =

InducFve data types
58
type key = int
type value = string
type tree =
Leaf
| Node of key * value * tree * tree
let rec insert (t:tree) (k:key) (v:value) : tree =
match t with
| Leaf ->
| Node (k’, v’, left, right) ->
Again, the type definiFon specifies the cases you must consider

InducFve data types
59
type key = int
type value = string
type tree =
Leaf
| Node of key * value * tree * tree
let rec insert (t:tree) (k:key) (v:value) : tree =
match t with
| Leaf -> Node (k, v, Leaf, Leaf)
| Node (k’, v’, left, right) ->

InducFve data types
60
type key = int
type value = string
type tree =
Leaf
| Node of key * value * tree * tree
let rec insert (t:tree) (k:key) (v:value) : tree =
match t with
| Leaf -> Node (k, v, Leaf, Leaf)
| Node (k’, v’, left, right) ->
if k < k' then Node (k', v', insert left k v, right) else if k > k’ then
Node (k’, v’, left, insert right k v)
else
Node (k, v, left, right)

InducFve data types
61
type key = int
type value = string
type tree =
Leaf
| Node of key * value * tree * tree
let rec insert (t:tree) (k:key) (v:value) : tree =
match t with
| Leaf -> Node (k, v, Leaf, Leaf)
| Node (k’, v’, left, right) ->
if k < k' then Node (k', v', insert left k v, right) else if k > k’ then
Node (k’, v’, left, insert right k v)
else
Node (k, v, left, right)

InducFve data types
62
type key = int
type value = string
type tree =
Leaf
| Node of key * value * tree * tree
let rec insert (t:tree) (k:key) (v:value) : tree =
match t with
| Leaf -> Node (k, v, Leaf, Leaf)
| Node (k’, v’, left, right) ->
if k < k' then Node (k', v', insert left k v, right) else if k > k’ then
Node (k’, v’, left, insert right k v)
else
Node (k, v, left, right)

63
InducFve data types: Another Example
• Recall, we used the type “int” to represent natural numbers
– but that was kind of broken: it also contained negaFve numbers
– we had to use a dynamic test to guard entry to a funcFon:
– it would be nice if there was a way to define the natural numbers exactly, and use OCaml’s type system to guarantee no client ever a`empts to double a negaFve number
let double (n : int) : int =
if n < 0 then raise (Failure "negative input!") else double_nat n 64 InducFve data types • Recall, a natural number n is either: – zero, or – m + 1 • We use a data type to represent this definiFon exactly: 65 InducFve data types • Recall, a natural number n is either: – zero, or – m + 1 • We use a data type to represent this definiFon exactly: type nat = Zero | Succ of nat 66 InducFve data types • Recall, a natural number n is either: – zero, or – m + 1 • We use a data type to represent this definiFon exactly: type nat = Zero | Succ of nat let rec nat_to_int (n : nat) : int = match n with Zero -> 0
| Succ n -> 1 + nat_to_int n

type sitree = int stree
match n with
Zero -> 0
General form:
InducFve data types
677
type (‘key, ‘val) tree =
• Recall, a natural number n is either: Leaf
– zero, or
| Node of ‘key * ‘val * (‘key, ‘val) tree * (‘key, ‘val) tree
– m + 1
• We use a data type to represent this definiFon exactly:
type nat = Zero | Succ of nat
let rec nat_to_int (n : nat) : int =
A more convenFonal notaFon
type ‘a stree = (string, ‘a) tree
| Succ n -> 1 + nat_to_int n
would have been (but is not ML): definiFon: definiFon:
let rec double_nat (n : nat) : nat =
match n with
type ‘x f = body type f x = body use:| Zero -> Zero use:
arg f
| Succ m -> Succ (Succ(double_nat m))
f arg
0

TopHat Q10-Q13

What is the type of comp?
let comp f g x = f (g x)
74

What is the type of comp?
let comp f g x = f (g x)
comp : (‘b -> ‘c) -> (‘a -> ‘b) ->
(‘a -> ‘c)
75

How about reduce?
let rec reduce f u xs = match xs with
| [] -> u
| hd::tl -> f hd (reduce f u tl)
What’s the most general type of reduce?
77

How about reduce?
let rec reduce f u xs = match xs with
| [] -> u
| hd::tl -> f hd (reduce f u tl)
What’s the most general type of reduce?
Based on the
paRerns, we know xs must be a (‘a list) for some type ‘a.
78

How about reduce?
let rec reduce f u (xs: ‘a list) = match xs with
| [] -> u
| hd::tl -> f hd (reduce f u tl)
What’s the most general type of reduce?
79

How about reduce?
let rec reduce f u (xs: ‘a list) = match xs with
| [] -> u
| hd::tl -> f hd (reduce f u tl)
What’s the most
general type of reduce?
f is called so it must be a funcKon of two arguments.
80

How about reduce?
letrecreduce(f:?->?->?)u(xs:’alist) = match xs with
| [] -> u
| hd::tl -> f hd (reduce f u tl)
What’s the most general type of reduce?
81

How about reduce?
letrecreduce(f:?->?->?)u(xs:’alist) = match xs with
| [] -> u
| hd::tl -> f hd (reduce f u tl)
What’s the most general type of reduce?
Furthermore, hd came from xs, so f must take an ‘a value as its first argument.
82

How about reduce?
let rec reduce (f:’a -> ? -> ?) u (xs: ‘a list) = match xs with
| [] -> u
| hd::tl -> f hd (reduce f u tl)
What’s the most general type of reduce?
83

How about reduce?
let rec reduce (f:’a -> ? -> ?) u (xs: ‘a list) = match xs with
| [] -> u
| hd::tl -> f hd (reduce f u tl)
What’s the most general type of reduce?
The second argument to f must have the same type as the result of reduce. Let’s call it ‘b.
84

How about reduce?
let rec reduce (f:’a -> ‘b -> ?) u (xs: ‘a list) : ‘b = match xs with
| [] -> u
| hd::tl -> f hd (reduce f u tl)
What’s the most general type of reduce?
The result of f must have the same type as the result of reduce overall: ‘b.
85

How about reduce?
let rec reduce (f:’a -> ‘b -> ‘b) u (xs: ‘a list) : ‘b = match xs with
| [] -> u
| hd::tl -> f hd (reduce f u tl)
What’s the most general type of reduce?
86

How about reduce?
let rec reduce (f:’a -> ‘b -> ?) u (xs: ‘a list) : ‘b = match xs with
| [] -> u
| hd::tl –
What’s the m
> f hd (reduce f u tl)
ost general type of reduce?
If xs is empty, then reduce returns u. So u’s type must be ‘b.
87

How about reduce?
let rec reduce (f:’a -> ‘b -> ?) (u:’b) (xs: ‘a list) : ‘b = match xs with
| [] -> u
| hd::tl -> f hd (reduce f u tl)
What’s the most general type of reduce?
88

How about reduce?
let rec reduce (f:’a -> ‘b -> ‘b) (u:’b) (xs: ‘a list) : ‘b = match xs with
| [] -> u
| hd::tl -> f hd (reduce f u tl)
What’s the most general type of reduce?
(‘a -> ‘b -> ‘b) -> ‘b -> ‘a list -> ‘b
91