程序代写 COMP 302: Programming Languages and Paradigms

COMP 302: Programming Languages and Paradigms
Week 2: Data Types and Pattern Matching Prof. Xujie Si

Basic Values and Types

What is the simplest value and data type?

Basic Values and Types
What is the simplest value and data type?

Basic Values and Types
What is the simplest value and data type? A slightly more informative data type?

Basic Values and Types
What is the simplest value and data type? A slightly more informative data type?
true : bool
false : bool

Basic Values and Types
What is the simplest value and data type? A slightly more informative data type?
More informative data types?
true : bool
false : bool

Basic Values and Types
What is the simplest value and data type? A slightly more informative data type?
More informative data types?
true : bool
false : bool
4.2 : float
“hello” : string

Basic Values and Types
What is the simplest value and data type? A slightly more informative data type?
More informative data types?
true : bool
false : bool
4.2 : float
“hello” : string
2147483647 : int
Be careful about integer overflow!
Int32.max_int

Built-in compound data types
(“COMP”, 302) : string * int Tuples (1821, 3, 31) : int * int * int

Built-in compound data types
(“COMP”, 302) : string * int Tuples (1821, 3, 31) : int * int * int
How about “1-tuple” and “0-tuple”?

Built-in compound data types
(42) : int
(“COMP”, 302) : string * int
(1821, 3, 31) : int * int * int
How about “1-tuple” and “0-tuple”?

Built-in compound data types
(42) : int
(“COMP”, 302) : string * int
(1821, 3, 31) : int * int * int
(1821, (3, 31)) :
How about “1-tuple” and “0-tuple”?

Built-in compound data types
(42) : int
(“COMP”, 302) : string * int
(1821, 3, 31) : int * int * int
(1821, (3, 31)) : int * (int * int)
How about “1-tuple” and “0-tuple”?

Built-in compound data types
(42) : int
[1; 2; 3] : int list
[‘a’; ‘b’; ‘c’] : char list
(“COMP”, 302) : string * int
(1821, 3, 31) : int * int * int
(1821, (3, 31)) : int * (int * int)
How about “1-tuple” and “0-tuple”?

Built-in compound data types
(42) : int
[1; 2; 3] : int list
[‘a’; ‘b’; ‘c’] : char list
Is an integer a list of digits?
Is a string a list of characters?
(“COMP”, 302) : string * int
(1821, 3, 31) : int * int * int
(1821, (3, 31)) : int * (int * int)
How about “1-tuple” and “0-tuple”?
Note that “,” is reserved for tuples, list separator is “;”

Built-in compound data types
(42) : int
[1; 2; 3] : int list
[‘a’; ‘b’; ‘c’] : char list
Is an integer a list of digits?
Is a string a list of characters?
(“COMP”, 302) : string * int
(1821, 3, 31) : int * int * int
(1821, (3, 31)) : int * (int * int)
How about “1-tuple” and “0-tuple”?
Not a (value) constructor but a syntax sugar!!
Note that “,” is reserved for tuples, list separator is “;”

What is a (value) constructor?
• Something used to construct values () : unit
true : bool
false : bool

What is a (value) constructor?
• Something used to construct values : unit
: bool : bool
constructors
true false

What is a (value) constructor?
• Something used to construct values
: unit : bool
: bool constructors
(“COMP”, 302) : string * int
true false

What is a (value) constructor?
• Something used to construct values
: unit : bool
: bool constructors
(“COMP”, 302) : string * int
: type1 * type2
“2-tuple” Constructor
true false

Syntax Sugar
Something not fundamental but making the language “sweeter” for human use
≡ // assignment in C/C++/Java/python etc. [1;2;3] ≡ 1::2::3::[]

Syntax Sugar
Something not fundamental but making the language “sweeter” for human use
Syntax sugar
≡ // assignment in C/C++/Java/python etc. ≡ 1::2::3::[]

Syntax Sugar
Something not fundamental but making the language “sweeter” for human use
Syntax sugar
After “desugaring”
// assignment in C/C++/Java/python etc.
1 :: 2 :: 3 :: []

Syntax Sugar
Something not fundamental but making the language “sweeter” for human use
Syntax sugar
After “desugaring”
// assignment in C/C++/Java/python etc.
≡ 1 :: (2 :: (3 :: []))
1 :: 2 :: 3 :: []

Syntax Sugar
Something not fundamental but making the language “sweeter” for human use
// assignment in C/C++/Java/python etc.
≡ 1 :: (2 :: (3 :: []))
1 :: 2 :: 3 :: []
Syntax sugar
After “desugaring”
Two basic constructors of a list

Algebraic Data Types

Algebraic Data Types
Product Types
(one constructor with multiple parameters)

Algebraic Data Types
Product Types
(one constructor with multiple parameters)
Sum Types (multiple constructors)

Algebraic Data Types
Product Types
(one constructor with multiple parameters)
(true, 1, 0.5) : bool * int * float
Sum Types (multiple constructors)

Algebraic Data Types
Product Types
(one constructor with multiple parameters)
(true, 1, 0.5) : bool * int * float
(“COMP”, 302) : string * int
Sum Types (multiple constructors)

Algebraic Data Types
Product Types
(one constructor with multiple parameters)
(true, 1, 0.5) : bool * int * float
(“COMP”, 302) : string * int
{dept=“comp”; num=302} : course_info
true : bool
false : bool
[] : int list
1 :: [] : int list
Red : color
Green : color
RGB (20,30,40) : color
Sum Types (multiple constructors)

