# CS计算机代考程序代写 data structure Haskell jquery cse130

cse130

file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

13 of 35

2/9/21, 8:58 AM

filter

The ¡°map¡± pattern

The map Pattern General Pattern

HOF map

Apply a transformation f to each element of a list

Specific Operations

Transformations toUpper and x -> x * x

map f [] = []

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

Lets refactor shout and squares

filter cond CT

L

x rest rest

filtercondCx I conax

I otherwise

where

filtercondxs I

rest

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

shout = map …

squares = map …

Q

map instances

QUIZ

What is the type of map ?

map f [] = []

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

14 of 35 2/9/21, 8:58 AM

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

(A) (Char -> Char) -> [Char] -> [Char] (B) (Int -> Int) -> [Int] -> [Int]

(C) (a -> a) -> [a] -> [a]

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

(E) (a -> b) -> [c] -> [d]

— For any types `a` and `b`

— if you give me a transformation from `a` to `b`

— and a list of `a`s,

— I’ll give you back a list of `b`s map :: (a -> b) -> [a] -> [b]

f

Type says it all!

The only meaningful thing a function of this type can do is apply its first argument to elements of the list

Hoogle it!

is

15 of 35 2/9/21, 8:58 AM

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

Things to try at home: 7

can you write a function map’ :: (a -> b) -> [a] -> [b] whose

behavior is di”erent from map ?

can you write a function map’ :: (a -> b) -> [a] -> [b] such that

map’ f xs returns a list whose elements are not in map f xs ?

z

X

QUIZ

x

x

What is the value of quiz ?

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

aint

quiz = map ((x, y) -> x + y) [1, 2, 3]

(A) [2, 4, 6]

(B) [3, 5]

(C) Syntax Error

(D) Type Error

(E) None of the above

Int Int

16 of 35 2/9/21, 8:58 AM

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

Don¡¯t Repeat Yourself

Benefits of factoring code with HOFs: Reuse iteration pattern

think in terms of standard patterns

lesstowrite1lesscodetofix maintain easier to communicate

Avoid bugs due to repetition

17 of 35 2/9/21, 8:58 AM

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

Recall: length of a list

— len [] ==> 0

— len [“carne”,”asada”] ==> 2 len :: [a] -> Int

len [] =0

len (x:xs) = 1 + len xs

Recall: summing a list

— sum [] ==> 0 — sum [1,2,3] ==> 6 sum :: [Int] -> Int sum [] =0

sum (x:xs) = x + sum xs

18 of 35 2/9/21, 8:58 AM

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

Example: string concatenation

Let¡¯s write a function cat :

— cat [] ==> “”

— cat [“carne”,”asada”,”torta”] ==> “carneasadatorta” cat :: [String] -> String

cat [] = …

cat (x:xs) = …

Can you spot the pattern?

19 of 35 2/9/21, 8:58 AM

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

— len

foo [] = 0

foo (x:xs) = 1 + foo xs

— sum

foo [] = 0

foo (x:xs) = x + foo xs

— cat

foo [] = “”

foo (x:xs) = x ++ foo xs

pattern = …

The ¡°fold-right¡± pattern

20 of 35 2/9/21, 8:58 AM

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

The foldr Pattern General Pattern

Recurse on tail

Combine result with the head using some binary operation

foldr f b [] = b

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

Let¡¯s refactor sum , len and cat : sum = foldr … …

cat = foldr … …

len = foldr … …

Factor the recursion out!

21 of 35 2/9/21, 8:58 AM

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

foldr instances

You can write it more clearly as

sum = foldr (+) 0

cat = foldr (++) “”

Nc

b

Nz Nz 2cgw

The ¡°fold-right¡± pattern

22 of 35 2/9/21, 8:58 AM

cse130

file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

23 of 35

2/9/21, 8:58 AM

foldr f b [a1, a2, a3, a4]

==> f a1 (foldr f b [a2, a3, a4])

==> f a1 (f a2 (foldr f b [a3, a4]))

==> f a1 (f a2 (f a3 (foldr f b [a4])))

==> f a1 (f a2 (f a3 (f a4 (foldr f b []))))

==> f a1 (f a2 (f a3 (f a4 b)))

cars

cat

cat deg

x IfI x

Accumulate the values from the right

For example:

dog

horse horse t

foldr (+) 0 [1, 2, 3, 4]

==> 1 + (foldr (+) 0 [2, 3, 4])

==> 1 + (2 + (foldr (+) 0 [3, 4]))

==> 1 + (2 + (3 + (foldr (+) 0 [4])))

==> 1 + (2 + (3 + (4 + (foldr (+) 0 []))))

==> 1 + (2 + (3 + (4 + 0)))

se

QUIZ

What does this evaluate to?

Kz

Nz

C

t seaPby

ok

op

z op 2cgop b

Tor

op

1

2cg

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

foldr f b [] =b

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

quiz = foldr (x v -> x : v) [] [1,2,3]

(A) Type error

(B) [1,2,3]

(C) [3,2,1]

(D) [[3],[2],[1]] (E) [[1],[2],[3]]

X Kz Ks Ky

a C

x i K2 Nz

2cg

foldr (:) [] [1,2,3]

==> (:) 1 (foldr (:) [] [2, 3])

==> (:) 1 ((:) 2 (foldr (:) [] [3]))

==> (:) 1 ((:) 2 ((:) 3 (foldr (:) [] []))) ==> (:) 1 ((:) 2 ((:) 3 []))

== 1:(2:(3:[]))

== [1,2,3]

24 of 35 2/9/21, 8:58 AM

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

QUIZ

HW EXERUSE What is the most general type of foldr ?

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

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

