CS计算机代考程序代写 python Haskell algorithm ecs713-week4-lecture

ecs713-week4-lecture

Dr. Paulo Oliva / Prof. Edmund Robinson

Week 4: Function Expressions and
Higher Order Functions

ECS713
Functional Programming

This week (learning objectives)
• understand how to use function application and function composition
• be able to work with functions without “naming” them, using sections,

partial application, and anonymous functions

• understand the concept of a higher-order function
• be familiar with using common higher-order functions such as fold, map,

zipWith and filter.

This week (core)
• Function Expressions:

✦ Partial application
✦ Sections
✦ Anonymous functions (aka lambda expression)

• Higher Order Functions
✦ What is a Higher Order Function?
✦ map, filter and zipWith
✦ foldl and foldr
✦ Application and composition

This week (additional)
• Function Expressions:

✦ Partial application
✦ Sections
✦ Anonymous functions (aka lambda expression)

• Higher Order Functions
✦ What is a Higher Order Function?
✦ map, filter and zipWith
✦ foldl and foldr
✦ Application and composition

Language Uniformity: functions as first-class values

Language Uniformity: declarations
and expressions

map-reduce

foldr and recursion foldl and iterators

Language Uniformity

• Languages should not have special cases:
✦ You should not have constructs that behave in one way on one class

of things and differently on others

• Uniformity across constructs:
✦ If you have two “equivalent” ways of doing something, they should

actually work the same.

Functions as first-class values
• There is no distinction between functions and things of other (basic) types

in terms of what you can do with them.

• In particular:
✦ There are expressions that are interpreted as functions (not just

names introduced by declarations)
✦ You can return a function as the result of an operation (another

function)
✦ You can pass a function as a parameter to another operation (a

higher order function)

Dr. Paulo Oliva / Prof. Edmund Robinson

Function Expressions
ECS713

Functional Programming

Function Expressions

• An expression that has type a -> b is called a function
expression, because it has a “function” type

• Some useful ways of building function expressions:
✦ Partial application
✦ Sections
✦ Anonymous functions (aka lambda expression)

Partial Application
We can give just some of the arguments of a
function in order to define a new function

Prelude> let f name age = “Hi ” ++ name ++ ” you are ” ++ show(age)

Prelude> :type f

f :: String -> Int -> String

Prelude> f “John” 40

“Hi John you are 40”

Prelude> let greetJohn = f “John”

Prelude> :type greetJohn

greetJohn :: Int -> String

Prelude> greetJohn 20

“Hi John you are 20”

f takes two arguments

When we give it one argument
(“John”), we get a function that is
waiting for the second argument

We would call this a partial application

Infix versus Prefix

Prelude> 2 + 3

5

Prelude> div 8 2

4

Prelude> (+) 2 3

5

Prelude> 8 `div` 2

4

Some binary functions are more naturally written in
infix notation, while most are written in prefix notation

One can convert from one to
the other using ( ) and ` `

Prelude> let f = (+3)

Prelude> :type f

Int -> Int

Prelude> f 10

13

Prelude> let g = (2^)

Prelude> map g [1..5]

[2,4,8,16,32]

Prelude> let h = (^2)

Prelude> map h [1..5]

[1,4,9,16,25]

Sections
We can also do partial application in infix
binary functions, these are called sections

We call this the “right
section” of addition +

This is the“left section” of the
exponentiation function

The left and right sections could
be very different functions

Reading the type
-> types can be read in two different ways

Prelude> let f name age = “Hi ” ++ name ++ ” you are ” ++ show(age)

Prelude> :type f

f :: String -> Int -> String

We can read this as a single type constructor:
<> -> <> -> <>

applied to three types

But technically it is a compound construction,
built from two instances of

<> -> <>

Reading the type
-> types can be read in two different ways: but

technically all functions in Haskell have only a single
argument

Prelude> let f name age = “Hi ” ++ name ++ ” you are ” ++ show(age)

Prelude> :type f

f :: String -> Int -> String