Algebraic Data Types
Product Types
(one constructor with multiple parameters)
(true, 1, 0.5) : bool * int * float
(“COMP”, 302) : string * int
Sum Types (multiple constructors)
{dept=“comp”; num=302} : course_info
true : bool
false : bool
[] : int list
1 :: [] : int list
Red : color
Green : color
RGB (20,30,40) : color
[] : ’a list
Type names are all in lower case
Custom data types (constructors should start with a capital letter; true/false are exceptions)

ADT syntax

ADT syntax
type mybool = True | False

ADT syntax
type mybool = True | False
type major = Comp | Math | Physics

ADT syntax
type mybool = True | False
type major = Comp | Math | Physics
• Disjoint Unions
• Constructors have 0 arguments

ADT syntax
type mybool = True | False
type major = Comp | Math | Physics
type color = Red | Green | RGB of
type course_info = {depth : string; num : int}
• Disjoint Unions
• Constructors have 0 arguments
int * int * int

ADT syntax
type mybool = True | False
type major = Comp | Math | Physics
type color = Red | Green | RGB of
type course_info = {depth : string; num : int}
What is the difference between a record and a tuple?
• Disjoint Unions
• Constructors have 0 arguments
int * int * int

ADT syntax
type mybool = True | False
type major = Comp | Math | Physics
type color = Red | Green | RGB of
type course_info = {depth : string; num : int} type nat = Zero | Suc of nat
What is the difference between a record and a tuple?
• Disjoint Unions
• Constructors have 0 arguments
int * int * int

ADT syntax
type mybool = True | False
type major = Comp | Math | Physics
type color = Red | Green | RGB of
type course_info = {depth : string; num : int} type nat = Zero | Suc of
How do we define a custom data type of list?
What is the difference between a record and a tuple?
• Disjoint Unions
• Constructors have 0 arguments
int * int * int
Can be recursive!!

ADT syntax
type mybool = True | False
type major = Comp | Math | Physics
type color = Red | Green | RGB of
type course_info = {depth : string; num : int} type nat = Zero | Suc of
What is the difference between a record and a tuple?
How do we define a custom data type of list?
type ilist = Empty | Cons of int * ilist
• Disjoint Unions
• Constructors have 0 arguments
int * int * int
Can be recursive!!

ADT syntax
type mybool = True | False
type major = Comp | Math | Physics
type color = Red | Green | RGB of
type course_info = {depth : string; num : int} type nat = Zero | Suc of
What is the difference between a record and a tuple?
How do we define a custom data type of list?
type ilist = Empty | Cons of int * ilist
type ‘a mylist = Empty | Cons of ‘a * ‘a mylist
• Disjoint Unions
• Constructors have 0 arguments
int * int * int
Can be recursive!!

A simple exercise
type mybool = True | False
type color = Red | Green | RGB of int * int * int
(* test whether a color is red or not *)
let is_red (x:color) : mybool = ???

A simple exercise
type mybool = True | False
type color = Red | Green | RGB of int * int * int
(* test whether a color is red or not *)
let is_red (x:color) : mybool = ???
How to examine the value of x?

Pattern Matching
(Almost) the only way of looking into values of an ADT type

Pattern Matching
(Almost) the only way of looking into values of an ADT type
match e with | p1 -> e1 | p2 -> e2 | p3 -> e3 |_ ->e4

Pattern Matching
(Almost) the only way of looking into values of an ADT type
match e with | p1 -> e1 | p2 -> e2 | p3 -> e3 |_ ->e4
This wildcard (_) will match value

Pattern Matching
(Almost) the only way of looking into values of an ADT type
match e with | p1 -> e1 | p2 -> e2 | p3 -> e3 |_ ->e4
match e with
| p1 | p2 | p3 -> e1 |_ ->e4
OCaml will check whether the pattern matching is exhaustive; if not, a warning will be issued.
Why is this important?
This wildcard (_) will match value
We can match more than one case at a time
let is_red (x:color) = match x with | Red | RGB (c, 0, 0) -> True
| _ -> False

Pattern Matching
(Almost) the only way of looking into values of an ADT type
match e with | p1 -> e1 | p2 -> e2 | p3 -> e3 |_ ->e4
OCaml will check whether the pattern matching is exhaustive; if not, a warning will be issued.
Why is this important?
This wildcard (_) will match value
We can match more than one case at a time
match e with
| p1 | p2 | p3 -> e1 |_ ->e4
let is_red (x:color) = match x with | Red | RGB (c, 0, 0) -> True
| _ -> False
let is_red = function
| Red | RGB (c, 0, 0) -> true | _ -> false

Pattern Matching
(Almost) the only way of looking into values of an ADT type
match e with | p1 -> e1 | p2 -> e2 | p3 -> e3 |_ ->e4
OCaml will check whether the pattern matching is exhaustive; if not, a warning will be issued.
Why is this important?
This wildcard (_) will match value
We can match more than one case at a time
function keyword can do matching as well
match e with
| p1 | p2 | p3 -> e1 |_ ->e4
let is_red (x:color) = match x with | Red | RGB (c, 0, 0) -> True
| _ -> False
let is_red = function
| Red | RGB (c, 0, 0) -> true | _ -> false

Value comparison

Value comparison
• Values of different types cannot be compared
• Unless some specific compare function is explicitly defined
• Values of the same type are (by default) ordered according to the definition order of constructors
• Equality is a bit tricky
• “Logically” equal (=), whether two values are the same
• “Physically” equal (==), usually faster, directly check underlying physical address (rule of thumb: use this only if you know what you are doing!!)

Value comparison
• Values of different types cannot be compared
• Unless some specific compare function is explicitl

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts