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.

length = foldr f e
  where
    f _ r = 1 + r
    e     = 0

2 (++) atHome

Append two lists.

(++) xs ys = foldr f e xs
  where
    f x r = x:r
    e = ys

3 product atHome

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

product = foldr f e
  where
    f x r = x * r
    e     = 1

4 or atHome

or returns the disjunction of a Boolean list.

or = foldr f e
  where
    f x r = x || r
    e     = False

5 any atHome

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

any p = foldr f e
  where
    f x r = p x || r
    e     = False

6 all atHome

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

all p = foldr f e
  where
    f x r = p x && r
    e     = True

7 map inClass

map g = foldr f e
  where
    f x r = g x : r
    e     = []

8 reverse inClass

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

reverse = foldr f e
  where
    f x r = r ++ [x]
    e     = []

9 concat atHome

Concatenate a list of lists into a single list.

concat = foldr f e
  where
    f x r = x ++ r
    e     = []

10 concatMap inClass

Map a function over a list and concatenate the results.

concatMap g = foldr f e
  where
    f x r = g x ++ r
    e     = []

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

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

-- Observe that 'elem y = any (== y)' so this is basically the same as any:
elem y = foldr f e
  where
    f x r = (x == y) || r
    e = False

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:

filter p = foldr f e
  where
    f x r = if p x then x:r else r
    e = []

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

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

maybeLast = foldr f e
  where
    f x r = case r of
              Nothing -> Just x
              Just _  -> r
    e = Nothing

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)

partition p = foldr f e
  where
    f x (ts,fs) = if p x then (x:ts,fs) else (ts,x:fs)
    e = ([],[])

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.

unzip = foldr f e
  where
    f (a,b) (as,bs) = (a:as,b:bs)
    e = ([],[])

16 unlines :: [String] -> String atHome

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

unlines = foldr f e
  where
    f l r = l ++ "\n" ++ r
    e = []

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

nub = reverse . foldl f e where
    f r x | x `elem` r = r
          | otherwise  = x:r
    e = []

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.

union xs ys = foldr f e ys
  where
    f y r | y `elem` r  = r
          | otherwise   = r ++ [y]
    e = xs

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]

intersect ys xs = foldr f e ys
  where
    f y r | y `elem` xs = y:r
          | otherwise  = r
    e = []

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.

sort = foldr f e
  where
    f x r = insert x r
    e = []

21 null atHome

Test whether a list is empty.

null xs = foldr f e xs
  where
    f x r = False
    e     = True

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"

intersperse c = foldr f e
  where
    f x r = case r of
              [] -> [x]
              _  -> x : c : r
    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.

permutations :: [a] -> [[a]]
permutations = foldr f e
  where
    f x r = concatMap (insertEverywhere x) r
    e     = [[]]

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

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:

takeWhile p = foldr f e
  where
    f x r = if p x then x:r else []
    e = []

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

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

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

tails = foldr f e
  where
    f x r = case r of
              []     -> [x]:r
              (ys:_) -> (x:ys):r
    e = []

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

group = foldr f e
  where
    f x r = case r of
              [] -> [x]:r                                -- handling the base case
              (ys@(y:_):rs) | x == y    -> (x:ys):rs     -- append to current series
                            | otherwise -> [x]:r         -- start a new series
    e = []

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

scanr g z = foldr f e
  where
    f x r@(y:_) = g x y : r
    e = [z]

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.

mapAccumR g z = foldr f e
  where
    f x (ra,ry) = let (acc,y) = g ra x in (acc,y:ry)
    e = (z,[])