CS计算机代考程序代写 ocaml data structure Simple Data

Simple Data

Simple Data

1

slides copyright 2017, 2018, 2019, 2020
Author David Walker, updated by Amy Felty

permission granted to reuse these slides for non-commercial educational purposes

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

Why is the mathematical variable so important?

The mathematician says:

“Let x be some integer, we define a polynomial over x …”

5

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!

6

OCAML BASICS:
LET DECLARATIONS

7

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)

8

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:

• We write this one:

(2 + 3) * (2 + 3)

let x = 2 + 3 in

x * x

9

A Few More Let Expressions

let x = 2 in

let squared = x * x in

let cubed = x * squared in

squared * cubed

10

A Few More Let Expressions

let a = “a” in

let b = “b” in

let as = a ^ a ^ a in

let bs = b ^ b ^ b in

as ^ bs

let x = 2 in

let squared = x * x in

let cubed = x * squared in

squared * cubed

11

Abstraction & Abbreviation

• Two kinds of let:

let … in … is an expression that
can appear inside any other expression

The scope of x does not extend outside
the enclosing “in”

let x = 2 + 3

let y = x + 17 / x

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)

if tuesday() then

let x = 2 + 3 in

x + x

else

0

12

OCaml for the Skeptical – Let

Let Expressions

https://www2.lib.uchicago.edu/keith/ocaml-class/definitions.html
https://www.cs.cornell.edu/courses/cs3110/2019sp/textbook/basics/let_expressions.html

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

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

It does not
matter what
I write next.
add_three
will always
add 3!

14

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

let x = 4

let add_four (y:int) : int = y + x

a distinct
variable that
“happens to
be spelled the
same”

15

Binding Variables to Values

• Since the 2 variables (both happened to be named x) are
actually different, unconnected things, we can rename them

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

16

Binding Variables to Values

• OCaml is a statically scoped (or lexically scoped) language

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

17

How do let expressions operate?

let x = 2 + 1 in x * x

18

How do let expressions operate?

let x = 2 + 1 in x * x

–>

let x = 3 in x * x

19

How do let expressions operate?

let x = 2 + 1 in x * x

–>

let x = 3 in x * x

–>

3 * 3

substitute
3 for x

20

How do let expressions operate?

let x = 2 + 1 in x * x

–>

let x = 3 in x * x

–>

3 * 3

–>

9

substitute
3 for x

21

How do let expressions operate?

let x = 2 + 1 in x * x

–>

let x = 3 in x * x

–>

3 * 3

–>

9

substitute
3 for x

Note: e1 –> e2
means e1 evaluates
to e2 in one step

22

Another Example

let x = 2 in

let y = x + x in

y * x

23

Another Example

let x = 2 in

let

y *

y

x

= x + x in

–>

substitute
2 for x

let y = 2 + 2 in

y * 2

24

Another Example

let x = 2 in

let y = x + x in

y * x

–>

–>

substitute
2 for x

let y = 2 + 2 in

y * 2

inlet y = 4

y * 2

25

Another Example

let x = 2 in

let y = x + x in

y * x

–>

–>

–>

substitute
2 for x

let y = 2 + 2 in

y * 2

inlet y = 4

y * 2

4 * 2

substitute
4 for y

26

Another Example

let x = 2 in

let

y *

y

x

= x + x in

–>

–>

–>

substitute
2 for x

let

y *

y

2

= 2 + 2 in

let y = 4 in

y * 2

4 * 2

–>
8

substitute
4 for y

Moral: Let
operates by
substituting

computed values
for variables

27

OCAML BASICS:
TYPE CHECKING AGAIN

29

Back to Let Expressions … Typing

let x = e1 in

e2

overall expression
takes on the type of e2

x given type of e1 for use in e2

30

Back to Let Expressions … Typing

let x = e1 in

e2

x given type of e1 for use in e2

let x = 3 + 4 in

string_of_int x

overall expression
takes on the type of e2

x has type int
for use inside the
let body

overall expression
has type string

31

OCAML BASICS:
FUNCTIONS

32

let add_one (x:int) : int = 1 + x

Defining functions
33

Defining functions

function name

argument name

type of argument

type of result
expression
that computes
value produced

by function

let keyword

let add_one (x:int) : int = 1 + x

Note: recursive functions begin with “let rec”

34

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

35

Defining functions

• Nonrecursive functions:

• With a local definition:

let add_one (x:int) : int = 1 + x

let add_two (x:int) : int = add_one (add_one x)

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 =

let add_one x = 1 + x in

add_one (add_one x)

36

Types for Functions

Some 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

function with two arguments

Types for functions:

add_one : int -> int

add_two : int -> int

add : int -> int -> int

37

val add_two : int -> int =

Rule for type-checking functions

Example:

add_one : int -> int

3 + 4 : int

add_one (3 + 4) : int

If a function f : T1 -> T2
and an argument e : T1
then f e : T2

General Rule:

38

Rule for type-checking functions

• Recall the type of add:

Definition:

let add (x:int) (y:int) : int =

x + y

add : int -> int -> int

Type:

39

Rule for type-checking functions

• Recall the type of add:

Definition:

let add (x:int) (y:int) : int =

x + y

add : int -> int -> int

Type:

add : int -> (int -> int)

Same as:

40

Rule for type-checking functions

add : int -> int -> int

3 + 4 : int

add (3 + 4) : ???

If a function f : T1 -> T2
and an argument e : T1
then f e : T2

General Rule:

Example:

A -> B -> C

same as:

A -> (B -> C)

41

Rule for type-checking functions

Example:

add : int -> (int -> int)

3 + 4 : int

