程序代写代做代考 Haskell algorithm Assignment 7 CIS 252 — Intro to Computer Science
Assignment 7 CIS 252 — Intro to Computer Science
Coverage & Logistics
This assignment focuses on material in Chapters 10 and 11 of Haskell: The Craft
of Functional Programming.
This homework is officially due in class on Thursday, March 23. However, it
comes with an automatic extension: anything submitted to the CIS 252 bin near
CST 4-226 by noon on Friday, March 24 will be accepted as being on time.
You may work singly or in pairs on this assignment.
What to turn in
You should turn in a hard copy of your source code and a transcript that demon-
strates convincingly that your code is correct.
Exercises
1. Fill in the blanks below to write a function such that locate x ys returns
a list of indices of locations of x in ys:
locate :: Eq a => a -> [a] -> [Int]
locate x ys = map ______ (filter _______ (zip [1..] ys))
For example, (locate ’i’ “mississippi”) should return [2,5,8,11].
2. Fill in the blanks below to write a function that, given a list of non-negative
Ints, produces a histogram string for the sequence:
histogram :: [Int] -> String
histogram xs = concat (map f xs)
where
f :: _________ -> ____________
f ________ = ________________________
That is, if the k-th element of the input list is n, then the k-th line of the
string produced by histogram consists of n asterisks in a row, terminated by
the newline character ’
’. For example, (histogram [5,3,1,4]) should
return “*****
***
*
****
”.
To display your histogram nicely, use putStrLn at the ghci prompt:
*Main > putStrLn (histogram [5,3,1,4])
*****
***
*
****
3. Fill in the blank below to write a one-line function manyFuns that, given a
list of functions and a value, applies each function to that value:
manyFuns :: [a -> b] -> a -> [b]
manyFuns fs v = map _____________ fs
For example, manyFuns [reverse, tail, take 2] “hello” should re-
turn [“olleh”,”ello”,”he”].
4. Consider the following Haskell implementation of the well-known insertion-
sort algorithm:
isort :: Ord a => [a] -> [a]
isort [] = []
isort (x:xs) = ins x (isort xs)
where
ins y [] = [y]
ins y (z:zs)
| y <= z = y:z:zs | otherwise = z: (ins y zs) This function has the effect of sorting a list of items into increasing order. (Try it out on the lists [1,6,2,4,9,8] and "alphabetical order" to see what it does.) Your task: Write a Haskell function mySort :: Ord a => (a -> a -> Bool) -> [a] -> [a]
that provides a generalized version of isort: that is, mySort p xs sorts the
list xs according to the binary predicate p. For example, mySort (<=) xs
sorts xs in ascending order (just like the original isort!), whereas mySort
(>=) xs sorts xs in descending order. Here are some examples:
*Main > mySort (<=) [1,6,2,4,9,6,8] [1,2,4,6,6,8,9] *Main > mySort (>=) [1,6,2,4,9,6,8]
[9,8,6,6,4,2,1]
Spring 2017
Assignment 7 CIS 252 — Intro to Computer Science
*Main > mySort (<=) "alphabetical order" " aaabcdeehilloprrt" *Main > mySort (>=) “alphabetical order”
“trrpolliheedcbaaa ”
Note: Your code should be extremely similar to isort in structure: only
very minor additions/changes need to be made.
5. In mathematical parlance, a fixed point of a function f is a value v such
that f(v) = v. For example, the values 0 and 1 are both fixed points of the
function g(x) = x2, because g(0) = 0 and g(1) = 1. (In contrast, 2 is not a
fixed point of g(x) = x2, because g(2) = 4.)
Write a Haskell function
isFixPt :: Eq a => (a -> a) -> a -> Bool
such that isFixPt f val determines whether val is a fixed point of the
function f. Here are some examples:
*Main > isFixPt (x -> x*x) 0
True
*Main > isFixPt (x -> x*x) 1
True
*Main > isFixPt (x -> x*x) 2
False
*Main > isFixPt toUpper ’A’
True
*Main > isFixPt toUpper ’b’
False
*Main > isFixPt toUpper ’?’
True
6. Write a Haskell function
changeFirst :: (a -> Bool) -> a -> [a] -> [a]
such that changeFirst p val xs returns a list that looks like xs except
that the leftmost item in xs that satisfies predicate p is replaced by val.
(If none of the elements of xs satisfy p, then xs is returned.)
Here are some examples:
*Main > changeFirst even 33 [1,7,4,8,2]
[1,7,33,8,2]
*Main > changeFirst even 33 [1,7,9,5]
[1,7,9,5]
*Main > changeFirst isLower ’!’ “Syracuse”
“S!racuse”
*Main > changeFirst isLower ’!’ “SYRACUSE”
“SYRACUSE”
Spring 2017
