程序代写代做代考 ocaml go data structure C algorithm Java 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
 You should be able to use GradeScope now. If you have some difficulty with submitting your homework to GradeScope, send a message to Piazza in which you describe the difficulty.
 First programming assignment is due Friday, February 7, Tuesday, February 11, no later than 11:59 pm.

In the previous classes…

Type Soundness
“Well typed programs do not go wrong” Programming languages with this property have
sound type systems. They are called safe languages. Safe languages are generally immune to buffer overrun
vulnerabiliRes, uniniRalized pointer vulnerabiliRes, etc., etc. (but not immune to all bugs!)
Safe languages: ML, Java, Python, … Unsafe languages: C, C++, Pascal
38

Another Example
subsDtute 2 for x
29
let x = 2 in
let y = x + x in y*x
Moral: Let operates by subs&tu&ng computed values for variables
let y = 2 + 2 in y*2
–>
–>
subsDtute 4 for y
let y = 4 in y*2
4*2
8
–> –>

let keyword
Defining funcDons
36
let add_one (x:int) : int = 1 + x
funcDon name
type of result
type of argument
expression
that computes value produced by funcDon
argument name
Note: recursive funcDons with begin with “let rec”

45
Rule for type-checking funcDons
General Rule:
A -> B -> C
same as:
A -> (B -> C)
If a funcDon f : T1 -> T2 and an argument e : T1 then f e : T2
Example:
add : int -> (int -> int)
3 + 4 : int
add (3 + 4) : int -> int

Tuples
• To use a tuple, we extract its components
• General case:
53
let (id1, id2, …, idn) = e1 in e2
• An example:
let (x,y) = (2,4) in x + x + y

77
Unit • Unit is the tuple with zero fields!
() : unit
• the unit value is wriZen with an pair of parens
• there are no other values with this type!
• Why is the unit type and value useful?
• Every expression has a type:
(print_string “hello world\n”) : unit
• Expressions executed for their effect return the unit value

20

Wri,ng Func,ons Over Typed Data
Steps to wri,ng func,ons over typed data:
1. Write down the func,on and argument names
2. Write down argument and result types
3. Write down some examples (in a comment)
4. Deconstruct input data structures
5. Build new output values
6. Clean up by iden,fying repeated paLerns

For op,on types:
when the input has type t op,on, deconstruct with:
when the output has type t op,on, construct with:
match … with
| None -> …
| Some s -> …
Some (…)
None

Input and Output Channels
The normal way of opening a file in OCaml returns a channel. There are two kinds of channels:
• channels that write to a file: type out_channel
• channels that read from a file: type in_channel
Four operations that will be useful are:
• Open input file: open_in: string -> in_channel
• Open out file: open_out: string -> out_channel
• Close input file: close_in: in_channel -> unit
• Close input file: close_out: out_channel -> unit
If you want to use a channel, you can use let, as usual.

Lists are Recursive Data
• In OCaml, a list value is:
– [ ] (the empty list)
– v :: vs (a value v followed by a shorter list of values vs)
36
Induc,ve Case
Base Case

TopHat Q0

Learning Goals for today • MoreonInductivedatatypes
Lists
• Functionalprogramming
Writing more complex functions Factoring your code

More Inductive Thinking

37
Lists are Induc,ve Data
• In OCaml, a list value is:
– [ ] (the empty list)
– v :: vs (a value v followed by a shorter list of values vs)
• An example:
– 2::3::5::[]hastypeintlist
– isthesameas: 2::(3::(5::[])) – “::” is called “cons”
• An alterna,ve syntax (“syntac,c sugar” for lists): – [2; 3; 5]
– Butthisisjustashorthandfor2::3::5::[]. Ifyoueverget confused fall back on the 2 basic constructors: :: and []

Typing Lists • Typing rules for lists:
(1) [ ] may have any list type t list
(2)
then (e1 :: e2) : t list
ife1:tand e2:tlist
38