String -> Int -> String

brackets as
String -> (Int -> String)

This fits with
f “John” 40

bracketing as
(f “John”) 40

The first argument of f is a
String

Partially applying f to this
String produces a function

Int -> String

*Main> filter ((==2).(`mod` 3)) [1..20]

[2,5,8,11,14,17,20]

*Main> filter (`elem` “aeiouAEIOU”) “The cat sat on the mat”

“eaaoea”

*Main> filter (not.(`elem` “aeiouAEIOU”)) “The cat sat on the

mat”

“Th ct st n th mt”

*Main>

Using sections
We can use sections in some complicated ways:

Prelude> let f n = n + 1

Prelude> f 10

11

Prelude> (\n -> n + 1) 10

11

Prelude> map (\n -> 2 * n) [1..5]

[2,4,6,8,10]

Prelude> map (2*) [1..5]

[2,4,6,8,10]

Anonymous functions
We can use the “lambda notation” to define a

function without giving it a name

This is called a “lambda expression”
because mathematically we would write this

as λn → n + 1

Sometimes a “section” is sufficient, these two
function expressions are equivalent

*Main> filter ((==2).(`mod` 3)) [1..20]

[2,5,8,11,14,17,20]

*Main> filter (\x -> x `mod` 3 == 2) [1..20]

[2,5,8,11,14,17,20]

*Main> filter (`elem` “aeiouAEIOU”) “The cat sat on the mat”

“eaaoea”

*Main> filter (not.(`elem` “aeiouAEIOU”)) “The cat sat on the mat”

“Th ct st n th mt”

*Main> filter (\x -> not (elem x “aeiouAEIOU”)) “The cat sat on the mat”

“Th ct st n th mt

*Main>

Using lambda expressions
We can use lambda expressions to make quick

anonymous functions:

Functions as first-class values
• There is no distinction between functions and things of other (basic) types

in terms of what you can do with them.

• In particular:
✦ There are expressions that are interpreted as functions (not just

names introduced by declarations)
✦ You can return a function as the result of an operation (another

function)
✦ You can pass a function as a parameter to another operation (a

higher order function)

— standard pattern-matching declaration – pattern = expr

f :: String -> Int -> String

f name age = “Hi “++name++” you are “++show(age)

— equivalent simple declarations – name = expr

g :: String -> Int -> String

g = \ name age -> “Hi “++name++” you are “++show(age)

h :: String -> Int -> String

h = \ name -> (\age -> “Hi “++name++” you are “++show(age))

Language uniformity
Using lambda expressions, any function declaration is

equivalent to a simple value declaration.

— standard pattern-matching declaration – pattern = expr

sum’ :: [Int] -> Int

sum’ [] = 0

sum’ (x:xs) = x + sum’ xs

— equivalent simple declaration – name = expr

sum” :: [Int] -> Int

sum” = \ xs -> case xs of

[] -> 0

(y:ys) -> y + sum” ys

Language uniformity
Using lambda expressions, any function declaration is

equivalent to a simple value declaration.

Language Uniformity

• Languages should not have special cases:
✦ You should not have constructs that behave in one way on one class

of things and differently on others

• Uniformity across constructs:
✦ If you have two “equivalent” ways of doing something, they should

actually work the same.

Dr. Paulo Oliva / Prof. Edmund Robinson

Higher Order Functions
ECS713

Functional Programming

Prelude> :type map

(a -> b) -> [a] -> [b]

Prelude> :type filter

(a -> Bool) -> [a] -> [a]

Prelude> :type foldl

(b -> a -> b) -> b -> [a] -> b

Prelude> :type foldr

(a -> b -> b) -> b -> [a] -> b

Higher Order Functions
Functions that take other functions as arguments!

map, filter and fold are
extremely useful higher order

functions!

Map
Prelude> :type map

map :: (a -> b) -> [a] -> [b]

Prelude> map (2*) [1..5]

[2,4,6,8,10]

Prelude> map (\x -> x + 17) [1..5]

