COMP302: Programming Languages and Paradigms
Prof. (Sec 01) Francisco Ferreira (Sec 02)
School of Computer Science Mc
Copyright By PowCoder代写 加微信 powcoder
Week 4-1, Fall 2017
Functional Tidbit: Cool Kids!
“Higher-order functions; relatively simple once mastered yet very powerful and they make you look awesome! ”
(TA for COMP 302) Office Hours: Wed 12:00pm – 2:00pm
“Higher order functions are super cool!”
(TA for COMP 302) Office Hours: Wed 2:00pm – 4:00pm
COMP302: Programming Languages and Paradigms
Functions are first-class values!
COMP302: Programming Languages and Paradigms 3 / 11
Functions are first-class values!
• Pass functions as arguments (Continued) • Return them as results (Today)
COMP302: Programming Languages and Paradigms 3 / 11
Functions are first-class values!
• Pass functions as arguments (Continued) • Return them as results (Today)
COMP302: Programming Languages and Paradigms 3 / 11
Common Higher-Order Functions (Built-In)
COMP302: Programming Languages and Paradigms 4 / 11
Common Higher-Order Functions (Built-In)
• List.map: (’a -> ’b) -> ’a list -> ’b list
• List.filter: (’a -> bool) -> ’a list -> ’a list
• List.fold_right: (’a -> ’b -> ’b) -> ’a list -> ’b -> ’b • List.fold_left: (’a -> ’b -> ’a) -> ’a -> ’b list -> ’a • List.for_all: (’a -> bool) -> ’a list -> bool
• List.exists : (’a -> bool) -> ’a list -> bool
Check the OCaml List library for more built-in higher-order functions! They make great practice questions!
COMP302: Programming Languages and Paradigms
Slogan – Revisited
Functions are first-class values!
• Pass functions as arguments (Continued) • Return them as results (Today)
COMP302: Programming Languages and Paradigms 5 / 11
What does it mean to return a function?
Let’s go back to the beginning … from the 1. week
1 2 3 4 5 6
(* We can also bind variable to functions. *)
let area : float -> float = function r -> pi *. r *. r
(* or more conveniently, we write usually *)
let area (r:float) = pi *. r *. r
• The variable name area is bound to the value
function r -> pi *. r *. r which OCaml prints simply as
• The type of the variable area is float -> float. COMP302: Programming Languages and Paradigms
Switching your viewpoint
Write a function curry that
• takes as input a function f:(’a * ’b) -> ’c
• returns as a result a function ’a -> ’b -> ’c.
. OMP302: Programming Languages and Paradigms
Switching your viewpoint
Write a function curry that
• takes as input a function f:(’a * ’b) -> ’c
• returns as a result a function ’a -> ’b -> ’c.
(* curry : ((’a * ’b) -> ’c) -> ’a -> ’b -> ’c *) (* Note : Arrows are right-associative. *) let curry f = (fun x y -> f (x,y))
. OMP302: Programming Languages and Paradigms
Switching your viewpoint
1 2 3 4 5 6 7
Write a function curry that
• takes as input a function f:(’a * ’b) -> ’c
• returns as a result a function ’a -> ’b -> ’c.
(* curry : ((’a * ’b) -> ’c) -> ’a -> ’b -> ’c *) (* Note : Arrows are right-associative. *) let curry f = (fun x y -> f (x,y))
let curry_version2 f x y = f (x,y)
let curry_version3 = fun f -> fun x -> fun y -> f (x,y)
. OMP302: Programming Languages and Paradigms
Switching your viewpoint
1 2 3 4 5 6 7
Write a function curry that
• takes as input a function f:(’a * ’b) -> ’c
• returns as a result a function ’a -> ’b -> ’c.
(* curry : ((’a * ’b) -> ’c) -> ’a -> ’b -> ’c *) (* Note : Arrows are right-associative. *) let curry f = (fun x y -> f (x,y))
let curry_version2 f x y = f (x,y)
let curry_version3 = fun f -> fun x -> fun y -> f (x,y)
. OMP302: Programming Languages and Paradigms
Let’s play!
COMP302: Programming Languages and Paradigms 8 / 11
Bonus: Approximating the Derivative
f′(x) = df = lim f(x +ε)−f(x) dxε→0 ε
COMP302: Programming Languages and Paradigms 9 / 11
Bonus: Approximating the Derivative
f′(x) = df = lim f(x +ε)−f(x) dxε→0 ε
Implement a function deriv : (float -> float) * float -> float -> float which
• given a function f:float -> float and an epsilon dx:float
• returns a function float -> float describing the derivative of f.
COMP302: Programming Languages and Paradigms 9 / 11
Bonus: Approximating the Derivative
f′(x) = df = lim f(x +ε)−f(x) dxε→0 ε
Implement a function deriv : (float -> float) * float -> float -> float which
• given a function f:float -> float and an epsilon dx:float
• returns a function float -> float describing the derivative of f.
COMP302: Programming Languages and Paradigms 10 / 11
Bonus: Approximating the Derivative
f′(x) = df = lim f(x +ε)−f(x) dxε→0 ε
Implement a function deriv : (float -> float) * float -> float -> float which
• given a function f:float -> float and an epsilon dx:float
• returns a function float -> float describing the derivative of f.
1 let deriv (f, dx) = fun x -> (f (x +. dx) -. f x) /. dx
COMP302: Programming Languages and Paradigms 10 / 11
Higher-order functions are super cool!
COMP302: Programming Languages and Paradigms 11 / 11
Higher-order functions are super cool!
Question: Do you know what the functions in the picture mean?
COMP302: Programming Languages and Paradigms 11 / 11
Functional Tidbit: Church and the Lambda-Calculus
• Logician and Mathematician
• June 14, 1903 – August 11, 1995
• Most known for the Lambda-Calculus:
– a simple language consisting of variables, functions (written as λx.t) and function application
– we can define all computable functions in the Lambda-Calculus!
Church Encoding of Booleans: T = λx.λy.x
F = λx.λy.y
COMP302: Programming Languages and Paradigms 12 / 11
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com