Recursive Functions on Lists

After understanding polymorphic types, we will now put our newfound knowledge to use and write some more polymorphic list functions. We will cover the most important techniques used to write recursive functions on lists.

(Re-)Constructing lists

So far all of the list functions we have written (e.g. length, containsMatching) returned a single value, like an integer or a boolean. Such functions that reduce a list to a single value are called “folds” in functional programming.

However, many functions that work on lists will return lists themselves after transforming, filtering, or combining the input lists. Some examples are the take, drop, or the ++ and concat functions. We will now see how to write such functions that (re-)construct lists themselves.

As an example, let’s reimplement the ++ operator that appends two lists as a polymorphic function called append.

append :: [a] -> [a] -> [a]

The base case of append is when the first input list is the empty list. In that case, we can simply return the second input list.

append [] ys = ys

The interesting case is when the first list is a nonempty list x : xs. What do we want the result of append to look like? Certainly, the head of the result should be x. The tail of the result should contain the elements of xs followed by the elements of ys. In other words, the tail of the result should be xs appended to ys.

append (x:xs) ys = x:(append xs ys)

We used the : constructor on the right side here to implement the reasoning discussed above. The equation says that the head of the result is x, and the tail of the result is xs appended to ys.

During a call of append, the first input list is at first deconstructed in pattern matching and subsequently reconstructed as part of the result list. In total, if the first input list has n elements, we make n+1 calls to append in computing the result.

Exercise: List reconstruction

Implement a recursive function takeAsLong :: [a] -> (a -> Bool) -> [a]. It takes a list of elements of type a and a predicate of type a -> Bool.

takeAsLong xs test should take elements from xs until it encounters an element which does not fulfill the predicate. All elements up to, but excluding that element, should be returned.

For example takeAsLong [5, 7, 1, 4, 2] (>3) should return [5, 7], as the next element 1 does not match the predicate. If all elements of xs fulfill the predicate, then all of them should be returned.

As ...