[18,19,20,21,22]

Prelude> map not [True, False, True]

[False, True, False]

Prelude> :module Data.Char

Prelude Data.Char> map toUpper “coffee”

“COFFEE”

Function to be
“mapped”

List of inputs
List of results

Filter
Prelude> :type filter

filter :: (a -> Bool) -> [a] -> [a]

Prelude> filter odd [1..10]

[1,3,5,7,9]

Prelude> filter (<3.1415) [4.3,1.1,0.2,5.7] [1.1,0.2] Prelude> :module Data.Char

Prelude Data.Char> filter isDigit “17 Mandela Blvd”

“17”

Prelude Data.Char> filter isAlpha “17 Mandela Blvd”

“MandelaBlvd”

A “test”

Input list
Sub-list, with elements

that “pass the test”

map and filter are built in functions
but actually they have simple recursive definitions

map f [] = []

map f (x:xs) = (f x) : (map f xs)

filter p [] = []

filter p (x:xs) = if p x then x : rest else rest

where rest = filter p xs

map and filter have recursive
definitions, by recursion on the

input list xs

zip and zipWith

Prelude> :type zip

zip :: [a] -> [b] -> [(a, b)]

Prelude> zip [‘a’..’d’] [1..5]

[(‘a’,1),(‘b’,2),(‘c’,3),(‘d’,4)]

Prelude> :type zipWith

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

Prelude> zipWith (*) [1..4] [2..6]

[2,6,12,20]

2 5 3 71

3

Prelude> foldl (+) 1 [2,5,3,7]

18

Fold Left

A binary function Starting value

List to be “folded”

+

5 3 73

Prelude> foldl (+) 1 [2,5,3,7]

18

Fold Left

A binary function Starting value

List to be “folded”

+

8

3 7

11

Prelude> foldl (+) 1 [2,5,3,7]

18

Fold Left

A binary function Starting value

List to be “folded”

+

8

711

Prelude> foldl (+) 1 [2,5,3,7]

18

Fold Left

A binary function Starting value

List to be “folded”

+

18

18

Fold Left
Prelude> foldl (+) 1 [2,5,3,7]

18

A binary function Starting value

List to be “folded”

2 5 3 7 1

8

Prelude> foldr (+) 1 [2,5,3,7]

18

Fold Right

A binary function Starting value

List to be “folded”

+

2 5 3 8

Prelude> foldr (+) 1 [2,5,3,7]

18

Fold Right

A binary function Starting value

List to be “folded”

+

11

2 5

Prelude> foldr (+) 1 [2,5,3,7]

18

Fold Right

A binary function Starting value

List to be “folded”

+

11

16

2

Prelude> foldr (+) 1 [2,5,3,7]

18

Fold Right

A binary function Starting value

List to be “folded”

+

16

18

Prelude> foldr (+) 1 [2,5,3,7]

18

Fold Right

A binary function Starting value

List to be “folded”

18

foldl :: (a -> b -> a) -> a -> [b] -> a

foldr :: (b -> a -> a) -> a -> [b] -> a

Fold Left / Right

Prelude> foldl (*) 1 [1..5]

120

Prelude> foldr (*) 1 [1..5]

120

Prelude> foldl (^) 2 [1..3]

64

Prelude> foldr (^) 2 [1..3]

1

((2^1)^2)^3 = 64

1^(2^(3^2)) = 1

foldl and foldr are built in functions
but actually they have simple recursive definitions

foldl f b [] = b

foldl f b (x:xs) = foldl f (f b x) xs

foldr f b [] = []

foldr f b (x:xs) = f x (foldr b xs)

foldl and foldr have recursive
definitions, by recursion on the

input list xsfo

foldr :: (b -> a -> a) -> a -> [b] -> a

Fold Right / Recursion
concat’ [] = []

concat’ (xs:xss) = xs ++ concat’ xss

— refactor

concat’ [] = []

concat’ (xs:xss) = foo xs (concat’ xss)

