Recursion on Lists

Implement the following functions using direct recursion. If no type signature is given, also give the type of the function. Note that these functions are actually all available in the standard library in the module Data.List.

1 atHome

product :: Num a => [a] -> a

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

2 atHome

concat

Concatenate a list of lists into a single list

3 atHome

and :: [Bool] -> Bool

and returns the conjunction of a Boolean list.

4 inClass

or :: [Bool] -> Bool

or returns the disjunction of a Boolean list.

5 inClass

all

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

6 atHome

map :: (a -> b) -> [a] -> [b]

7 atHome

intersperse

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"

8 atHome

concatMap

Map a function over a list and concatenate the results.

9 atHome

unlines :: [String] -> String

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

10 inClass

filter :: (a -> Bool) -> [a] -> [a]

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]

11 inClass

partition

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)

12 atHome

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

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

13 atHome

insert :: Ord a => a -> [a] -> [a]

The insert function takes an element and a (sorted) list and inserts the element into the list at the last position where it is still less than or equal to the next element.

14 atHome

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

The sort function implements a sorting algorithm.

15 atHome

take

take i returns the first i elements from the input list. If the list has fewer than i elements, the entire input list is returned.

16 atHome

takeWhile :: (a -> Bool) -> [a] -> [a]

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

17 inClass

group

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"]

18 atHome

remSuccessiveduplicates

The function remSuccessiveDuplicates removes succesive repeated elements from a list. For example

remSuccessiveduplicates [1, 2, 2, 3, 2, 4] == [1, 2, 3, 2, 4]

19 atHome

nub

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

20 atHome

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

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.

21 atHome

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

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]

22 atHome

maybeLast :: [a] -> Maybe a

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

23 atHome challenging

insertEverywhere

insertEverywhere x ys “inserts” x at every position in the list ys. I.e.:

insertEverywhere 10 [1..5] == [[10,1,2,3,4,5],[1,10,2,3,4,5],[1,2,10,3,4,5],[1,2,3,10,4,5],[1,2,3,4,10,5],[1,2,3,4,5,10]]

24 atHome challenging

permutations :: [a] -> [[a]]

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.

25 inClass challenging

foldr :: (a -> b -> b) -> b -> [a] -> b

The function foldr takes a function ‘f’ and an unit element ‘z’ and “combines” all elements in the list using the function ‘f’, and starting from value ‘z’.

Your implementation should satisfy:

26 atHome

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

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

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

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

head (scanr f z xs) == foldr f z xs.

27 atHome

run length encoding: encode

The function encode computes the run-length encoding of a list. That is, the list is mapped to a list of pairs whose first element says how many times the second component of the pair appears in adjacent positions in the list. For example:

encode [1, 2, 2, 3, 2, 4] == [(1, 1),(2, 2),(1, 3),(1, 2),(1, 4)]

28 atHome

run length encoding: decode

Given a run length encoded list, decode produces the original input list, e.g. from the example above:

decode [(1, 1),(2, 2),(1, 3),(1, 2),(1, 4)] == [1, 2, 2, 3, 2, 4]

29 inClass

splitAll :: Int -> [a] -> [[a]]

The splitAll function divides the given list in sublists, where the sublists have the given length. Only the last list might be shorter. For example,

splitAll 3 [1..11] == [[1,2,3],[4,5,6],[7,8,9],[10,11]]

Hint: Try to think of a simpler problem first, and write a helper function that solves this simpler problem.

30 atHome

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

zipWith combines two lists into a single list, by pairwise applying the given function. I.e. if f is the supplied function, and x and y are the \(i^\mathrm{th}\) elements in the first and second list, respectively, the \(^i\mathrm{th}\) element in the output list is f x y. If the lists have different length, the lengths are truncated to the shortest list. For example:

31 atHome challenging

transpose :: [[a]] -> [[a]]

Transposes a matrix (represented by a list of equally long lists). That is, the function transpose :: [[a]] -> [[a]] which maps the \(i^\mathrm{th}\) element of the \(j^\mathrm{th}\) list to the \(j^\mathrm{th}\) element of the \(i^\mathrm{th}\) list.

Hint: make use of the function zipWith.

32 Maximum Segment Sum atHome challenging

Given a list of numbers, we define a segment as a contiguous sublist. For example [2,3,4] is a segment of l=[1,2,3,4,5,6] but [2,4,6] is not a segment of l. The sum of a segment is the value we obtain by summing all values in a segment, and the maximum segment sum of l is the maximum sum over all possible segments of l.

  1. Write the function segments that computes all segments of a list by combine existing functions from Data.List (which you have re-implemented in the exercises above)

  2. implement maximumSegmentSum using a combination of existing List functions.

  3. The above implementation is simple, but actually very slow (\(O(n^3)\) time). With a bit of work we can derive a linear time implementation instead!

    Write, using direct recursion, a function maxPrefixSum that computes the maximum among all prefixes of a list.

  4. Implement a function maximumSegSum with direct recursion.

  5. Hopefully you can notice some commonality in the implementation of maxPrefixSum and maxSegSum. Exploit that to obtain a linear time implementation maxSegSum for the maximum segment sum.

    Hint: Write a function maxPrefixAndSegSum : [Int] -> (Int,Int) that simultaneously computes the maximum prefix sum and the maximum segment sum. I.e. Your function should satisfy the specification:

    maxPrefixAndSegSum xs = (maxPrefixSum xs, maxSegSum xs)

33 atHome

Let countTrues :: [Bool] -> [int] be a function such that countTrues bs computes, for each prefix of the list bs, the number of True s in the list.

  1. Write countTrues using direct recursion.

    Hint: Take another look at your implementation of inits first.

  2. Write countTrues using a combination of existing functions.

  3. Write countTrues using an accumulator so that your implementation runs in linear time.

  4. Write an alternative implementation of countTrues (not using an accumulator) that also runs in linear time.