When we introduced polymorphism, we noted that many of the types we were defining were essentially the same. That is, a binary tree containing integers is not really any structurally different from a binary tree containing strings or a binary tree containing integers. We sought a way to generalize or abstract the structure, so that we could define a "generic" tree once that we could use in many different contexts.
If we take a look at, say, the binary tree functions that we wrote, we will notice that there are many structural similarities. We find the same structures and patterns in our functions that operate on lists too. We notice that these functions are not substantially different from each other. In many cases, they differ from each other in only one spot. What we would like to do is apply the same idea behind abstracting structures into polymorphic structures, but for list functions.
We can try to describe the operations we use to compute with and manipulate lists more generally. For instance, one operation we've seen was the idea of creating a list of values based on the application of a function to the values in some given list. An example of this is our strings-lengths function:
(: strings-lengths (-> (Listof String) (Listof Integer)))
;; Given a list of strings, computes a list with each string's length
(define (first-letter t)
(match t
['() '()]
[(cons first rest) (cons (string-length first)
(strings-lengths rest))]))
Here's another simple example. Suppose I have a list of integers which represent "red" values in an RGB colour. I would like to create a square of the corresponding shade of red for each integer. We get the following:
(: red-squares (-> (Listof Byte) (Listof Image)))
;; Produce a list with a square with colour red from each number
;; from the given list
(define (red-squares lst)
(match lst
['() '()]
[(cons head tail) (cons (square 50 'solid (color head 0 0))
(red-squares tail))]))
Observe that, for the most part, our functions look almost identical. In fact, the only difference in each case is the application of our function. This seems like a natural place to generalize this kind of function.
(: map (All (S T) (-> (-> S T) (Listof S) (Listof T))))
(define (map f lst)
(match lst
['() '()]
[(cons head tail) (cons (f head) (map f tail))]))This is called map because it applies the given function to each element of the list, mapping each element from the old list to the new list. map takes two inputs, a function of type (-> S T) and a (Listof S), and produces a (Listof T).
We can rewrite each of the functions above using map. For instance, we can replace the entire function definition of strings-lengths with a function call to (map string-length strs), where strs is our list of strings.
We can also do this with functions that are not built-in. For instance, to replicate the function red-squares, we can call
(map red-square lst), where red-square is defined in the following.
(: red-square (-> Byte Image))
;; Draws a square with colour (x 0 0)
(define (red-square x)
(square 50 'solid (color x 0 0)))When viewed like this, it's clear that map is a very fundamental operation on lists. In fact, it is so fundamental that it is provided by Racket! So we didn't actually need to write it ourselves, but looking back, doing it ourselves wasn't so bad, was it?
Another common operation on lists is to create a list based on values of a list which satisfy a certain condition. We've already seen an example of this:
(: lte140 (-> (Listof Integer) (Listof Integer)))
;; Given a list of integers, produce a list with only those
;; integers that are at most 140
(define (lte140 ns)
(match ns
['() '()]
[(cons f r) (if (<= f 140)
(cons f (lte140 r))
(lte140 r))]))
This function takes a list of integers and produces a list with only those integers that are less than 140. This is another common pattern: filtering a list so that it contains only those values that satisfy a particular condition. This condition can be expressed as a Boolean function, called a predicate. This pattern can be implemented as the filter function.
(: filter (All (A) (-> (-> A Boolean) (Listof A) (Listof A))))
(define (filter pred lst)
(match lst
['() '()]
[(cons head tail) (if (pred head)
(cons head (filter pred tail))
(filter pred tail))]))Like map, filter is provided by Racket, so we don't need to write it ourselves. However, it is evidently not too difficult to reproduce.
Let's examine the type for filter. Here, we see that it takes two arguments: a Boolean function (that is, a function of type (-> A Boolean) and a list (specifically, a (Listof A). Note that the Boolean function must take values of type A, which is the type of the given list, and the result is also a list of the same type, A.
Now, one of the complications of this is that unlike with map, where our thought process typically begins with trying to apply a function we likely already have to the list, predicates are often something that are not provided for us. In other words, we often have to turn the predicates into functions, like so.
(: is-lte-140? (-> Integer Boolean))
;; Determine if the given integer is at most 140
(define (is-lte-140? n)
(<= n 140))Once we do this, we can use filter with the function with (filter is-lte-140? lst).
Now, one thing you might wonder about is what the point of filter is if we have to write this function anyway. After all, it's not that hard to write the recursive code at this point. With the work of coming up with a name, purpose, type ascription, and tests, it seems like we didn't save any work by using filter. And that's probably correct. But, there is something coming soon that we'll be covering that will make the use of filter much more convenient, so look forward to that.