Typing Lists • Typing rules for lists:
(1) [ ] may have any list type t list
(2)
then (e1 :: e2) : t list
ife1:tand e2:tlist • More examples:
(1 + 2) :: (3 + 4) :: [ ] : ?? (2::[])::(5::6 ::[])::[] :?? [ [2]; [5; 6] ] : ??
39

Typing Lists • Typing rules for lists:
(1) [ ] may have any list type t list
(2)
then (e1 :: e2) : t list
ife1:tand e2:tlist • More examples:
(1 + 2) :: (3 + 4) :: [ ] : int list
(2::[])::(5::6 ::[])::[] :intlistlist
[ [2]; [5; 6] ] : int list list
(Remember that the 3rd example is an abbrevia,on for the 2nd)
40

41
Another Example
• What type does this have?
[ 2 ] :: [ 3 ]

Another Example
• What type does this have?
[ 2 ] :: [ 3 ]
42
int list
int list
# [2] :: [3];;
Error: This expression has type int but an
#
expression was expected of type
int list

43
Another Example
• What type does this have?
[ 2 ] :: [ 3 ]
int list
int list
• Give me a simple fix that makes the expression type check?

44
Another Example
• What type does this have?
[ 2 ] :: [ 3 ]
int list
int list
• Give me a simple fix that makes the expression type check? Either: 2 :: [3] :intlist
Or: [ 2 ] :: [ [ 3 ] ] : int list list

TopHat Q1-Q7

45
Analyzing Lists
• Just like op,ons, there are two possibili,es when deconstruc,ng lists. Hence we use a match with two branches
(* return Some v, if v is the first list element;
return None, if the list is empty *)
let head (xs : int list) : int option =

Analyzing Lists
• Just like op,ons, there are two possibili,es when deconstruc,ng lists. Hence we use a match with two branches
46
(* return Some v, if v is the first list element;
return None, if the list is empty *)
let head (xs : int list) : int option =
match xs with
| [] ->
| hd :: _ ->
we don’t care about the contents of the tail of the list so we use the underscore

47
Analyzing Lists
• Just like op,ons, there are two possibili,es when deconstruc,ng lists. Hence we use a match with two branches
(* return Some v, if v is the first list element;
return None, if the list is empty *)
let head (xs : int list) : int option =
match xs with
| [] -> None
| hd :: _ -> Some hd
• This func,on isn’t recursive — we only extracted a small , fixed amount of informa,on from the list — the first element

48
A more interes,ng example
(* Given a list of pairs of integers,
produce the list of products of the pairs
prods [(2,3); (4,7); (5,2)] == [6; 28; 10]
*)

49
A more interes,ng example
(* Given a list of pairs of integers,
produce the list of products of the pairs
prods [(2,3); (4,7); (5,2)] == [6; 28; 10]
*)
let rec prods (xs : (int * int) list) : int list =

50
A more interes,ng example
(* Given a list of pairs of integers,
produce the list of products of the pairs
prods [(2,3); (4,7); (5,2)] == [6; 28; 10]
*)
let rec prods (xs : (int * int) list) : int list =
match xs with
| [] ->
| (x,y) :: tl ->

51
A more interes,ng example
(* Given a list of pairs of integers,
produce the list of products of the pairs
prods [(2,3); (4,7); (5,2)] == [6; 28; 10]
*)
let rec prods (xs : (int * int) list) : int list =
match xs with
| [] -> []
| (x,y) :: tl ->

A more interes,ng example
52
(* Given a list of pairs of integers,
produce the list of products of the pairs
prods [(2,3); (4,7); (5,2)] == [6; 28; 10]
*)
let rec prods (xs : (int * int) list) : int list =
match xs with
| [] -> []
| (x,y) :: tl -> ?? :: ??
the result type is int list, so we can speculate that we should create a list

53
A more interes,ng example
(* Given a list of pairs of integers,
produce the list of products of the pairs
prods [(2,3); (4,7); (5,2)] == [6; 28; 10]
*)
let rec prods (xs : (int * int) list) : int list =
match xs with
| [] -> []
| (x,y) :: tl -> (x * y) :: ??
the first element is the product

