Yao Lirong's Blog

Advanced Data Types

CS3110
2020/02/04

From Textbook: Advanced Data Types

Algebraic Data Types

以前我们的 variants 比较像 enum，但是现在我们更像一个abstract class

1
2
3
4
5
6
7
8
9
10
11
12
13
(*definition*)
type t = C1 | C2 of t2| ... | Cn (*of tn*)
(* t: 'a * 'a * ... *)

(*expression*)
C e
---or---
C
(* e: (e1:'a, e2:'a, ...) *)

(*pattern matching*)
C p
(* p: (e1:'a, e2:'a, ...) *)

examples: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
type point = float * float 

type shape =
  | Point  of point
  | Circle of point * float (* center and radius *)
  | Rect   of point * point (* lower-left and 
                               upper-right corners *)

let area = function
  | Point _ -> 0.0
  | Circle (_,r) -> pi *. (r ** 2.0)
  | Rect ((x1,y1),(x2,y2)) ->
      let w = x2 -. x1 in
      let h = y2 -. y1 in
        w *. h

type string_or_int =
| String of string
| Int of int

type string_or_int_list = string_or_int list

let rec sum : string_or_int list -> int = function
  | [] -> 0
  | (String s)::t -> int_of_string s + sum t
  | (Int i)::t -> i + sum t

let three = sum [String "1"; Int 2]

When do we need [],(),{} | of?

1
2
type node = {value:int; next:mylist}
and mylist = Nil | Node of node
  • []: list
  • (): Constructor of a tuple
  • {}: Constructor of a record
  • |: delineate different variants inside a type
  • of: defining the construction of an algebraic type

Recursive Variants

1
2
3
4
5
6
7
8
9
10
type intlist = Nil | Cons of int * intlist

type 'a tree = 
  | Leaf 
  | Node of 'a node
and 'a node = { 
  value: 'a; 
  left:  'a tree; 
  right: 'a tree
}

Parametrized Variants

No matter what kind of types we define, either a variant, a record, or a tuple. We need the type parameter 'a or ('a,'b) when we define it. 

1
2
3
4
5
6
(* [Option] makes it safer to return nothing*)
type 'a option = None | Some of 'a

type 'a mylist = Nil | Cons of 'a * 'a mylist
type ('a,'b) pair = {first: 'a; second: 'b}
type ('a,'b) test = 'a * 'b

Similarly, when you want to declare a variable that has a parametrized type, you also need to give the type parameter.

1
2
3
type 'a tree = Leaf of 'a | Node of ('a * 'a tree * 'a tree)
let x:'a tree = Leaf 5
let x:int tree = Leaf 5

If you do let x:tree = Leaf 5, the compiler won’t know what type you are talking about.

Polymorphic Variants

They would be better off with the name “anonymous variants,” because you want to use them when these variants are only used in this specific function and not anywhere else.

The constructor of polymorphic variants start with a “ ` “

1
2
3
4
5
6
7
8
9
10
11
12
(* note: no type definition *)

let f = function
  | 0 -> `Infinity
  | 1 -> `Finite 1
  | n -> `Finite (-n)
  
val f : int -> [> `Finite of int | `Infinity ]

let lst = [`Pos 5; `Zero; `Neg (~-4); `Pos 3];;
val lst : [> `Neg of int | `Pos of int | `Zero ] list =
  [`Pos 5; `Zero; `Neg (-4); `Pos 3]

Pattern Matching

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
type 'a tree = 
  | Leaf 
  | Node of 'a node

and 'a node = { 
  value: 'a; 
  left:  'a tree; 
  right: 'a tree
}

(* [mem x t] returns [true] if and only if [x] is a value at some
 * node in tree [t]. 
 *)
let rec mem x = function
  | Leaf -> false
  | Node {value; left; right} -> value = x || mem x left || mem x right

Exceptions

The Basics

1
2
3
4
5
6
7
8
9
10
(*Definition: it is just a special kind of "type"*)
exception E of t


(*Call an Exception*)
raise e

(*syntactic sugar*)
failwith "Not Good"
raise (Failure ("Not Good"))

Pattern Matching

The following code says: try evaluating e. If it produces an exception packet, use the exception patterns from the original match expression to handle that packet. If it doesn’t produce an exception packet but instead produces a normal value, use the non-exception patterns from the original match expression to match that value.

1
2
3
4
5
6
7
8
9
match 
  try e with
    | q1 -> e1
    | ...
    | qn -> en
with
  | r1 -> e1
  | ...
  | rm -> em

Author：Yao Lirong

Link：https://yao-lirong.github.io/blog/2020-02-04-Advanced-Data-Types/

Publish date：February 4th 2020, 12:00:00 am

Update date：June 9th 2022, 3:27:38 am

License：本文采用 Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) 进行许可

CATALOG
  1. 1. Algebraic Data Types
    1. 1.1. Recursive Variants
    2. 1.2. Parametrized Variants
    3. 1.3. Polymorphic Variants
    4. 1.4. Pattern Matching
  2. 2. Exceptions
    1. 2.1. The Basics
    2. 2.2. Pattern Matching
Total : 66
2023
2022
2021
2020
2019
NOI CS2112 Logistics Cornell Review CS3110 Manual Journal Tsinghua Book