程序代写代做代考 C data structure ocaml Simple Data

Simple Data
CSI 3120
Amy Felty University of Ottawa
slides copyright 2017, 2018, 2019, 2020 Author David Walker, updated by Amy Felty permission granted to reuse these slides for non-commercial educational purposes
1

What is the single most important mathematical concept ever developed in human history?
2

What is the single most important mathematical concept ever developed in human history?
An answer: The mathematical variable
3

What is the single most important mathematical concept ever developed in human history?
An answer: The mathematical variable (runner up: natural numbers/induction)
4

5 Why is the mathematical variable so important?
The mathematician says:
“Let x be some integer, we define a polynomial over x …”

6 Why is the mathematical variable so important?
The mathematician says:
“Let x be some integer, we define a polynomial over x …”
What is going on here? The mathematician has separated a definition (of x) from its use (in the polynomial).
This is the most primitive kind of abstraction (x is some integer) Abstraction is the key to controlling complexity and without it,
modern mathematics, science, and computation would not exist. It allows reuse of ideas, theorems … functions and programs!

OCAML BASICS: LET DECLARATIONS
7

8
Abstraction
• Good programmers identify repeated patterns in their code and factor out the repetition into meaningful components
• In O’Caml, the most basic technique for factoring your code is to use let expressions
• Instead of writing this expression: (2 + 3) * (2 + 3)

Abstraction & Abbreviation
• Good programmers identify repeated patterns in their code and factor out the repetition into meaning components
• In O’Caml, the most basic technique for factoring your code is to use let expressions
• Instead of writing this expression: (2 + 3) * (2 + 3)
• We write this one:
9
let x = 2 + 3 in x*x

10
A Few More Let Expressions
let x = 2 in
let squared = x * x in
let cubed = x * squared in
squared * cubed

A Few More Let Expressions
11
let x = 2 in
let squared = x * x in
let cubed = x * squared in
squared * cubed
let a = “a” in
let b = “b” in
let as = a ^ a ^ a in
let bs = b ^ b ^ b in
as ^ bs

12
Abstraction & Abbreviation • Two kinds of let:
if tuesday() then
let x = 2 + 3 in
x+x else
0
let x = 2 + 3
let y = x + 17 / x
let … in … is an expression that
can appear inside any other expression
The scope of x does not extend outside the enclosing “in”
let … without “in” is a top-level declaration
Variables x and y may be exported; used by other modules
(Don’t need ;; if another let comes next; do need it if the next top-level declaration is an expression)

13
Binding Variables to Values
• Each OCaml variable is bound to 1 value
• The value to which a variable is bound to never changes!
let x = 3
let add_three (y:int) : int = y + x

Binding Variables to Values
• Each OCaml variable is bound to 1 value
• The value to which a variable is bound to never changes!
It does not matter what I write next. add_three will always add 3!
14
let x = 3
let add_three (y:int) : int = y + x

Binding Variables to Values
• Each OCaml variable is bound to 1 value
• The value to which a variable is bound to never changes!
15
let x = 3
let add_three (y:int) : int = y + x
let x = 4
let add_four (y:int) : int = y + x
a distinct variable that “happens to be spelled the same”

Binding Variables to Values
• Since the 2 variables (both happened to be named x) are actually different, unconnected things, we can rename them
16
let x = 3
let add_three (y:int) : int = y + x
let zzz = 4
let add_four (y:int) : int = y + zzz
rename x
to zzz
if you want to, replacing its uses

Binding Variables to Values
• OCaml is a statically scoped (or lexically scoped) language
17
let x = 3
let add_three (y:int) : int = y + x
let x = 4
let add_four (y:int) : int = y + x
let add_seven (y:int) : int =
add_three (add_four y)
we can use add_three without worrying about the second definition of x

18
How do let expressions operate?
let x = 2 + 1 in x * x

How do let expressions operate?
–>
19
let x = 2 + 1 in x * x
let x = 3 in x * x

20
How do let expressions operate?
–>
substitute –> 3 for x
let x = 2 + 1 in x * x
let x = 3 in x * x
3*3

21
How do let expressions operate?
–>
substitute –> 3 for x
–>
let x = 2 + 1 in x * x
let x = 3 in x * x
3*3
9

22
How do let expressions operate?
–>
substitute –> 3 for x
–>
let x = 2 + 1 in x * x
let x = 3 in x * x
3*3
Note: e1 –> e2 means e1 evaluates to e2 in one step
9

Another Example
23
let x = 2 in
let y = x + x in y*x

Another Example
substitute 2 for x
24
let x = 2 in
let y = x + x in y*x
–>
let y = 2 + 2 in y*2

Another Example
substitute 2 for x
25
–>
–>
let x = 2 in
let y = x + x in y*x
let y = 2 + 2 in y*2
let y = 4 in y*2

