Our final (for now) common list operation is the act of taking a list and applying a function that aggregates the values of our list. We've already seen an example of this: summing up things over a list. Here is a more general take on that again.
(: add-list (-> (Listof Number) Number))
(define (add-list lst)
(match lst
['() 0]
[(cons head tail)
(+ head (add-list tail))]))For another example, here is a function that concatenates the strings in a list into a single string.
(: concat-list (-> (Listof String) String))
(define (concat-list lst)
(match lst
['() ""]
[(cons head tail)
(string-append head (concat-list tail))]))We can see the basic structure: there is a base case for the empty list and a function application that combines the current element with the accumulated result of the recursive function call on the rest of the list. The result is a single value. This is generalized into the fold function.
(: foldr (All (S T) (-> (-> S T T) T (Listof S) T)))
(define (foldr f base lst)
(match lst
['() base]
[(cons head tail) (f head (foldr f base tail)]))The type for foldr is a bit more complicated than map or filter, so let's walk through it. foldr takes three things as input:
(-> S T T), which is the function that we want to use to "aggregate" or "fold" our list
T, which we use as our base case
(Listof S)
We can then use foldr in the following way. To replace add-list, we can write (foldr + 0 lst), and we would write (foldr string-append "" lst) to replace concat-list. Note that for fold, we need to provide a base case as well, since that depends on the function we want to do our folding with.
And as with the other cases, we can use our own functions too. For instance, we can rewrite points in the following way:
(: plot-point (-> (Pairof Integer Integer) Image Image))
;; Plots a point on the given image
(define (plot-point pt bg)
(match pt
[(Pairof x y)
(place-image (circle 2 'solid 'red)
x y
bg)]))
Then we can plot our list of points with
(foldr plot-point (empty-scene 100 100) pts)
Now, you might notice the function is called foldr rather than just fold. The reason for this is that the r stands for right, as in the direction. Why is that? If we think about what is going on, we can see that we begin applying our function once we reach the base case, which we often imagine as the right-most end of the list. In other words, we fold the list into one value from the right.
Let's take a step back and see what's happening mathematically. Suppose we have a sequence $a_0, a_1, \dots, a_n$, where each element is of type $A$ and we have a base case $b \in B$. We would like to apply a binary function $f : A \times B \to B$. Then foldr for this function looks like
\[f(a_0, f(a_1, f( \dots f(a_n,b) \dots ))).\]
But what if we didn't want to apply the function like that? What if we wanted to fold the list from left to right? In other words, what if we wanted to do the following? \[f(a_n, f(a_{n-1}, f( \dots f(a_0,b) \dots )))\]
First, why would we want to do this? After all, it doesn't really matter in which order we add things up: $1+2 = 2+1$, after all. Except that this isn't true for every function. For example, (string-append x y) and (string-append y x) are not guaranteed to be the same string.
Such functions are said to be non-commutative functions. We say that a function $f$ is commutative if for all $x,y$, $f(x,y) = f(y,x)$. In other words, a function is commutative if the order in which we take the arguments doesn't matter.
From this, we can see that, in theory, if we were to apply, say, string-append on our list from left to right, rather than right to left, we would get something different.
But how would we write such a function in practice? The trick is to provide the partial computation as part of the input. Consider the following variant of our concat-list function, which we'll cleverly call concat-listl.
(: concat-listl (-> (Listof String) String String))
(define (concat-listl lst acc)
(match lst
['() acc]
[(cons head tail)
(concat-listl tail (string-append head acc))]))In this version, the concatenation is being applied on the current element before proceeding to the rest of the list. We observe that what used to be the base case is now just holding the partial computation as we proceed down the list. We can take this as inspiration for the foldl function.
(: foldl (All (S T) (-> (-> S T T) T (Listof S) T)))
(define (foldl f base lst)
(match lst
['() base]
[(cons head tail) (foldl f (f head base) tail)]))It's interesting to observe that this version of fold is more similar to how we would typically think of an "iterative" process (as opposed to a recursive process): we perform a partial computation that gets closer and closer to our final result at each iteration.
Since + is commutative, both (foldr + 0 lst) and (foldl + 0 lst) will produce the same thing. This makes sense, since it doeson't really matter what order we choose to add numbers up in. But the results are different when we try to use string-append, as we'd argued.