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.