CS代考 CS 314: Principles of Programming Languages

CS 314: Principles of Programming Languages
OCaml Data Types
CS314 Spring 2022 1

OCaml Data
• So far, we’ve seen the following kinds of data
• Basic types (int, float, char, string)
Ø One kind of data structure
Ø A list is either [ ] or h::t, deconstructed with pattern matching
• Tuples and Records
Ø Let you collect data together in fixed-size pieces
• Functions
• How can we build other data structures?
• Building everything from lists and tuples is awkward
CS314 Spring 2022 2

User Defined Types
type can be used to create new names for types
• Like typedef in C – a name might be more useful for
communicating intent than just the type structure
# type mylist = int*(int list);;
type mylist = int * int list
# let empty:mylist = (0,[]);;
val empty : mylist = (0, [])
Annotation required to tell type inference you want mylist, not int*int list
# let add x ((n,xs):mylist):mylist = (n+1,x::xs);;
val add : int -> mylist -> mylist =
# let length ((n,_):mylist) = n;;
val length : mylist -> int =
# let x = add 1 (add 2 empty);;
val x : mylist = (2, [1; 2])
CS314 Spring 2022 3

(User-Defined) Variants
type coin = Heads | Tails
let flip x = match x with
Heads -> Tails
| Tails -> Heads
let rec count_heads x = match x with
| (Heads::x’) -> 1 + count_heads x’
| (_::x’) -> count_heads x’
CS314 Spring 2022 4
In simplest form: Like a C enum
Basic pattern
resembles C
Combined list and variant patterns possible

Constructing and Destructing Variants
•type t = C1 | … | Cn
• theCiarecalledconstructors
Ø Must begin with a capital letter
• Evaluation
• A constructor Ci is already a value
• Destructingavaluevoftypetisdonebypattern
matching on v ; the patterns are the constructors Ci • Type Checking
• Ci : t (for each Ci in t’s definition)
CS314 Spring 2022 5

Data Types: Variants with Data
• We can define variants that “carry data” too
• Not just a constructor, but a constructor plus values
type shape =
Rect of float * float (* width*length *)
| Circle of float (* radius *)
• Rect and Circle are constructors • whereashapeiseitheraRect(w,l)
Ø for any floats w and l • oraCircler
Ø for any float r
CS314 Spring 2022 6

Data Types (cont.)
let area s = match s with
Rect (w, l) -> w *. l |Circler->r *.r*.3.14
area (Rect (3.0, 4.0));; (* 12.0 *) area (Circle 3.0);; (* 28.26 *)
• Use pattern matching to deconstruct values • Can bind pattern values to data parts
• Data types are aka algebraic data types and tagged unions
CS314 Spring 2022 7

Data Types (cont.)
type shape =
Rect of float * float (* width*length *)
| Circle of float (* radius *) let lst = [Rect (3.0, 4.0) ; Circle 3.0]
• What’s the type of lst? • shape list
• What’s the type of lst’s first element? • shape
CS314 Spring 2022 8

