留学生代考 COMP 302: Programming Languages and Paradigms

COMP 302: Programming Languages and Paradigms
Week 4: Higher-Order Functions Prof. Xujie Si

Slogan: functions are first-class citizen

Copyright By PowCoder代写 加微信 powcoder

Slogan: functions are first-class citizen
• Functions are values!
• Values can be passed around, manipulated, and returned. • So are functions!
• Higher-order function
• A function that takes a function as an argument, or returns a function

Slogan: functions are first-class citizen
• Functions are values!
• Values can be passed around, manipulated, and returned. • So are functions!
• Higher-order function
• A function that takes a function as an argument, or returns a function

Slogan: functions are first-class citizen
• Functions are values!
• Values can be passed around, manipulated, and returned. • So are functions!
• Higher-order function
• A function that takes a function as an argument, or returns a function

Slogan: functions are first-class citizen
• Functions are values!
• Values can be passed around, manipulated, and returned. • So are functions!
• Higher-order function
• A function that takes a function as an argument, or returns a function

Example: addition is a higher-order function!
let add x y = x + y

Example: addition is a higher-order function!
let add x y = x + y

Example: addition is a higher-order function!
let add x y = x + y letadd= funxy->x+y

Example: addition is a higher-order function!
let add x y = x + y letadd= funxy->x+y let add = function

Example: addition is a higher-order function!
let add x y = x + y letadd= funxy->x+y let add = function x ->

Example: addition is a higher-order function!
let add x y = x + y
letadd= funxy->x+y
let add = function x -> function y -> x + y

Example: addition is a higher-order function!
let add x y = x + y
letadd= funxy->x+y
let add = function x -> function y -> x + y
let add_two = add 2

Example: addition is a higher-order function!
let add x y = x + y
letadd= funxy->x+y
let add = function x -> function y -> x + y
let add_two = add 2
= (function x -> function y -> x + y) 2

Example: addition is a higher-order function!
let add x y = x + y
letadd= funxy->x+y
let add = function x -> function y -> x + y
let add_two = add 2
= (function x -> function y -> x + y) 2
= (function y -> 2 + y)

Example: addition is a higher-order function!
let add x y = x + y
letadd= funxy->x+y
let add = function x -> function y -> x + y
let add_two = add 2
= (function x -> function y -> x + y) 2
= (function y -> 2 + y)
let res = add_two 10

Example: addition is a higher-order function!
let add x y = x + y
letadd= funxy->x+y
let add = function x -> function y -> x + y
let add_two = add 2
= (function x -> function y -> x + y) 2
= (function y -> 2 + y)
let res = add_two 10
= (function y -> 2 + y) 10

Example: addition is a higher-order function!
let add x y = x + y
letadd= funxy->x+y
let add = function x -> function y -> x + y
let add_two = add 2
= (function x -> function y -> x + y) 2
= (function y -> 2 + y)
let res = add_two 10
= (function y -> 2 + y) 10
= (2 + 10)

Example: addition is a higher-order function!
let add x y = x + y
letadd= funxy->x+y
let add = function x -> function y -> x + y
let add_two = add 2
= (function x -> function y -> x + y) 2
= (function y -> 2 + y)
let res = add_two 10
= (function y -> 2 + y) 10
= (2 + 10)

Example: addition is a higher-order function!
let add x y = x + y
letadd= funxy->x+y
let add = function x -> function y -> x + y
let add_two = add 2
= (function x -> function y -> x + y) 2
= (function y -> 2 + y)
let res = add_two 10
= (function y -> 2 + y) 10
= (2 + 10)
add : int -> int -> int

Example: addition is a higher-order function!
let add x y = x + y
letadd= funxy->x+y
let add = function x -> function y -> x + y
let add_two = add 2
= (function x -> function y -> x + y) 2
= (function y -> 2 + y)
let res = add_two 10
= (function y -> 2 + y) 10
= (2 + 10)
add : int -> int -> int
add : int -> (int -> int)

Example: addition is a higher-order function!
let add x y = x + y
letadd= funxy->x+y
let add = function x -> function y -> x + y
add : int -> int -> int
add : int -> (int -> int)
f : int -> int -> int -> int
= (function x -> function y -> x + y) 2
let add_two = add 2
= (function y -> 2 + y)
let res = add_two 10
= (function y -> 2 + y) 10
= (2 + 10) = 12

