Week 8: Exercises

1. List Functions

Write the following functions, which all belong to Haskell's standard library:

a) iterate :: (a → a) → a → [a]

Return an infinite list generated by applying a function repeatedly:

iterate f x = [x, f x, f (f x), ...]

b) takeWhile :: (a → Bool) → [a] → [a]

Return the longest prefix of elements that all satisfy a predicate.

c) find :: (a → Bool) → [a] → Maybe a

Return the first element in the list that satisfies the given predicate, or Nothing if there is none.

d) span :: (a → Bool) → [a] → ([a], [a])

Split a list into two lists using a predicate p. (span p l) is equivalent to (takeWhile p l, dropWhile p l).

e) elemIndex :: Eq a => a → [a] → Maybe Int

Return the index of the first element in the given list that is equal to the query element, or Nothing if there is no such element. Elements are indexed starting from 0.

f) maybe :: b -> (a -> b) -> Maybe a -> b

This function takes a default value, a function f, and a Maybe value. If the Maybe value is Nothing, it returns the default value. Otherwise, it applies f to the value inside the Maybe and returns the result.

g) group :: Eq a => [a] → [[a]]

Group adjacent identical elements into sublists. For example,

group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]

2. Currying and Uncurrying

A curried function takes its arguments one at a time:

> sum 3 4
7

An uncurried function takes its arguments in a tuple:

> sum (3, 4)
7

Write a function curry that converts an uncurried function of two arguments to a curried function, and a function uncurry that performs the inverse transformation.

3. Alternating Map

Write a function altMap that takes two functions and a list. altMap should apply the two functions alternately to list elements. For example:

altMap (\i -> i + 1) (\i -> i - 1) [1..8] == [2, 1, 4, 3, 6, 5, 8, 7]

4. Common Words

Write a function commonWords :: Int -> String -> String that takes an integer N and a string text, and returns a string describing the N most frequent words in the text. Each line in the output string should contain a word and its count, separated by a space. Convert all words to lowercase.

For example, the output string might look like this:

the 23
a 18
for 15
we 10
horse 6
mill 3

5. Pythagorean Triples

Write a function triples that takes an integer N and returns a list of integer triples (a, b, c) with 0 < a < b < c ≤ N such that a² + b² = c². If two triples are multiples of each other (e.g. (3, 4, 5) and (6, 8, 10)), only the smaller of them (e.g. (3, 4, 5)) should appear in the list.

> triples 15
[(3,4,5),(5,12,13)]