26
Another Example
substitute 2 for x
let x = 2 in
let y = x + x in y*x
–>
–>
–>
substitute 4 for y
let y = 2 + 2 in y*2
let y = 4 in y*2
4*2

Another Example
substitute 2 for x
27
let x = 2 in
let y = x + x in y*x
Moral: Let operates by substituting computed values for variables
–>
–>
–>
substitute 4 for y
–>
let y = 2 + 2 in y*2
let y = 4 in y*2
4*2
8

OCAML BASICS:
TYPE CHECKING AGAIN
29

30
Back to Let Expressions … Typing
x given type of e1 for use in e2
let x = e1 in e2
overall expression takes on the type of e2

Back to Let Expressions … Typing
x given type of e1 for use in e2
31
let x = e1 in e2
overall expression takes on the type of e2
let x = 3 + 4 in
string_of_int x
x has type int
for use inside the let body
overall expression has type string

OCAML BASICS: FUNCTIONS
32

33
Defining functions
let add_one (x:int) : int = 1 + x

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

35
Defining functions • Nonrecursive functions:
let add_one (x:int) : int = 1 + x
let add_two (x:int) : int = add_one (add_one x)
definition of add_one must come before use

36
Defining functions • Nonrecursive functions:
let add_one (x:int) : int = 1 + x
let add_two (x:int) : int = add_one (add_one x)
• With a local definition:
local function definition hidden from clients
Note that there are no types. OCaml figures them out.
Good style: types on top-level definitions
let add_two’ (x:int) : int = add_one (add_one x)
let add_one x = 1 + x in

37
Some functions:
Types for Functions
let add_one (x:int) : int = 1 + x
let add_two (x:int) : int = add_one (add_one x)
let add (x:int) (y:int) : int = x + y
Types for functions:
function with two arguments
add_one : int -> int
add_two : int -> int
add : int -> int -> int

Rule for type-checking functions
General Rule:
Example:
38
If a function f : T1 -> T2 and an argument e : T1 then f e : T2
add_one : int -> int
3 + 4 : int
add_one (3 + 4) : int

39
Rule for type-checking functions • Recall the type of add:
Definition:
Type:
let add (x:int) (y:int) : int = x+y
add : int -> int -> int

40
Rule for type-checking functions • Recall the type of add:
Definition:
Type:
Same as:
let add (x:int) (y:int) : int = x+y
add : int -> int -> int
add : int -> (int -> int)

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

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

43
Rule for type-checking functions
General Rule:
A -> B -> C
same as:
A -> (B -> C)
If a function 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

44
Rule for type-checking functions
General Rule:
A -> B -> C
same as:
A -> (B -> C)
If a function 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
(add (3 + 4)) 7 : int

45
Rule for type-checking functions
General Rule:
A -> B -> C
same as:
A -> (B -> C)
If a function 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
add (3 + 4) 7 : int

Rule for type-checking functions
Example:
46
let munge (b:bool) (x:int) : ?? =
if not b then
string_of_int x
else
“hello” ;;
let y = 17;;
munge (y > 17) : ??
munge true (f (munge false 3)) : ??
f : ??
munge true (g munge) : ??
g : ??

Rule for type-checking functions
Example:
47
let munge (b:bool) (x:int) : ?? =
if not b then
string_of_int x
else
“hello” ;;
let y = 17;;
munge (y > 17) : ??
munge true (f (munge false 3)) : ??
f : string -> int
munge true (g munge) : ??
g : (bool -> int -> string) -> int

48
One key thing to remember
• If you have a function f with a type like this:
A -> B -> C -> D -> E -> F
• Then each time you add an argument, you can get the type of the result by knocking off the first type in the series
fa1:B->C->D->E->F (ifa1:A)
f a1 a2 : C -> D -> E -> F f a1 a2 a3 : D -> E -> F
f a1 a2 a3 a4 a5 : F
(if a2 : B)
(if a3 : C)
(if a4 : D and a5 : E)

OUR FIRST* COMPLEX DATA STRUCTURE! THE TUPLE
* it is really our second complex data structure since functions are data structures too!
49

50
Tuples
• A tuple is a fixed, finite, ordered collection of expressions
• Some examples with their types:
(1, 2) : int * int
(“hello”, 7 + 3, true) : string * int * bool (‘a’, (“hello”, “goodbye”)) : char * (string * string)

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

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

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 –> 2+2+4
–> 8

54
Rules for Typing Tuples
ife1:t1 ande2:t2 then (e1, e2) : t1 * t2

55
Rules for Typing Tuples
if e1 : t1 * t2 then
x1 : t1 and x2 : t2
inside the expression e2
ife1:t1 ande2:t2 then (e1, e2) : t1 * t2
let (x1,x2) = e1 in
e2
overall expression takes on the type of e2