where foo xs a = xs ++ a

— rewrite with foldr

concat’ = foldr foo []

where foo xs a = xs ++ a

foo xs (concat’ xss)

make the form explicit

foldl :: (a -> b -> a) -> a -> [b] -> a

Fold Left / Iterators
# Python

>>> y=0

>>> for x in [2,5,6]:

… y = y+x

>>> y

13

Iterator: for loop

Block makes y
function of y and x

— Haskell

foo y x = y+x

foldl foo 0 [2,5,6]

13

Block makes y
function of y and x

Iterator: for loop

Google’s MapReduce
(http://code.google.com/edu/parallel/mapreduce-tutorial.html#MapReduce)

(although link is no longer available)

Now that we have seen some basic examples of parallel programming, we can look at the
MapReduce programming model. This model derives from the map and reduce combinators from a
functional language like Lisp.

In Lisp, a map takes as input a function and a sequence of values. It then applies the
function to each value in the sequence. A reduce combines all the elements of a sequence
using a binary operation. For example, it can use “+” to add up all the elements in the
sequence.

MapReduce is inspired by these concepts. It was developed within Google as a mechanism for
processing large amounts of raw data, for example, crawled documents or web request logs.
This data is so large, it must be distributed across thousands of machines in order to be
processed in a reasonable time. This distribution implies parallel computing since the
same computations are performed on each CPU, but with a different dataset. MapReduce is an
abstraction that allows Google engineers to perform simple computations while hiding the
details of parallelization, data distribution, load balancing and fault tolerance.

Map, written by a user of the MapReduce library, takes an input pair and produces a set of
intermediate key/value pairs. The MapReduce library groups together all intermediate
values associated with the same intermediate key I and passes them to the reduce function.

The reduce function, also written by the user, accepts an intermediate key I and a set of
values for that key. It merges together these values to form a possibly smaller set of
values.

http://code.google.com/edu/parallel/mapreduce-tutorial.html#

Divide and conquer

Divide and conquer

• Classic algorithmic technique

• Split your problem into smaller ones

• Keep splitting until solution is trivial

• Combine solutions to get solution for large problem.

Divide and conquer: sorting

• Split list into smaller lists.

• Sort smaller lists.

• Combine sorted lists.

Divide and conquer

• Split list into smaller lists.

• Sort smaller lists.

• Combine sorted lists.

• Divide and conquer is always a candidate for
recursion.

Divide and conquer:
mergesort

• Split list into smaller lists – put no effort into this, but
ideally into two halves.

• Sort smaller lists.

• Combine sorted lists: work done here using merge.

Divide and conquer:
quicksort

• Split list into smaller lists – put effort into this: make
sure everything in one list is smaller than anything in
the other.

• Sort smaller lists.

• Combine sorted lists: now trivial since you can just
concatenate.

Divide and conquer:
functional mergesort

• Function to split list: simple like dealing cards

halve :: [a] -> ([a],[a])
halve [] = ([],[])
halve [a] = ([a],[])
halve (a1:a2:as) = let (t1,t2) = halve as in
(a1:t1,a2:t2)

Divide and conquer:
functional mergesort

• Function to merge sorted lists:

merge :: Ord a => [a] -> [a] -> [a]
merge as [] = as
merge [] (b:bs) = b:bs
merge (a:as) (b:bs) | a <= b = a:(merge as (b:bs)) merge (a:as) (b:bs) | otherwise = b:(merge (a:as) bs) Divide and conquer: functional mergesort • Put them together with trivial cases mergesort :: [a] -> [a] -> [a]
mergesort [] = []
mergesort [a] = [a]
mergesort (a1:a2:as) = let (t1,t2) = halve (a1:a2:as) in
merge (mergesort t1) (mergesort t2)

Divide and conquer:
functional quicksort

quicksort :: Ord a => [a] -> [a] -> [a]
quicksort [] = []
quicksort (a:as) = let t1 = [x | x <- as, x<=a] t2 = [x | x <- as, a