CS 421 — Higher Order Functions Activity
Reflector Assessesteamperformance
Keeps team on track Records decisions Reports to class
Learning Objectives
Copyright By PowCoder代写 加微信 powcoder
Mapping, folding, and zipping allow us to abstract away common list computations. Knowing how to use them will make you more productive as a programmer.
1. Reducecodesizebyusingmap,foldr,andzipWith.
2. Discoverhowtotakeafix-point.
3. Usetypesignaturestoimplementcurry,uncurry,andflip.
Mapping and Folding
Consider the following code, implementing three common higher order functions:
1 map :: (a->b) ->
2 map f [] = []
3 map f (x:xs) = f
5 foldr :: (a -> b
6 foldr f z [] = z
7 foldr f z (x:xs)
[a] -> [b]
x : map xs
-> b) -> b -> [a] -> b = f x (foldr z xs)
9 zipWith (a -> b -> c) -> [a] -> [b] -> [c]
10 zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
11zipWith _ _ _ = []
Problem 1) Use map to write a function that negates the elements of a list. Here is the recursive version.
1 negList [] = []
2 negList (x:xs) = – x : negList xs
Problem 2) Use foldr to write a function that returns the sums of the squares of the elements of a list.1 (E.g., sumSqr [3,4] will return 25.) Here is the recursive version.
1 sumSqr [] = 0
2sumSqr (x:xs) = x * x + sumSqr xs
Problem 3) Could you have used map to rewrite the above function? Why or why not?
Problem 4) How would you describe the relationship between map and zipWith?
Infinities
Consider this code, which deals with “infinite” lists.
1 foo = 1 : foo
2 bar = 1 : map (+1) bar
3 baz = map (**) bar
4 quuz = 1 : 1 : zipWith (+) quuz (tail quuz)
Problem 5) What do each of the above definitions do? Remember to use take if you try to type these in to the REPL.
Problem 6) The fix-point of function f is a value x such that f(x) = x. Write a function fix :: (a -> a) -> a -> a that takes a function f and returns its fix-point.
1 Prelude> cos 1
2 0.5403023058681398
3 Prelude> cos (cos 1) 4 0.8575532158463934
5 Prelude> fix cos 1
6 0.7390851332151607
Write the function fix.
1The type signature of foldr is actually a bit more general than this, but we will talk about that later.
List Comprehensions
List comprehensions are similar to higher order functions, and can allow you to write very compact code.
1 Prelude> stuff = 2Prelude> [ x+1 | 3 [9,7,8,6,4,1,10]
Problem7)Whatisthepurposeofthex <- stuffexpression?
Problem8)Whatisthepurposeofx > 5,andeven x?
Problem 9) How do you describe the order in which x and y are created in the last example?
Problem 10) What does the following code do?
1 guess [] = []
2 guess (x:xs) = guess [y | y <- xs, y < x]
3 ++ [x] ++
4 guess [y | y <- xs, y >= x]
x+1 | x+1 | x + y
[8,6,7,5,3,0,9] x <- stuff ]
x <- stuff, x > 5]
x <- stuff, x > 5, even x] | x <- stuff, y <- [10,20]]
4 Prelude> [
5 [9,7,8,10]
6 Prelude> [
8Prelude> [
9 [18,28,16,26,17,27,15,25,13,23,10,20,19,29]
Problem11)Writeafunctioncurry :: ((a,b) -> c) -> a -> b -> cthattakesafunctionthattakesapairandreturns an equivalent function that takes its arguments one at a time.
1 Prelude> let plus (a,b) = a + b 2 Prelude> :t plus
3 Num a => (a,a) -> a
4 Prelude> let cplus = curry plus 5 Prelude> cplus 10 20
Problem12)Writeafunctionflip :: (a -> b -> c) -> (b -> a -> c)thattakesafunctionthattakestwoarguments
and returns an equivalent function where the arguments have been reversed.
1 Prelude> let sub a b = a – b 2 Prelude> flip sub 10 2
Problem 13) Consider the types of flip and curry. Can you write another function that has either of those types? Try to prove it.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com