A more interes,ng example
54
(* Given a list of pairs of integers,
produce the list of products of the pairs
prods [(2,3); (4,7); (5,2)] == [6; 28; 10]
*)
let rec prods (xs : (int * int) list) : int list =
match xs with
| [] -> []
| (x,y) :: tl -> (x * y) :: ??
to complete the job, we must compute the products for the rest of the list

55
A more interes,ng example
(* Given a list of pairs of integers,
produce the list of products of the pairs
prods [(2,3); (4,7); (5,2)] == [6; 28; 10]
*)
let rec prods (xs : (int * int) list) : int list =
match xs with
| [] -> []
| (x,y) :: tl -> (x * y) :: prods tl

57
Another example: zip
(* Given two lists of integers,
return None if the lists are different lengths
otherwise stitch the lists together to create
Some of a list of pairs
zip [2; 3] [4; 5] == Some [(2,4); (3,5)]
zip [5; 3] [4] == None
zip [4; 5; 6] [8; 9; 10; 11; 12] == None
*)
(Give it a try.)

58
Another example: zip
let rec zip (xs : int list) (ys : int list)
: (int * int) list option =

59
Another example: zip
let rec zip (xs : int list) (ys : int list)
: (int * int) list option =
match (xs, ys) with

60
Another example: zip
let rec zip (xs : int list) (ys : int list)
: (int * int) list option =
match (xs, ys) with
| ([], []) ->
| ([], y::ys’) ->
| (x::xs’, []) ->
| (x::xs’, y::ys’) ->

61
Another example: zip
let rec zip (xs : int list) (ys : int list)
: (int * int) list option =
match (xs, ys) with
| ([], []) -> Some []
| ([], y::ys’) ->
| (x::xs’, []) ->
| (x::xs’, y::ys’) ->

62
Another example: zip
let rec zip (xs : int list) (ys : int list)
: (int * int) list option =
match (xs, ys) with
| ([], []) -> Some []
| ([], y::ys’) -> None
| (x::xs’, []) -> None
| (x::xs’, y::ys’) ->

Another example: zip
63
let rec zip (xs : int list) (ys : int list)
: (int * int) list option =
match (xs, ys) with
| ([], []) -> Some []
| ([], y::ys’) -> None
| (x::xs’, []) -> None
| (x::xs’, y::ys’) -> (x, y) :: zip xs’ ys’
is this ok?

Another example: zip
64
let rec zip (xs : int list) (ys : int list)
: (int * int) list option =
match (xs, ys) with
| ([], []) -> Some []
| ([], y::ys’) -> None
| (x::xs’, []) -> None
| (x::xs’, y::ys’) -> (x, y) :: zip xs’ ys’
No! zip returns a list op,on, not a list!
We need to match it and decide if it is Some or None.

Another example: zip
65
let rec zip (xs : int list) (ys : int list)
: (int * int) list option =
match (xs, ys) with
| ([], []) -> Some []
| ([], y::ys’) -> None
| (x::xs’, []) -> None
| (x::xs’, y::ys’) ->
(match zip xs’ ys’ with
None -> None
| Some zs -> (x,y) :: zs)
Is this ok?

66
Another example: zip
let rec zip (xs : int list) (ys : int list)
: (int * int) list option =
match (xs, ys) with
| ([], []) -> Some []
| ([], y::ys’) -> None
| (x::xs’, []) -> None
| (x::xs’, y::ys’) ->
(match zip xs’ ys’ with
None -> None
| Some zs -> Some ((x,y) :: zs))

Another example: zip
67
let rec zip (xs : int list) (ys : int list)
: (int * int) list option =
match (xs, ys) with
| ([], []) -> Some []
| (x::xs’, y::ys’) ->
(match zip xs’ ys’ with
None -> None
| Some zs -> Some ((x,y) :: zs))
| (_, _) -> None
Clean up.
Reorganize the cases.
PaLern matching proceeds in order.