add (3 + 4) :

General Rule:

42

A -> B -> C

same as:

A -> (B -> C)

If a function f : T1 -> T2
and an argument e : T1
then f e : T2

Rule for type-checking functions

add : int -> (int -> int)

3 + 4 : int

add (3 + 4) : int -> int

General Rule:

Example:

43

If a function f : T1 -> T2
and an argument e : T1
then f e : T2

A -> B -> C

same as:

A -> (B -> C)

Rule for type-checking functions

add : int -> int -> int

3 + 4 : int

add (3 + 4) : int -> int

(add (3 + 4)) 7 : int

General Rule:

Example:

44

If a function f : T1 -> T2
and an argument e : T1
then f e : T2

A -> B -> C

same as:

A -> (B -> C)

Rule for type-checking functions

add : int -> int -> int

3 + 4 : int

add (3 + 4) : int -> int

add (3 + 4) 7 : int

General Rule:

Example:

45

If a function f : T1 -> T2
and an argument e : T1
then f e : T2

A -> B -> C

same as:

A -> (B -> C)

Rule for type-checking functions

let munge (b:bool) (x:int) : ?? =

if not b then

string_of_int x

else

“hello”

;;

let y = 17;;

Example:

munge (y > 17) : ??

munge

f :

true

??

(f (munge false 3)) : ??

munge

g :

true

??

(g munge) : ??

46

Rule for type-checking functions

let munge (b:bool) (x:int) : ?? =

if not b then

string_of_int x

else

“hello”

;;

let y = 17;;

Example:

munge (y > 17) : ??

munge

f :

true

??

(f (munge false 3)) : ??

munge

g :

true

??

(g munge) : ??

46

string

munge : bool -> int -> string

Rule for type-checking functions

let munge (b:bool) (x:int) : ?? =

if not b then

string_of_int x

else

“hello”

;;

let y = 17;;

Example:

munge (y > 17) : ??

munge true (f (munge false 3)) : ??

f : string -> int

munge true (g munge) : ??

g : (bool -> int -> string) -> int

47

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

f a1 : B -> C -> D -> E -> F (if a1 : A)

f a1 a2 : C -> D -> E -> F (if a2 : B)

f a1 a2 a3 : D -> E -> F (if a3 : C)

f a1 a2 a3 a4 a5 : F (if a4 : D and a5 : E)

48

OUR FIRST* COMPLEX DATA STRUCTURE!
THE TUPLE

* it is really our second complex data structure since functions
are data structures too!

49

• A tuple is a fixed, finite, ordered collection of expressions

• Some examples with their types:

Tuples

(1, 2) : int * int

(“hello”, 7 + 3, true) : string * int * bool

(‘a’, (“hello”, “goodbye”)) : char * (string * string)

50

• To use a tuple, we extract its components

• General case:

Tuples

let (id1, id2, …, idn) = e1 in e2

• An example:

let (x,y) = (2,4) in x + x + y

51

• To use a tuple, we extract its components

• General case:

Tuples

let (id1, id2, …, idn) = e1 in e2

• An example:

let (x,y) = (2,4) in x + x + y

–> 2 + 2 + 4
substitute!

52

• To use a tuple, we extract its components

• General case:

Tuples

let (id1, id2, …, idn) = e1 in e2

• An example:

let (x,y) = (2,4) in x + x + y

–> 2 + 2 + 4

–> 8

53

Rules for Typing Tuples
54

if e1 : t1 and e2 : t2
then (e1, e2) : t1 * t2

Rules for Typing Tuples

let (x1,x2) = e1 in

e2

if e1 : t1 * t2 then
x1 : t1 and x2 : t2
inside the expression e2

overall expression
takes on the type of e2

55

if e1 : t1 and e2 : t2
then (e1, e2) : t1 * t2

Distance between two points

c2 = a2 + b2 (x1, y1)

a

b
c

(x2, y2)

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

56

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)

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)

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

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

6. Clean up by identifying repeated patterns

• define and reuse helper functions

• your code should be elegant and easy to read

59

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

6. 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

Distance between two points

type point = float * float

a type abbreviation (x1, y1)

(x2, y2)

a

b
c

61

c2 = a2 + b2

Distance between two points

type point = float * float

let distance (p1:point) (p2:point) : float =

write down function name
argument names and types

(x1, y1)

(x2, y2)

a

b
c

62

c2 = a2 + b2

Distance between two points

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 =

(x1, y1)

(x2, y2)

a

b
cexamples

63

c2 = a2 + b2

Distance between two points

type point = float * float

let distance (p1:point) (p2:point) : float =

let (x1,y1) = p1 in

let (x2,y2) = p2 in

deconstruct
function inputs

(x1, y1)

(x2, y2)

a

b
c

64

c2 = a2 + b2

Distance between two points

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

(x1, y1)

(x2, y2)

a

b
c

65

c2 = a2 + b2

Distance between two points

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

(x1, y1)

(x2, y2)

a

b
c

66

c2 = a2 + b2

Distance between two points

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

let pt1 = (2.0,3.0)

let pt2 = (0.0,1.0)

let dist1

2

= distance pt1 pt2

testing

(x1, y1)

(x2, y2)

a

b
c

67

c2 = a2 + b2

MORE TUPLES

68

Tuples

• Here’s a tuple with 2 fields:

(4.0, 5.0) : float * float

69

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

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

• Here’s a tuple with 4 fields:

(4.0, 5, “hello”, 55) : float * int * string * int

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

• Here’s a tuple with 0 fields:

() : unit

72

SUMMARY:
BASIC FUNCTIONAL PROGRAMMING

76

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

77