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,
all even [1..5] == False
all even [2,4,6] == True
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:
takeWhile (< 3) [1,2,3,4,1,2,3,4] == [1,2]
takeWhile (< 9) [1,2,3] == [1,2,3]
takeWhile (< 0) [1,2,3] == []
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:
foldr (+) 0 xs == sum xs
, for any list of numbers xs, andlet f i s = chr i : s in foldr f "" [65..70] == "ABCDE"
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:
zipWith (,) [1,2,3,4] ["a","b","c","d","e"] == [(1,"a"),(2,"b"),(3,"c"),(4,"d")]
zipWith (+) [1,2,3] [100,200,300,400] == [1001,2002,3003]
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
.
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)implement
maximumSegmentSum
using a combination of existing List functions.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.Implement a function
maximumSegSum
with direct recursion.Hopefully you can notice some commonality in the implementation of
maxPrefixSum
andmaxSegSum
. Exploit that to obtain a linear time implementationmaxSegSum
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:= (maxPrefixSum xs, maxSegSum xs) maxPrefixAndSegSum 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.
Write
countTrues
using direct recursion.Hint: Take another look at your implementation of
inits
first.Write
countTrues
using a combination of existing functions.Write
countTrues
using an accumulator so that your implementation runs in linear time.Write an alternative implementation of
countTrues
(not using an accumulator) that also runs in linear time.