68
A bad list example
let rec sum (xs : int list) : int =
match xs with
| hd::tl -> hd + sum tl

A bad list example
69
let rec sum (xs : int list) : int =
match xs with
| hd::tl -> hd + sum tl
# Characters 39-78:
..match xs with
hd :: tl -> hd + sum tl..
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched: []
val sum : int list -> int =

TopHat Q8-Q9

An example: insertion sort

71
Recall Inser,on Sort
• At any point during the inser,on sort:
– some ini,al segment of the array will be sorted
– the rest of the array will be in the same (unsorted) order as it was originally
-5
-2
3
-4
10
6
7
sorted
unsorted

Recall Inser,on Sort
• At any point during the inser,on sort:
– some ini,al segment of the array will be sorted
– the rest of the array will be in the same (unsorted) order as it was originally
72
-5
-2
3
-4
10
6
7
sorted
unsorted
• At each step, take the next item in the array and insert it in order into the sorted por,on of the list
-5
-4
-2
3
10
6
7
sorted
unsorted

Inser,on Sort With Lists
• The algorithm is similar, except instead of one array, we will
maintain two lists, a sorted list and an unsorted list
list 1:
sorted
list 2:
73
-5
-2
3
-4
10
6
7
• We’ll factor the algorithm:
– a func,on to insert into a sorted list
– a sor,ng func,on that repeatedly inserts
unsorted

74
Insert
(* insert x in to sorted list xs *)
let rec insert (x : int) (xs : int list) : int list =

75
Insert
(* insert x in to sorted list xs *)
let rec insert (x : int) (xs : int list) : int list =
match xs with
| [] ->
| hd :: tl ->
a familiar paLern:
analyze the list by cases

76
Insert
(* insert x in to sorted list xs *)
let rec insert (x : int) (xs : int list) : int list =
match xs with
| [] -> [x]
| hd :: tl ->
insert x into the empty list

77
Insert
(* insert x in to sorted list xs *)
let rec insert (x : int) (xs : int list) : int list =
match xs with
| [] -> [x]
| hd :: tl ->
if hd < x then hd :: insert x tl build a new list with: • hd at the beginning • the result of inser,ng x in to the tail of the list awerwards 78 Insert (* insert x in to sorted list xs *) let rec insert (x : int) (xs : int list) : int list = match xs with | [] -> [x]
| hd :: tl ->
if hd < x then hd :: insert x tl else x :: xs put x on the front of the list, the rest of the list follows 79 Inser,on Sort type il = int list insert : int -> il -> il
(* insertion sort *)
let rec insert_sort(xs : il) : il =

80
Inser,on Sort
type il = int list
insert : int -> il -> il
(* insertion sort *)
let rec insert_sort(xs : il) : il =
let rec aux (sorted : il) (unsorted : il) : il =
in

81
Inser,on Sort
type il = int list
insert : int -> il -> il
(* insertion sort *)
let rec insert_sort(xs : il) : il =
let rec aux (sorted : il) (unsorted : il) : il =
in
aux [] xs

82
Inser,on Sort
type il = int list
insert : int -> il -> il
(* insertion sort *)
let rec insert_sort(xs : il) : il =
let rec aux (sorted : il) (unsorted : il) : il =
match unsorted with
| [] ->
| hd :: tl ->
in
aux [] xs

83
Inser,on Sort
type il = int list
insert : int -> il -> il
(* insertion sort *)
let rec insert_sort(xs : il) : il =
let rec aux (sorted : il) (unsorted : il) : il =
match unsorted with
| [] -> sorted
| hd :: tl -> aux (insert hd sorted) tl
in
aux [] xs

More functional programming

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.
– beRer, 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 creaKng new funcKons?
– findandfixabuginonecopy,havetofixinallofthem.
– decide to change the funcKonality, have to track down all of the places where it gets used.
21

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 Q10-Q13

Summary
• MoreonInductivedatatypes
Lists
• Functionalprogramming
Writing more complex functions Factoring your code