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.

length

length returns the length of a finite list.

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

(++)

Append two lists.

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

product

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

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

or

or returns the disjunction of a Boolean list.

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

any

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

all

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

map

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

reverse

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

concat

Concatenate a list of lists into a single list.

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

concatMap

Map a function over a list and concatenate the results.

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

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

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

filter

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]

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

maybeLast :: [a] -> Maybe a

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

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 p = foldr f e
  where
    f x (ts,fs) = if p x then (x:ts,fs) else (ts,x:fs)
    e = ([],[])

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

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 = ([],[])

unlines :: [String] -> String

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

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 = reverse . foldl f e where
    f r x | x `elem` r = r
          | otherwise  = x:r
    e = []

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.

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

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]

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

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

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

null

Test whether a list is empty.

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

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"

intersperse c = foldr f e
  where
    f x r = case r of
              [] -> [x]
              _  -> x : c : r
    e     = []

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

takeWhile

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

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

tails :: [a] -> [[a]]

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

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

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

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

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.

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

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

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