Example: addition is a higher-order function!
let add x y = x + y
letadd= funxy->x+y
let add = function x -> function y -> x + y
add : int -> int -> int
add : int -> (int -> int)
f : int -> int -> int -> int
f : int ->(int ->(int -> int))
let add_two = add 2
= (function x -> function y -> x + y) 2
= (function y -> 2 + y)
let res = add_two 10
= (function y -> 2 + y) 10
= (2 + 10)

Example: apply_twice

Example: apply_twice
let apply_twice f x = f (f x)

Example: apply_twice
let apply_twice f x = f (f x)
= function f -> function x -> f (f x)

Example: apply_twice
let apply_twice f x = f (f x)
= function f -> function x -> f (f x)

Example: apply_twice
let apply_twice f x = f (f x)
= function f -> function x -> f (f x)
f : int -> float

Example: apply_twice
let apply_twice f x = f (f x)
= function f -> function x -> f (f x)
f : int -> float (f x): float

Example: apply_twice
let apply_twice f x = f (f x)
= function f -> function x -> f (f x)
f : int -> float (f x): float

Example: apply_twice
let apply_twice f x = f (f x)
= function f -> function x -> f (f x)
f : int -> float
f : int -> int
(f x): float

Example: apply_twice
let apply_twice f x = f (f x)
= function f -> function x -> f (f x)
f : int -> float
f : int -> int
(f x): float
(f x): int

Example: apply_twice
let apply_twice f x = f (f x)
= function f -> function x -> f (f x)
f : int -> float
f : int -> int
(f x): float
(f x): int

Example: apply_twice
let apply_twice f x = f (f x)
= function f -> function x -> f (f x)
f : int -> float (f x): float
f : int -> int (f x): int x : ‘a f : ‘a -> ‘a

Example: apply_twice
let apply_twice f x = f (f x)
= function f -> function x -> f (f x)
apply_twice : (‘a -> ‘a) -> ‘a -> ‘a
f : int -> float (f x): float
f : int -> int (f x): int x : ‘a f : ‘a -> ‘a

Example: apply_twice
let apply_twice f x = f (f x)
= function f -> function x -> f (f x)
apply_twice : (‘a -> ‘a) -> ‘a -> ‘a
let apply_twice (f : ‘a -> ‘a) (x : ‘a) : ‘a =
f : int -> float (f x): float
f : int -> int (f x): int x : ‘a f : ‘a -> ‘a

Example: apply_twice
let apply_twice f x = f (f x)
= function f -> function x -> f (f x)
apply_twice : (‘a -> ‘a) -> ‘a -> ‘a
let apply_twice (f : ‘a -> ‘a) (x : ‘a) : ‘a =
Howabout x:int->int??
f : int -> float (f x): float
f : int -> int (f x): int x : ‘a f : ‘a -> ‘a

Example: apply_twice
let apply_twice f x = f (f x)
= function f -> function x -> f (f x)
apply_twice : (‘a -> ‘a) -> ‘a -> ‘a
let apply_twice (f : ‘a -> ‘a) (x : ‘a) : ‘a =
Howabout x:int->int??
x : int -> int -> int ??
f : int -> float (f x): float
f : int -> int (f x): int
f : ‘a -> ‘a

let addT2 (x, y) = x + y

letaddT2(x,y)=x+y addT2:int*int->int

letaddT2(x,y)=x+y addT2:int*int->int let add x y = x + y add : int -> int -> int

letaddT2(x,y)=x+y addT2:int*int->int let add x y = x + y add : int -> int -> int
f : ‘a * ‘b -> ‘c

letaddT2(x,y)=x+y addT2:int*int->int let add x y = x + y add : int -> int -> int
f : ‘a * ‘b -> ‘c g : ‘a -> ‘b -> ‘c

letaddT2(x,y)=x+y addT2:int*int->int let add x y = x + y add : int -> int -> int
f : ‘a * ‘b -> ‘c g : ‘a -> ‘b -> ‘c let currying f = ???

letaddT2(x,y)=x+y addT2:int*int->int let add x y = x + y add : int -> int -> int
f : ‘a * ‘b -> ‘c g : ‘a -> ‘b -> ‘c let currying f = ???

letaddT2(x,y)=x+y addT2:int*int->int let add x y = x + y add : int -> int -> int
f : ‘a * ‘b -> ‘c g : ‘a -> ‘b -> ‘c
let currying f = ???
function x -> function y -> f (x,y)

letaddT2(x,y)=x+y addT2:int*int->int let add x y = x + y add : int -> int -> int
f : ‘a * ‘b -> ‘c g : ‘a -> ‘b -> ‘c let currying f = ???
function x -> function y -> f (x,y)
currying : (‘a * ‘b -> ‘c) -> ‘a -> ‘b -> ‘c

