COMP302: Programming Languages and Paradigms
Prof. (Sec 01) Francisco Ferreira (Sec 02)
School of Computer Science Mc
Copyright By PowCoder代写 加微信 powcoder
Week 3-3, Fall 2017
Functional Tidbit: Words of Wisdom
“Higher-order functions are super cool!” – (TA for COMP 302)
COMP302: Programming Languages and Paradigms 2 / 15
Why are higher-order functions cool?
Higher-order functions allow us to abstract over com- mon functionality.
COMP302: Programming Languages and Paradigms 3 / 15
Why are higher-order functions cool?
Higher-order functions allow us to abstract over com- mon functionality.
• Programs can be very short and compact
• Programs are reusable, well-structured, modular!
• Each significant piece of functionality is implemented in one place.
COMP302: Programming Languages and Paradigms 3 / 15
Functions are first-class values!
COMP302: Programming Languages and Paradigms 4 / 15
Functions are first-class values!
• Pass functions as arguments (Today) • Return them as results (Next week)
COMP302: Programming Languages and Paradigms 4 / 15
Functions are first-class values!
• Pass functions as arguments (Today) • Return them as results (Next week)
COMP302: Programming Languages and Paradigms 4 / 15
Abstracting over common functionality
COMP302: Programming Languages and Paradigms 5 / 15
Abstracting over common functionality
let rec sum (a,b) =
if a > b then 0 else a + sum(a+1,b)
COMP302: Programming Languages and Paradigms
Abstracting over common functionality
let rec sum (a,b) =
if a > b then 0 else a + sum(a+1,b)
COMP302: Programming Languages and Paradigms
Abstracting over common functionality
let rec sum (a,b) =
if a > b then 0 else a + sum(a+1,b)
k2 let rec sum (a,b) =
if a > b then 0 else square(a) + sum(a+1,b)
COMP302: Programming Languages and Paradigms
Abstracting over common functionality
let rec sum (a,b) =
if a > b then 0 else a + sum(a+1,b)
k2 let rec sum (a,b) =
if a > b then 0 else square(a) + sum(a+1,b)
2k let rec sum (a,b) =
if a > b then 0 else exp(2,a) + sum(a+1,b)
COMP302: Programming Languages and Paradigms
Abstracting over common functionality
let rec sum (a,b) =
if a > b then 0 else a + sum(a+1,b)
k2 let rec sum (a,b) =
if a > b then 0 else square(a) + sum(a+1,b)
2k let rec sum (a,b) =
if a > b then 0 else exp(2,a) + sum(a+1,b) Can we write a generic sum function?
Non-Generic Sum (old) Generic Sum using a function as an argument
sum:int*int->int sum: (int->int)->int*int-> int
COMP302: Programming Languages and Paradigms 5 / 15
COMP302: Programming Languages and Paradigms 6 / 15
Abstracting over common functionality
let rec sum f (a, b) =
if (a > b) then 0 else (f a) + sum f (a+1, b)
How about only summing up odd numbers between a and b?
COMP302: Programming Languages and Paradigms 7 / 15
Abstracting over common functionality
let rec sum f (a, b) =
if (a > b) then 0 else (f a) + sum f (a+2, b)
How about only summing up even numbers between a and b?
let rec sumOdd (a, b) =
if (a mod 2) = 1 then
sum (fun x -> x) (a, b) (* a was odd *) else
sum (fun x -> x) (a+1, b) (* a was even *)
COMP302: Programming Languages and Paradigms
Abstracting over common functionality (increment)
let rec sum f (a, b) inc =
if (a > b) then 0 else (f a) + sum f (inc(a), b) inc
How about only summing up even numbers between a and b?
let rec sumOdd (a, b) =
if (a mod 2) = 1 then
sum (fun x -> x) (a, b) (fun x -> x + 2) (* a was odd *) else
sum (fun x -> x) (a+1, b) (fun x -> x + 2) (* a was even *)
COMP302: Programming Languages and Paradigms
Abstracting over common functionality how we combine numbers in each step
let rec sum f (a, b) inc = if(a>b)then0else(fa)+ sumf(inc(a),b)inc
How about only multiplying numbers between a and b?
COMP302: Programming Languages and Paradigms 10 / 15
Abstracting over common functionality how we combine numbers in each step
let rec sum f (a, b) inc = if(a>b)then0else(fa)+ sumf(inc(a),b)inc
How about only multiplying numbers between a and b?
let rec product f (a, b) inc = if(a>b)then1else(fa)* productf(inc(a),b)inc
COMP302: Programming Languages and Paradigms
Abstracting over common functionality (tail-recursively) how we combine numbers in each step
let rec sum f (a, b) inc acc =
if (a > b) then 0 else sum f (inc(a), b) inc (f a + acc)
How about only multiplying numbers between a and b?
COMP302: Programming Languages and Paradigms 11 / 15
Abstracting over common functionality (tail-recursively) how we combine numbers in each step
let rec sum f (a, b) inc acc =
if (a > b) then 0 else sum f (inc(a), b) inc (f a + acc)
How about only multiplying numbers between a and b?
let rec product f (a, b) inc acc =
if (a > b) then 1 else product f (inc(a), b) inc (f a * acc)
COMP302: Programming Languages and Paradigms
COMP302: Programming Languages and Paradigms 12 / 15
Abstraction and higher-order functions are very powerful mechanisms for writing reusable prorgrams.
Computing a series
series: (int -> int -> int) -> (int -> int)
-> (int * int) -> (int -> int) -> int
(* comb *)
(* f *)
(* (a,b) *)
(* inc *)
(* acc *)
(* result *)
let sum f (a,b) inc = series (fun x y -> x + y) f (a,b) inc 0
let prod f (a,b) inc = series (fun x y -> x * y) f (a,b) inc 1
COMP302: Programming Languages and Paradigms
Bonus: Approximating the integral!
f(a+(dx/2)
Let l = a + dx/2.
= dx ∗ (f (l ) + f (l + dx ) + f (l + 2 ∗ dx ) + f (l + 3 ∗ dx ) . . .) COMP302: Programming Languages and Paradigms 14 / 15
bf(x)dx ≈f(l)∗dx+f(l+dx)∗dx+f(l+dx+dx)∗dx+…
Higher-order functions on data types
More higher-order functions next week!
COMP302: Programming Languages and Paradigms 15 / 15
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com