56
Distance between two points
c2 =a2 +b2
a (x1, y1)
b c
Problem:
• A point is represented as a pair of floating point values.
• Write a function that takes in two points as arguments and returns the distance between them as a floating point number
(x2, y2)

57
Writing Functions Over Typed Data
Steps to writing functions over typed data:
1. Write down the function and argument names
2. Write down argument and result types
3. Write down some examples (in a comment)

58
Writing Functions Over Typed Data
Steps to writing functions over typed data:
1. Write down the function and argument names
2. Write down argument and result types
3. Write down some examples (in a comment)
4. Deconstruct input data structures
• the argument types suggests how to do it
5. Build new output values
• the result type suggests how you do it

59
Writing Functions Over Typed Data Steps to writing functions over typed data:
1.
2.
3.
4. 5. 6.
Write down the function and argument names
Write down argument and result types
Write down some examples (in a comment)
Deconstruct input data structures
• the argument types suggests how to do it
Build new output values
• the result type suggests how you do it
Clean up by identifying repeated patterns
• define and reuse helper functions
• your code should be elegant and easy to read

Writing Functions Over Typed Data Steps to writing functions over typed data:
1.
2.
3.
4. 5. 6.
Write down the function and argument names
Write down argument and result types
Write down some examples (in a comment)
Deconstruct input data structures
• the argument types suggests how to do it
Build new output values
• the result type suggests how you do it
Clean up by identifying repeated patterns
• define and reuse helper functions
• your code should be elegant and easy to read
Types help structure your thinking about how to write programs.
60

61
Distance between two points a type abbreviation
c2 =a2 +b2
a (x1, y1)
b c
type point = float * float
(x2, y2)

62
Distance between two points
c2 =a2 +b2
a (x1, y1)
b c
type point = float * float
let distance (p1:point) (p2:point) : float =
write down function name argument names and types
(x2, y2)

63
Distance between two points
examples
c2 =a2 +b2
a (x1, y1)
b c
type point = float * float
(* distance (0.0,0.0) (0.0,1.0) == 1.0
* distance (0.0,0.0) (1.0,1.0) == sqrt(1.0 + 1.0) *
* from the picture:
* distance (x1,y1) (x2,y2) == sqrt(a^2 + b^2) *)
let distance (p1:point) (p2:point) : float =
(x2, y2)

64
Distance between two points
c2 =a2 +b2
a (x1, y1)
b c
type point = float * float
let distance (p1:point) (p2:point) : float =
let (x1,y1) = p1 in let (x2,y2) = p2 in …
deconstruct function inputs
(x2, y2)

65
Distance between two points
c2 =a2 +b2
a (x1, y1)
b c
type point = float * float
let distance (p1:point) (p2:point) : float =
let (x1,y1) = p1 in
let (x2,y2) = p2 in
sqrt ((x2 -. x1) *. (x2 -. x1) +.
(y2 -. y1) *. (y2 -. y1))
compute function results
notice operators on floats have a “.” in them
(x2, y2)

66
Distance between two points
c2 =a2 +b2
a (x1, y1)
b c
type point = float * float
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))
define helper functions to avoid repeated code
(x2, y2)

67
Distance between two points
c2 =a2 +b2
a (x1, y1)
b c
type point = float * float
let distance (p1:point) (p2:point) : float =
let square x = x *. let (x1,y1) = p1 in let (x2,y2) = p2 in sqrt (square (x2 -.
let pt1 = (2.0,3.0) let pt2 = (0.0,1.0) let dist12 = distance
x in
x1) +. square (y2 -. y1))
pt1 pt2
(x2, y2)
testing

MORE TUPLES
68

69
Tuples • Here’s a tuple with 2 fields:
(4.0, 5.0) : float * float

70
Tuples
• Here’s a tuple with 2 fields:
(4.0, 5.0) : float * float
• Here’s a tuple with 3 fields:
(4.0, 5, “hello”) : float * int * string

71
Tuples
• Here’s a tuple with 2 fields:
(4.0, 5.0) : float * float
• Here’s a tuple with 3 fields:
(4.0, 5, “hello”) : float * int * string
• Here’s a tuple with 4 fields:
(4.0, 5, “hello”, 55) : float * int * string * int

72
Tuples
• Here’s a tuple with 2 fields:
(4.0, 5.0) : float * float
• Here’s a tuple with 3 fields:
(4.0, 5, “hello”) : float * int * string
• Here’s a tuple with 4 fields:
(4.0, 5, “hello”, 55) : float * int * string * int
• Here’s a tuple with 0 fields: () : unit

SUMMARY:
BASIC FUNCTIONAL PROGRAMMING
76

77
Writing Functions Over Typed Data
Steps to writing functions over typed data:
1. Write down the function 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 identifying repeated patterns
For tuple types:
– when the input has type t1 * t2 • use let (x,y) = … to deconstruct
– when the output has type t1 * t2 • use (e1, e2) to construct
We will see this paradigm repeat itself over and over