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

concat []       = []
concat (xs:xss) = xs ++ concat xss

3 atHome

and :: [Bool] -> Bool

and returns the conjunction of a Boolean list.

and []     = True
and (x:xs) = x && and xs

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 _ []     = True
all p (x:xs) = p x && all p xs

6 atHome

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

map _ []     = []
map f (x:xs) = f x : map f xs

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)

partition _ []                 = ([],[])
partition p (x:xs) | p x       = let (ts,fs) = partition p xs in (x:ts,  fs)
                   | otherwise = let (ts,fs) = partition p xs in (  ts,x:fs)

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.

insert q [] = [q]
insert q (x:xs) | q > x     = x : insert q xs
                | otherwise = q : x : xs

14 atHome

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

The sort function implements a sorting algorithm.

sort []     = []
sort (x:xs) = insert x (sort xs)

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.

take          :: Int -> [a] -> [a]
take 0 _      = []
take n []     = []
take n (x:xs) = x : take (n-1) xs

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 _ []                 = []
takeWhile p (x:xs) | p x       = x : takeWhile p xs
                   | otherwise = []

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

group []     = []
group (x:xs) = case group xs of
                 []                        -> [[x]]
                 (ys@(y:_):rs) | x == y    ->      (x:ys) : rs
                               | otherwise -> [x] :    ys : rs

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]

remSuccessiveduplicates []                   = []
remSuccessiveduplicates [x]                  = [x]
remSuccessiveduplicates (x:y:xs) | x == y    = remsuccessiveduplicates (y:xs)
                                 | otherwise = x : remsuccessiveduplicates (y:xs)

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

nub l                   = nub' l [] where
    nub' [] _           = []
    nub' (x:xs) seen
        | x `elem` seen   = nub' xs seen
        | otherwise     = x : nub' xs (x:seen)

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.

maybeLast []     = Nothing
maybeList (x:xs) = case maybeList xs of
                     Nothing -> Just x
                     jl      -> jl

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

insertEverywhere             :: a -> [a] -> [[a]]
insertEverywhere x []        = [[x]]
insertEverywhere x xs@(y:ys) = (x:xs) : map (y:) (insertEverywhere x ys)

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.

permutations        :: [a] -> [[a]]
permutations []     = [[]]
permutations (x:xs) = concatMap (insertEverywhere x) $ permutations xs

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 _ z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

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.

scanr _ z []     = [z]
scanr f z (x:xs) = let rs@(r:_) = scanr f z xs
                   in f x r : rs

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

encode        :: Eq a => [a] -> [(Int,a)]
encode []     = []
encode (x:xs) = case encode xs of
                  []                       -> [(1,x)]
                  r@((i,y):ys) | x == y    -> (i+1,x) : ys
                               | otherwise -> (1,x)   : r

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]

decode :: [(Int,a)] -> [a]
decode = concatMap (\(i,x) -> replicate i x)
  where
    replicate 0 _ = []
    replicate i x = x : replicate (i-1) x
    -- replicate is actually already defined in the Prelude.

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.

-- | splitAt splits off the first i elements. Returns all elements in
-- the first list if there are fewer than i elements.
splitAt          :: Int -> [a] -> ([a],[a])
splitAt 0 xs     = ([],xs)
splitAt i []     = ([],[])
splitAt i (x:xs) = let (ys,rest) = splitAt (i-1) xs
                   in (x:ys,rest)

splitAll      :: Int -> [a] -> [[a]]
splitAll i xs = case splitAt i xs of
                  (ys,[])   -> [ys]
                  (ys,rest) -> ys : splitAll i rest

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 f (x:xs) (y:ys) = (f x y) : zipWith f xs ys
zipWith _ _      _      = []

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.

-- The main work is done here; we consider the first row separately,
-- transpose the rest of the matrix (without its first row), and then
-- cons the elements from the first row onto the result.
--
-- If there are no rows left we generate sufficiently many (infinitely
-- many) empty rows that this consing/combining described above is
-- successful. The zipWith function will just truncate the empty
-- leftover rows generated.
transpose' (xs:xss) = zipWith (:) xs (transpose' xss)
transpose' []       = repeat []

-- The above function transpose' transposes non-empty matrices. But
-- when the matrix empty at the very start we get this infinite list
-- of empty lists instead. We should fix that:
transpose [] = []
transpose xs = transpose' xs

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)

    segments :: [Int] -> [[Int]]
segments = ([] :) . concatMap (tail . List.inits) . List.tails

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

    maxSegSumSpec = maximum . map sum . segments

  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.

    maxPrefixSum        :: [Int] -> Int
maxPrefixSum []     = 0
maxPrefixSum (x:xs) = 0 `max` (x + maxPrefixSum xs)

  4. Implement a function maximumSegSum with direct recursion.

    maxSegSum []     = 0
maxSegSum (x:xs) = maxSegSum xs `max` (x + maxPrefixSum xs)

  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)
    maxPrefixAndSegSum        :: [Int] -> (Int,Int)
maxPrefixAndSegSum []     = (0,0)
maxPrefixAndSegSum (x:xs) = let (maxPrefix,maxSeg) = maxPrefixAndSegSum xs
                                candidatePrefix    = x + maxPrefix
                            in (0       `max` candidatePrefix
                               , maxSeg `max` candidatePrefix
                               )

maxSegSum :: [Int] -> Int
maxSegSum = snd . maxPrefixAndSegSum

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.

    countTrues            :: [Bool] -> [Int]
countTrues []         = [0]
countTrues (True:bs)  = 0 : map (+1) (countTrues bs)
countTrues (False:bs) = 0 : countTrues bs

  2. Write countTrues using a combination of existing functions.

    countTrues    :: [Bool] -> [Int]
countTrues bs = map (length . filter (== True)) . inits $ bs

-- note that we can eta-reduce to
countTrues :: [Bool] -> [Int]
countTrues = map (length . filter (== True)) . inits

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

    countTrues :: [Bool] -> [Int]
countTrues = count [0]
  where
    -- invariant: count acc xs == (reverse acc) ++ countTrues xs
    count acc          []        = reverse acc
    count acc@(cur:_) (True:bs)  = count (cur+1 : acc) bs
    count acc@(cur:_) (False:bs) = count (cur   : acc) bs

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

    countTrues :: [Bool] -> [Int]
countTrues = reverse . count . reverse
  where
    count []         = [0]
    count (True :bs) = let res@(cur:_) = count bs in cur + 1 : res
    count (False:bs) = let res@(cur:_) = count bs in cur     : res