While working though Structure and Interpretation of Computer Programs, I came across the definition of the foldright
function:
Exercise 2.38: The accumulate procedure is also known as foldright, because it combines the first element of the sequence with the result of comining all the elements to the right.
I have trouble with purely verbal explanations of things, I prefer notation and diagrams whenever appropriate. In exercise 2.38, the authors give a definition of foldleft
in Scheme:
1 2 3 4 5 6 7 

And using foldright
(accumulate) from earlier in the text:
1 2 3 4 5 

To show that foldleft and foldright are different, the authors ask for the values of:
1 2 3 4 5 

However, that does not show why they are different. To get a better understanding of why these functions are different, I used a feature of Scheme called quasiquoting, it’s similar to quoting, but allows for partial evaluation, I’ll explain with an example:
1 2 3 4 5 

Quoting returns the expression itself, not the value it evaulates to. Quasiquoting returns the expression itself, after evaluating all the expressions after commas.
So, to study the (foldright / 1 (list 1 2 3))
and (foldleft / 1 (list 1 2 3))
computations, we can redefine /
to use quasiquoting, and prevent the scheme interpreter from evaluating it all the way down to a number. Instead of (/ 1 2)
evaluating to 1/2
, we want it to evaluate to (/ 1 2)
.
1


Then, recompute the values:
1 2 3 4 5 

This expanded view makes it very clear how these functions are different. It also suggests that they are different only for nonassociative operators.
Here’s another example of quasiquoting that is useful for visualizing the recursive structure of a computation.