[SOLVED] 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 seewhat it does.)Your task: Write a Haskell functionmySort :: 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 (<=) xssorts 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