Variation: Shapes in Java
public interface Shape { public double area();
Compare this to OCaml
class Rect implements Shape { private double width, length;
Rect (double w, double l) { this.width = w; this.length = l;
double area() {
return width * length;
class Circle implements Shape { private double rad;
Circle (double r) {
this.rad = r;
double area() {
return rad * rad * 3.14159;
CS314 Spring 2022 9

Option Type
type optional_int = None
| Some of int
let divide x y =
if y != 0 then Some (x/y) else None
let string_of_opt o = match o with
Some i -> string_of_int i | None -> “nothing”
let p = divide 1 0;; print_string
(string_of_opt p);;
(* prints “nothing” *)
let q = divide 1 1;; print_string
(string_of_opt q);;
(* prints “1” *)
• Comparing to Java: None is like null, while Some i is like an Integer(i) object
CS314 Spring 2022 10

Polymorphic Option Type
• A Polymorphic version of option type can work with any kind of data
• As int option, char option, etc…
type ‘a option =
Some of ‘a
let opthd l =
match l with
[] -> None
| x::_ -> Some x
In fact, this option type is built into OCaml
letp=opthd[];; (*p=None*) let q = opthd [1;2];; (* q = Some 1 *) let r = opthd [“a”];; (* r = Some “a” *)
CS314 Spring 2022 11
Polymorphic parameter: like Option in Java

type foo = (int * (string list)) list
Which one of the following could match foo?
A. [(3, “foo”, “bar”)]
B. [(7, [“foo”; “bar”])] C. [(5, [“foo”, “bar”])] D. [(9, [(“foo”, “bar”)])]
CS314 Spring 2022 12

type foo = (int * (string list)) list
Which one of the following could match foo?
A. [(3, “foo”, “bar”)]
B. [(7, [“foo”; “bar”])]
C. [(5, [“foo”, “bar”])] D. [(9, [(“foo”, “bar”)])]
CS314 Spring 2022 13

Quiz 2: What does this evaluate to?
type num = Int of int | Float of float;; let plus a b =
match a, b with
| Int i, Int j -> Int (i+j)
| Float i, Float j -> Float (i +. j)
| Float i, Int j -> Float (i +. float_of_int j)
plus (Float 2.0) (Int 2);;
C. Float 4.0
D. Type Error
CS314 Spring 2022 14

Quiz 3: What does this evaluate to?
let foo f = match f with None -> 42.0
| Some n -> n +. 42.0 ;;
C. Some 45.3 D. Error
CS314 Spring 2022 16

Quiz 3: What does this evaluate to?
let foo f = match f with None -> 42.0
| Some n -> n +. 42.0 ;;
foo 3.3;; foo (Some 3.3)
C. Some 45.3 D. Error
CS314 Spring 2022 17

Recursive Data Types
• We can build up lists with recursive variant types
type ‘a mylist =
| Cons of ‘a * ‘a mylist
let rec len l = match l with | Nil -> 0
| Cons (_, t) -> 1 + (len t)
len (Cons (1, Cons (2, Cons (3, Nil))))
(* evaluates to 3 *)
• Won’t have nice [1; 2; 3] syntax for this kind of list
CS314 Spring 2022 18

Variants (full definition)
•type t = C1 [of t1] | … | Cn [of tn] • theCiarecalledconstructors
Ø Must begin with a capital letter; may include associated data – notated with brackets [] to indicate it’s optional
• Type Checking •Ci[vi]:t[ifvihas typeti]
CS314 Spring 2022 19

Exercise: A Binary Tree Data Type
• Write type bin_tree for binary trees over int • Trees should be ordered (binary search tree)
• Implement the following
empty : bin_tree
is_empty : bin_tree -> bool
member : int -> bin_tree -> bool insert : int -> bin_tree -> bin_tree remove: int -> bin_tree -> bin_tree equal : bin_tree -> bin_tree -> bool fold : (int -> ‘a -> ‘a) -> bin_tree
-> ‘a -> ‘a
max : bin_tree -> int
CS314 Spring 2022 21

Exercise: A Binary Tree Data Type
type bin_tree =
| Leaf (* like Nil in mylist *)
| Node of int * int bin_tree * int bin_tree
Node(50, ——> Node (30,
Node (20, Leaf, Leaf),
Node (40, Leaf, Leaf)), Node (80,
CS314 Spring 2022
Leaf, Leaf))

Exercise: A Binary Tree Data Type
type bin_tree =
| Node of int * int bin_tree * int bin_tree
(* type: int -> bin_tree -> bin_tree *) let rec insert x t =
match t with
| Leaf -> Node (x, Leaf, Leaf) | Node (v, t1, t2) ->
CS314 Spring 2022
= v then t
if x < v then Node (v, insert x t1, t2) (* x > v *)
Node (v, t1, insert x t2)

Exercise: A Binary Tree Data Type
let tree =
Node (20, Leaf, Leaf),
Node (40, Leaf, Leaf)), Node (80,
insert 65 tree
insert 65 —————>
20 40 20 40 65 CS314 Spring 2022

Exercise: A Binary Tree Data Type
let rec remove x t = match t with
| Leaf -> Leaf
| Node (v, t1, t2) ->
\ remove 70
if x = v then match t with
| Node (_, Leaf, t2) -> t2
70 t2 —————> /\\/\
30 20 40 80 20 40
CS314 Spring 2022

Exercise: A Binary Tree Data Type
let rec remove x t = match t with
| Leaf -> Leaf
| Node (v, t1, t2) ->
if x = v then match t with
CS314 Spring 2022
| Node (_, Leaf, t2) -> t2 | Node (_, t1, Leaf) -> t1

Exercise: A Binary Tree Data Type
let rec remove x t = match t with
| Leaf -> Leaf
| Node (v, t1, t2) ->
if x = v then match t with
| Node (_, Leaf, t2) -> t2 | Node (_, t1, Leaf) -> t1 | Node (_, t1, t2) ->
CS314Spring2022
remove 50 /
let newv = max t1 in
let newt1 = remove newv t1 in
50 Node (newv, newt1, t2)
/ \ newv 20 40
—————> 30 /

Exercise: A Binary Tree Data Type
let rec remove x t = match t with
| Leaf -> Leaf
| Node (v, t1, t2) ->
if x = v then match t with
| Node (_, Leaf, t2) -> t2 | Node (_, t1, Leaf) -> t1 | Node (_, t1, t2) ->
let newv = max t1 in
let newt1 = remove newv t1 in Node (newv, newt1, t2)
else if x < v then Node (v, remove x t1, t2) else (* x > v *)
Node (v, t1, remove x t2)
CS314 Spring 2022

OCaml Exceptions
exception My_exception of int let f n =
if n > 0 then
raise (My_exception n)
raise (Failure “foo”)
let bar n =
with My_exception n ->
Printf.printf “Caught %d\n” n | Failure s ->
Printf.printf “Caught %s\n” s
CS314 Spring 2022 30

Exceptions (cont.)
• Exceptions are declared with exception
• Exceptions may take arguments • Just like type constructors
• May also have no arguments
• Catch exceptions with try…with…
• Pattern-matching can be used in with
• If an exception is uncaught
Ø Current function exits immediately
Ø Control transfers up the call chain
Ø Until the exception is caught, or until it reaches the top level
CS314 Spring 2022 31

OCaml Exceptions (cont.)
• failwith:Raise exception Failure with the given string.
let div x y =
if y = 0 then failwith “divide by zero” else x/y;;
let div x y =
if y = 0 then raise (Failure “divide by zero”) else x/y;;
CS314 Spring 2022 33

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

Related Posts