[SOLVED] 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

Copyright By Assignmentchef assignmentchef

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

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

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!
https://www.fortinet.com/blog/threat-research/microsoft-kernel-integer-overflow-vulnerability
Int32.max_int

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!
https://www.fortinet.com/blog/threat-research/microsoft-kernel-integer-overflow-vulnerability
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
(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
(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?
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

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

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
[1,2,3] [(1,2,3)]
Two basic constructors of a list

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
[1,2,3] [(1,2,3)] (1,2,3)::[]
Two basic constructors of a list

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
[1,2,3] [(1,2,3)] (1,2,3)::[]
: (int * int * int) list 45
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
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
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
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
{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)
Type names are all in lower case

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)
Type names are all in lower case
Custom data types (constructors should start with a capital letter; true/false are exceptions)

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

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 int * int * int
Disjoint Unions
Constructors have 0 arguments

ADT syntax
type mybool = True | False
type major = Comp | Math | Physics
type color = Red | Green | RGB of
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}
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
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
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
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?

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?

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?
This works, but not very elegant

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?
This works, but not very elegant

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?
This works, but not very elegant Seems better, but how to implement get_r/g/b??

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

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
match e with
| p1 | p2 | p3 -> e1 |_ ->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
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

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 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: assignmentchef QQ: 1823890830 Email: [email protected]