# 程序代写代做代考 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