(A) (a -> a -> a) -> a -> [a] -> a (B) (a -> a -> b) -> a -> [a] -> b (C) (a -> b -> a) -> b -> [a] -> b (D) (a -> b -> b) -> b -> [a] -> b (E) (b -> a -> b) -> b -> [a] -> b

25 of 35 2/9/21, 8:58 AM

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

Tail Recursive Fold

foldr f b [] = b

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

Is foldr tail recursive?

Not

TR

What about tail-recursive versions?

Let¡¯s write tail-recursive sum !

sumTR :: [Int] -> Int

sumTR = …

26 of 35 2/9/21, 8:58 AM

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

Lets run sumTR to see how it works

sumTR [1,2,3]

==> helper 0 [1,2,3]

==> helper 1 [2,3]

==> helper 3 [3]

==> helper 6 []

==> 6

— 0 + 1 ==> 1

— 1 + 2 ==> 3

— 3 + 3 ==> 6

Note: helper directly returns the result of recursive call!

Let¡¯s write tail-recursive cat !

catTR :: [String] -> String

catTR = …

27 of 35 2/9/21, 8:58 AM

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

Lets run catTR to see how it works

catTR

==> helper “”

==> helper “carne”

==> helper “carneasada”

==> helper “carneasadatorta”

[“carne”, “asada”, “torta”]

[“carne”, “asada”, “torta”]

[“asada”, “torta”]

[“torta”]

[]

==> “carneasadatorta”

Note: helper directly returns the result of recursive call!

28 of 35 2/9/21, 8:58 AM

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

Can you spot the pattern?

— sumTR

foo xs = helper 0 xs

where

helper acc [] = acc

helper acc (x:xs) = helper (acc + x) xs

— catTR

foo xs = helper “” xs

where

helper acc [] = acc

helper acc (x:xs) = helper (acc ++ x) xs

pattern = …

The ¡°fold-left¡± pattern

29 of 35 2/9/21, 8:58 AM

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

The foldl Pattern General Pattern

Use a helper function with an extra accumulator argument

To compute new accumulator, combine current accumulator with the head using some binary operation

foldl f b xs = helper b xs

where

helper acc [] = acc

helper acc (x:xs) = helper (f acc x) xs

Let¡¯s refactor sumTR and catTR : sumTR = foldl … …

catTR = foldl … …

Factor the tail-recursion out!

30 of 35 2/9/21, 8:58 AM

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

QUIZ

What does this evaluate to?

foldl f b xs = helper b xs

where

helper acc [] = acc

helper acc (x:xs) = helper (f acc x) xs

quiz = foldl (xs x -> x : xs) [] [1,2,3]

(A) Type error

(B) [1,2,3]

(C) [3,2,1]

(D) [[3],[2],[1]] (E) [[1],[2],[3]]

31 of 35 2/9/21, 8:58 AM

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

foldl f b (x1: x2: x3 : [])

==> helper b (x1: x2: x3 : [])

==> helper (f x1 b) (x2: x3 : [])

==> helper (f x2 (f x1 b)) (x3 : [])

==> helper (f x3 (f x2 (f x1 b))) []

==> ( x3 : (x2 : (x1 : [])))

The ¡°fold-left¡± pattern

foldl f b

==> helper b

==> helper (f b x1)

==> helper (f (f b x1) x2)

==> helper (f (f (f b x1) x2) x3) [x4]

==> helper (f (f (f (f b x1) x2) x3) x4) []

==> (f (f (f (f b x1) x2) x3) x4)

Accumulate the values from the left For example:

[x1, x2, x3, x4]

[x1, x2, x3, x4]

[x2, x3, x4]

[x3, x4]

32 of 35 2/9/21, 8:58 AM

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

foldl (+) 0

==> helper 0

==> helper (0 + 1)

==> helper ((0 + 1) + 2)

==> helper (((0 + 1) + 2) + 3)

==> helper ((((0 + 1) + 2) + 3) + 4) []

==> ((((0 + 1) + 2) + 3) + 4)

Left vs.Right

foldl f b [x1, x2, x3]

foldr f b [x1, x2, x3]

For example:

foldl (+) 0 [1, 2, 3]

foldr (+) 0 [1, 2, 3]

Di”erent types!

==> f (f (f b x1) x2) x3

==> f x1 (f x2 (f x3 b))

— Left

— Right

[1, 2, 3, 4]

[1, 2, 3, 4]

[2, 3, 4]

[3, 4]

[4]

==> ((0 + 1) + 2) + 3 — Left ==> 1 + (2 + (3 + 0)) — Right

33 of 35 2/9/21, 8:58 AM

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

foldl :: (b -> a -> b) -> b -> [a] -> b — Left foldr :: (a -> b -> b) -> b -> [a] -> b — Right

Higher Order Functions

Iteration patterns over collections:

Filter values in a collection given a predicate

Map (iterate) a given transformation over a collection

Fold (reduce) a collection into a value, given a binary operation to combine results

HOFs can be put into libraries to enable modularity

Data structure library implements map , filter , fold for its collections

generic e!cient implementation

generic optimizations: map f (map g xs) –> map (f.g) xs Data structure clients use HOFs with specific operations

no need to know the implementation of the collection

34 of 35 2/9/21, 8:58 AM

cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html

Crucial foundation of

¡°big data¡± revolution e.g. MapReduce, Spark, TensorFlow ¡°web programming¡± revolution e.g. Jquery, Angular, React

(https://ucsd-cse130.github.io/wi21/feed.xml) (https://twitter.com/ranjitjhala) (https://plus.google.com/u/0/104385825850161331469) (https://github.com/ranjitjhala)

Generated by Hakyll (http://jaspervdj.be/hakyll), template by Armin Ronacher (http://lucumr.pocoo.org), suggest improvements here (https://github.com /ucsd-progsys/liquidhaskell-blog/).

35 of 35 2/9/21, 8:58 AM