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) partition :: (a → Bool) → [a] → ([a], [a])

Given a predicate and a list, return lists of elements that do and do not satisfy the predicate.

e) 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).

2. 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]

3. Maximum By

a) Write the following function (which is in Haskell's standard library in the Data.List module):

maximumBy :: (a → a → Ordering) → [a] → a

Compute the largest element of a list with respect to a comparison function.

For example:

> maximumBy (\s t -> compare (length s) (length t)) ["one", "fine", "day"]
"fine"

b) Write a function maxBy :: Ord b => (a -> b) -> [a] -> a that takes a function f and a list of values, and returns the value x for which f(x) is largest.

For example:

> maxBy length ["one", "fine", "day"]
"fine"

4. Folding Minus

Recall the description of the built-in functions foldl and foldr:

foldl :: (a → b → a) → a → [b] → a

Fold a list using a binary operator, from left to right. In the type signature above, a is the accumulator type and b is the list element type. The function passed to foldl takes the accumulator as its first argument, i.e. on the left.

foldr :: (b → a → a) → a → [b] → a

Reduce a list using a binary operator, from right to left. In the type signature above, a is the accumulator type and b is the list element type. The function passed to foldr takes the accumulator as its second argument, i.e. on the right.

What are the values of these expressions?

1. foldl (-) 0 [1, 2, 3]

2. foldr (-) 0 [1, 2, 3]

5. Writing Folds

Write the functions foldl and foldr.

6. Using Folds

Write the folowing functions using foldl or foldr:

1. map :: (a → b) → [a] → [b]

2. filter :: (a → Bool) → [a] → [a]

3. elem :: Eq a => a → [a] → Bool

4. reverse :: [a] → [a]

7. 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