Say we want to add a list of numbers together:
1 + 2 + 3 + 4.
This is a pretty common way to write it. But I wrote "add a list of numbers together" and not "write numbers with pluses in between." There is something fundamentally different in the way I expressed the operation in prose and the mathematical notation that I used. We do this because we know that this is the equivalent notation for addition (because it is commutative), and in our heads it immediately reduces to:
3 + 7.
and then
10.
So what is it? The problem is that we have no way to understand the idea of summation from this example. What if instead I wrote "Start at 0, and then take one item from the list at a time and add it to the starting value as the current amount"? In fact, this is what summation is about, and that he does not arbitrarily decide which two things to add first, until the equation is reduced.
sum(List) -> sum(List, 0). sum([], A) -> A; sum([H|T], A) -> sum(T, H + A).
If you are still with me, then you are ready to understand the folds.
There is a problem with the function above; it is too specific. He combines three ideas together without indicating independently:
- iteration
- accumulation
- Adding
It's easy to miss the difference between iteration and accumulation, because most of the time we never think about it. Most languages randomly encourage us to skip the difference, in fact, by having the same storage location change its value every iteration of a similar function.
It's easy to miss the independence of the add simply because of how it is written in this example, because the “+” looks like an “operation”, not a function.
What if I said: "Start with 1, then take one item from the list at a time and multiply it by the current value"? We will still process the list in exactly the same way, but with two examples for comparison it is clear enough that multiplication and addition are the only difference between them:
prod(List) -> prod(List, 1). prod([], A) -> A; prod([H|T], A) -> prod(T, H * A).
This is exactly the same thread of execution, but for the internal operation and the initial value of the battery.
So, let's add the add and multiply bits to the functions so that we can pull out this part of the template:
add(A, B) -> A + B. mult(A, B) -> A * B.
How can we write a list operation ourselves? We need to pass the function to - addition or multiplication - and get it to work on the values. In addition, we must pay attention to the identity of the type and action of the things we are working on, or we will ruin the magic, which is an aggregation of meanings. "add (0, X)" always returns X, so this idea (0 + Foo) is an join identity operation. When multiplying, the identification operation must be multiplied by 1. Therefore, we must start our drive at 0 for addition and 1 for multiplication (and for building lists, an empty list, etc.). Thus, we cannot write a function with a built-in battery value, because it will be correct only for some pairs of operations of type +.
So this means that to write the fold we need to have a list argument, a function for the argument argument, and a battery argument, for example:
fold([], _, Accumulator) -> Accumulator; fold([H|T], Operation, Accumulator) -> fold(T, Operation, Operation(H, Accumulator)).
With this definition, we can now write sum / 1 using this more general pattern:
fsum(List) -> fold(List, fun add/2, 0).
And prod / 1 also:
fprod(List) -> fold(List, fun prod/2, 1).
And they are functionally identical to the ones we wrote above, but the notation is more understandable, and we don’t need to write a bunch of recursive details that combine the idea of iteration with the idea of accretion with the idea of some like the operation of multiplication or addition.
In the case of the RPN calculator, the idea of aggregate list operations is combined with the concept of selective sending (choosing the operation to execute based on which character is encountered / matched). The RPN example is relatively simple and small (you can put all the code in your head at once, it’s just a few lines), but until you get used to the functional paradigms, the process that it shows can hurt you. In functional programming, tiny code can create an arbitrarily complex process of unpredictable (or even evolving!) Behavior, based only on list operations and selective sending; this is very different from conditional checks, input verification methods, and procedural checks used in other paradigms that are more common today. The analysis of such behavior is greatly facilitated by single assignment and recursive notation, since each iteration is a conceptually independent slice of time that can be viewed in isolation from the rest of the system. I am a little ahead of the main question, but this is the main idea that you might want to consider when you consider why we like to use operations such as folds and recursive notations instead of multi-assignment procedural loops.
Hope this helped more than embarrass.