COMP302: Programming Languages and Paradigms
Prof. (Sec 01) Francisco Ferreira (Sec 02)
School of Computer Science Mc
Copyright By PowCoder代写 加微信 powcoder
Week 2-1, Fall 2017
Let’s talk about lists!
COMP302: Programming Languages and Paradigms 2 / 16
Bad Programming Practice: Keeping it Old-Style
(* head: ’a list -> ’a *)
let head (h::t) = h
(* tail: ’a list -> ’a list *)
let tail l = match l with | [] -> []
| h::t -> t
(* Destructor style *)
let rec app (l1, l2) = if l1 = [] then l2
head(l1)::(app (tail(l1), l2))
1 2 3 4 5 6 7 8 9
10 11 12 13
Why do you think this is bad style?
COMP302: Programming Languages and Paradigms
Task: Reverse a list
COMP302: Programming Languages and Paradigms 4 / 16
Task: Reverse a list
Write a function rev which given a list l of type ’a list it returns its reverse.
Example: rev [1, 2, 3, 4] ===> [4, 3, 2, 1] What is the type of rev?
COMP302: Programming Languages and Paradigms 4 / 16
Task: Reverse a list
Write a function rev which given a list l of type ’a list it returns its reverse.
Example: rev [1, 2, 3, 4] ===> [4, 3, 2, 1]
(* rev : ’a list -> ’a list *)
let rec rev l = match l with | [] -> []
| x::l -> (rev l) @ [x]
COMP302: Programming Languages and Paradigms
Task: Reverse a list
Write a function rev which given a list l of type ’a list it returns its reverse.
Example: rev [1, 2, 3, 4] ===> [4, 3, 2, 1]
(* rev : ’a list -> ’a list *)
let rec rev l = match l with | [] -> []
| x::l -> (rev l) @ [x]
Is this a good program?
COMP302: Programming Languages and Paradigms
Task: Reverse a list
Write a function rev which given a list l of type ’a list it returns its reverse.
Example: rev [1, 2, 3, 4] ===> [4, 3, 2, 1]
(* rev : ’a list -> ’a list *)
let rec rev l = match l with | [] -> []
| x::l -> (rev l) @ [x]
Is this a good program? Tail-Recursion to the rescue!
COMP302: Programming Languages and Paradigms
Practice Problem 1
Write a function merge:’a list -> ’a list -> ’a list which given two ordered lists l1 and l2, both of type ’a list, it returns the sorted combination of both lists.
COMP302: Programming Languages and Paradigms 6 / 16
Practice Problem 2
Write a function split:’a list -> ’a list * ’a list which given a list l it splits it into two sublists.
split[1,2,3,4] =⇒ ([1,3],[2,4]) split [1, 2, 3] =⇒ ([1, 3] , [2])
COMP302: Programming Languages and Paradigms 7 / 16
Practice Problem 3
Write a function zip:’a list * ’a list -> ’a list which given two lists l1 and l2, zips them together
zip([1,3],[2,4]) =⇒ [1,2,3,4] zip([1,3],[2]) =⇒ [1,2,3]
COMP302: Programming Languages and Paradigms 8 / 16
Practice Problem 3
Write a function zip:’a list * ’a list -> ’a list which given two lists l1 and l2, zips them together
zip([1,3],[2,4]) =⇒ [1,2,3,4] zip([1,3],[2]) =⇒ [1,2,3]
For all l, zip (split l) = l.
COMP302: Programming Languages and Paradigms
Functional Tidbit: Words of Wisdom
“On theories such as these we cannot rely. Proof we need. Proof!”
COMP302: Programming Languages and Paradigms 9 / 16
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com