Week 10: Exercises

1. map

map maps a function over a list:

> map (\i -> i * i) [2 .. 4]
[4,9,16]

1. What is the type of map?

2. Write map recursively.

3. Write map using foldr.

2. takeWhile

takeWhile returns the longest prefix of elements that satisfy a predicate:

> takeWhile (\i -> i * i < 30) [1 ..]
[1,2,3,4,5]

1. What is the type of takeWhile?

2. Write takeWhile recursively.

3. Write takeWhile using foldr.

3. Left Shift

Define a function

lshift:: Int -> String –> String

such that lshift n string cyclically shifts a given string

• by n positions to the left if n is positive

• by |n| positions to the right if n is negative

The function should work correctly even when |n| exceeds the list length.

> lshift 2 "abcde"
"cdeab"
> lshift (-1) "abcde"
"eabcd"
> lshift (-11) "abcde"
"eabcd"

4. Combinations

Write a function combinations :: Int -> [a] -> [[a]] 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.

5. 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 = 6,364,136,223,846,793,005

• c = 1,442,695,040,888,963,407

• m = 2⁶⁴

6. 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, numbered 0, 1, ..., 2n - 1, you may return either element (n - 1) or element (n), i.e. either of the two elements that straddle the midpoint of the list. Use the stream of pseudorandom numbers that you constructed in the previous exercise.