COMP302: Programming Languages and Paradigms
Prof. (Sec 01) Francisco Ferreira (Sec 02)
School of Computer Science Mc
Copyright By PowCoder代写 加微信 powcoder
Week 3-2, Fall 2017
Can’t see the forest for the trees
COMP302: Programming Languages and Paradigms 2 / 1
Inductive definition of a binary tree
• The empty binary tree Empty is a binary tree
• Ifl andr arebinarytreesandv isavalueoftype’a
then Node(v, l, r) is a binary tree. • Nothing else is a binary tree.
COMP302: Programming Languages and Paradigms 3 / 1
Inductive definition of a binary tree
• The empty binary tree Empty is a binary tree
• Ifl andr arebinarytreesandv isavalueoftype’a
then Node(v, l, r) is a binary tree. • Nothing else is a binary tree.
How to define a recursive data type for trees in OCaml?
COMP302: Programming Languages and Paradigms
Inductive definition of a binary tree
• The empty binary tree Empty is a binary tree
• Ifl andr arebinarytreesandv isavalueoftype’a
then Node(v, l, r) is a binary tree. • Nothing else is a binary tree.
How to define a recursive data type for trees in OCaml?
type ’a tree = Empty
| Node of ’a * ’a tree * ’a tree
COMP302: Programming Languages and Paradigms
Inductive definition of a binary tree
• The empty binary tree Empty is a binary tree
• Ifl andr arebinarytreesandv isavalueoftype’a
then Node(v, l, r) is a binary tree. • Nothing else is a binary tree.
How to define a recursive data type for trees in OCaml?
type ’a tree = Empty
| Node of ’a * ’a tree * ’a tree
Let’s do some programming with trees!
COMP302: Programming Languages and Paradigms
How to prove it?
Step 2: How to reason inductively about trees?
COMP302: Programming Languages and Paradigms 4 / 1
How to prove it?
Step 2: How to reason inductively about trees? Analyze their structure!
COMP302: Programming Languages and Paradigms 4 / 1
How to prove it?
Step 2: How to reason inductively about trees? Analyze their structure!
The recipe …
To prove a property P(t) holds about a binary tree t
Base Case:
Step Case:
t = Empty P(Empty) holds
t = Node(x, l, r)
Assume the property P holds for trees smaller than t.
Show the property P holds for the tree t.
P(Node(x, l, r) holds
COMP302: Programming Languages and Paradigms 4 / 1
Let’s prove something!
1 2 3 4 5 6
1 2 3 4 5 6
let rec insert ((x,d) as e) t = match t with
| Empty -> Node(e, Empty , Empty) | Node ((y,d’), l, r) ->
ifx=ythen Node(e,l,r)
else (if x < y then Node((y,d’), insert e l, r)
else Node((y,d’), l, insert e r))
Theorem: For all trees t, keys x, and data dx, lookup x (insert (x, dx) t) =⇒∗ Some dx
let rec lookup x t = match t with | Empty -> None
| Node ((y,d), l, r) ->
if x = y then Some(d)
else (if x < y then lookup x l else lookup x r)
COMP302: Programming Languages and Paradigms
Remember the slice of cake?
Give an OCaml data type definition for cake!
COMP302: Programming Languages and Paradigms 6 / 1
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com