Week 11: Exercises

1. (->)

We saw in the lecture that [], Maybe and (,) are all instances of the Functor type class. Actually the type constructor (->) is also an instance. Investigate this. Specifically, how does fmap affect a function?

2. International Colors

Here are some association lists with colors in a few languages:

cz_colors :: [(String, String)]
cz_colors = [("red", "cerveny"), ("blue", "modry"), ("green", "zeleny")]

fr_colors :: [(String, String)]
fr_colors = [("red", "rouge"), ("blue", "bleu"), ("yellow", "jaune")]

Write a function fr_to_cz :: String -> Just String that maps a color name in French to its equivalent name in Czech, by translating through English if possible. If the name is absent in either dictionary, return Nothing.

3. Merging Files

Write a function merge :: String -> String -> String -> IO () that takes three filenames, which are the names of two input files and one output file. The input files are sorted files of integers, with one integer per line. The function should merge the contents of the files and write them to the output file, again with one integer per line. The files may be larger than available memory.

4. Permutations

Write a function permutations :: [a] -> [[a]] that returns a list of all permutations of a given list. Do not assume that the type a implements Eq.

5. Infinite Pairs

Write a function pairs that takes two lists L and M and produces a list of pairs (x, y) of elements where x ∈ L and y ∈ M. Every such pair must appear exactly once in the output list, even if both input lists are infinite.

6. Combinations

Write a function that takes an integer K and a list of length N, with K ≤ N. The function should return a list of all combinations of K elements of the list N.

7. Infinite Combinations

Wil your function from the previous exercise work even for an infinite input list? If not, modify it so that it will.

8. Subsets

Write a function that takes a finite list L representing a set of distinct elements, and returns a list of all subsets of L.

9. Finite Subsets

Write a function that takes a possibly infinite list L representing a set of distinct elements, and returns a list of all finite subsets of L.

10. Linear Congruential Generator

A linear congruential generator is a formula for generating a series of pseudorandom numbers. It has the form

X_n+1 = (a X_n + c) mod m

where X is the series of pseudorandom values, and a, c, and m are constants.

Use a linear congruential generator to construct an infinite list of values of type Double in the range from 0.0 to 1.0. Use the constants

• a = 1,664,525

• c = 1,013,904,223

• m = 2³²

11. Quickselect

Write a Haskell function median :: Ord a => [a] -> a that uses the Quickselect algorithm to find the median element of a list in time O(n) on average, where n is the length of the list. (If the list has an even number of elements, you may return either of the two elements that straddle the midpoint of the list.)