Fold Exercises

Write the following functions using the foldr or foldl function. If no type signature is given, also give the type of the function.

A good strategy to get started is to first write the function using explicit recursion, and then somewhat mechanically convert it to using foldr or foldl.

1 length atHome

length returns the length of a finite list.

2 (++) atHome

Append two lists.

3 product atHome

The product function computes the product of a finite list of numbers.

4 or atHome

or returns the disjunction of a Boolean list.

5 any atHome

Applied to a predicate and a list, any determines if any element of the list satisfies the predicate.

6 all atHome

Applied to a predicate and a list, all determines if all elements of the list satisfy the predicate.

7 map inClass

8 reverse inClass

reverse xs returns the elements of xs in reverse order. xs must be finite.

9 concat atHome

Concatenate a list of lists into a single list.

10 concatMap inClass

Map a function over a list and concatenate the results.

11 elem :: Eq a => a -> [a] -> Bool atHome

elem is the list membership predicate, usually written in infix form, e.g., x `elem` xs.

12 filter atHome

filter, applied to a predicate and a list, returns the list of those elements that satisfy the predicate; i.e.,

filter p xs = [ x | x <- xs, p x] :atHome:

13 maybeLast :: [a] -> Maybe a atHome

Extract the last element of a list. Returns Nothing if the list is empty.

14 partition inClass

The partition function takes a predicate a list and returns the pair of lists of elements which do and do not satisfy the predicate, respectively; i.e.,

partition p xs == (filter p xs, filter (not . p) xs)

15 unzip :: [(a, b)] -> ([a], [b]) atHome

unzip transforms a list of pairs into a list of first components and a list of second components.

16 unlines :: [String] -> String atHome

unlines is an inverse operation to lines. It joins lines, after appending a terminating newline to each.

17 nub atHome

The nub function removes duplicate elements from a list. In particular, it keeps only the first occurrence of each element. (The name nub means `essence’.)

18 union :: Eq a => [a] -> [a] -> [a] atHome

The union function returns the list union of the two lists. For example,

"dog" `union` "cow" == "dogcw"

Duplicates, and elements of the first list, are removed from the the second list, but if the first list contains duplicates, so will the result.

19 intersect :: Eq a => [a] -> [a] -> [a] inClass

The intersect function takes the list intersection of two lists. For example,

[1,2,3,4] `intersect` [2,4,6,8] == [2,4]

If the first list contains duplicates, so will the result.

[1,2,2,3,4] `intersect` [6,4,4,2] == [2,2,4]

20 sort :: Ord a => [a] -> [a] atHome

The sort function implements a stable sorting algorithm.

You can assume that there is a function insert :: Ord a => a -> [a] -> [a] that takes an element and a list and inserts the element into the list at the last position where it is still less than or equal to the next element.

21 null atHome

Test whether a list is empty.

22 intersperse atHome

The intersperse function takes an element and a list and `intersperses’ that element between the elements of the list. For example,

intersperse ',' "abcde" == "a,b,c,d,e"

23 permutations :: [a] -> [[a]] challenging atHome

The permutations function returns the list of all permutations of the argument. E.g.:

permutations "abc" == ["abc","bac","bca","acb","cab","cba"]

Note that it is ok if your solution returns the permutations in any order. E.g.

permutations "abc" == ["abc","bac","cba","bca","cab","acb"]

is also correct.

24 takeWhile atHome

takeWhile, applied to a predicate p and a list xs, returns the longest prefix (possibly empty) of xs of elements that satisfy p:

25 tails :: [a] -> [[a]] inClass

The tails function returns all final segments of the argument, longest first. For example,

tails "abc" == ["abc", "bc", "c",""]

26 group :: Eq a => [a] -> [[a]] challenging inClass

The group function takes a list and returns a list of lists such that the concatenation of the result is equal to the argument. Moreover, each sublist in the result contains only equal elements. For example,

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

27 scanr :: (a -> b -> b) -> b -> [a] -> [b] atHome

scanr is similar to foldr but returns a list of successive reduced values from the right:

scanr g z [x_1, x_2, .., x_n] == [x_1 `g` .., .., x_(n-1) `g` z ,x_n `g` z,z]

That is, it also returns all intermediate answers of a foldr. Note in particular that

head (scanr g z xs) == foldr g z xs :athome

28 mapAccumR :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y]) atHome

The mapAccumR function behaves like a combination of map and foldr; it applies a function to each element of a list, passing an accumulating parameter from right to left, and returning a final value of this accumulator together with the new list.