letaddT2(x,y)=x+y addT2:int*int->int let add x y = x + y add : int -> int -> int
f : ‘a * ‘b -> ‘c g : ‘a -> ‘b -> ‘c let currying f = ???
function x -> function y -> f (x,y)
currying : (‘a * ‘b -> ‘c) -> ‘a -> ‘b -> ‘c
let uncurrying g = ???

letaddT2(x,y)=x+y addT2:int*int->int let add x y = x + y add : int -> int -> int
f : ‘a * ‘b -> ‘c g : ‘a -> ‘b -> ‘c let currying f = ???
function x -> function y -> f (x,y)
currying : (‘a * ‘b -> ‘c) -> ‘a -> ‘b -> ‘c
let uncurrying g = ???
function (x,y) -> g x y

letaddT2(x,y)=x+y addT2:int*int->int let add x y = x + y add : int -> int -> int
f : ‘a * ‘b -> ‘c g : ‘a -> ‘b -> ‘c let currying f = ???
function x -> function y -> f (x,y)
currying : (‘a * ‘b -> ‘c) -> ‘a -> ‘b -> ‘c
let uncurrying g = ???
function (x,y) -> g x y
uncurrying : (‘a -> ‘b -> ‘c) -> ‘a * ‘b -> ‘c

One more example: sum numbers

One more example: sum numbers

One more example: sum numbers

One more example: sum numbers

One more example: sum numbers

One more example: sum numbers

One more example: sum numbers

One more example: sum numbers
Can we have a generic sum function?

One more example: sum numbers
Can we have a generic sum function?

One more example: sum numbers
Can we have a generic sum function?
let f = fun x -> x

One more example: sum numbers
Can we have a generic sum function?
let f = fun x -> x
let f = fun x -> square x

One more example: sum numbers
Can we have a generic sum function?
let f = fun x -> x
let f = fun x -> square x
let f = square

One more example: sum numbers
Can we have a generic sum function?
let f = fun x -> x
let f = fun x -> square x
let f = square
let f = fun x -> exp(2,x)

Common Higher-Order Functions (Built-in)
Ocaml List Library API: https://ocaml.org/api/List.html

fold_left vs fold_right

fold_left vs fold_right

fold_left vs fold_right

fold_left vs fold_right
bop x [y1;y2;…;yn]

fold_left vs fold_right
bop x [y1;y2;…;yn] (((x `bop` y1) `bop` y2) … `bop` yn)

fold_left vs fold_right
bop x [y1;y2;…;yn] (((x `bop` y1) `bop` y2) … `bop` yn)

fold_left vs fold_right
bop x [y1;y2;…;yn] (((x `bop` y1) `bop` y2) … `bop` yn)
bop [y1;y2;…;yn] x

fold_left vs fold_right
bop x [y1;y2;…;yn] (((x `bop` y1) `bop` y2) … `bop` yn)
bop [y1;y2;…;yn] x
(y1 `bop` … (y_{n-1} `bop` (yn `bop` x)))

fold_left vs fold_right
bop x [y1;y2;…;yn] (((x `bop` y1) `bop` y2) … `bop` yn)
bop [y1;y2;…;yn] x
(y1 `bop` … (y_{n-1} `bop` (yn `bop` x)))
let sum ls = List.fold_left (+) 0 ls

fold_left vs fold_right
bop x [y1;y2;…;yn] (((x `bop` y1) `bop` y2) … `bop` yn)
bop [y1;y2;…;yn] x
(y1 `bop` … (y_{n-1} `bop` (yn `bop` x)))
let sum ls = List.fold_left (+) 0 ls
let sum ls = List.fold_right (+) ls 0

Some Exercises
• Increase each number in a list by 10 (List.map)
• Sum up numbers in a list (List.fold_right, List.fold_left) • Reverse a list (List.fold_right, List.fold_left)
• Check if a list contains a negative number (List.exists) • Check if all numbers in a list are positive (List.for_all)
• Only keep odd numbers in a list (List.filter)

Some Exercises
• Increase each number in a list by 10 (List.map)
• Sum up numbers in a list (List.fold_right, List.fold_left) • Reverse a list (List.fold_right, List.fold_left)
• Check if a list contains a negative number (List.exists) • Check if all numbers in a list are positive (List.for_all)
• Only keep odd numbers in a list (List.filter)
let reverse ls = List.fold_left (fun xs x -> x :: xs) [] ls

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com