recursionfunctional-programmingerlangtail-recursionfold# Explanation of lists:fold function

I learning more and more about Erlang language and have recently faced some problem. I read about `foldl(Fun, Acc0, List) -> Acc1`

function. I used learnyousomeerlang.com tutorial and there was an example (example is about Reverse Polish Notation Calculator in Erlang):

```
%function that deletes all whitspaces and also execute
rpn(L) when is_list(L) ->
[Res] = lists:foldl(fun rpn/2, [], string:tokens(L," ")),
Res.
%function that converts string to integer or floating poitn value
read(N) ->
case string:to_float(N) of
%returning {error, no_float} where there is no float avaiable
{error,no_float} -> list_to_integer(N);
{F,_} -> F
end.
%rpn managing all actions
rpn("+",[N1,N2|S]) -> [N2+N1|S];
rpn("-", [N1,N2|S]) -> [N2-N1|S];
rpn("*", [N1,N2|S]) -> [N2*N1|S];
rpn("/", [N1,N2|S]) -> [N2/N1|S];
rpn("^", [N1,N2|S]) -> [math:pow(N2,N1)|S];
rpn("ln", [N|S]) -> [math:log(N)|S];
rpn("log10", [N|S]) -> [math:log10(N)|S];
rpn(X, Stack) -> [read(X) | Stack].
```

As far as I understand `lists:foldl`

executes `rpn/2`

on every element on list. But this is as far as I can understand this function. I read the documentation but it does not help me a lot. Can someone explain me how `lists:foldl`

works?

Solution

Let's say we want to add a list of numbers together:

```
1 + 2 + 3 + 4.
```

This is a pretty normal way to write it. But I wrote "add a list of numbers together", not "write numbers with pluses between them". There is something fundamentally different between the way I expressed the operation in prose and the mathematical notation I used. We do this because we know it is an equivalent notation for addition (because it is commutative), and in our heads it reduces immediately to:

```
3 + 7.
```

and then

```
10.
```

So what's the big deal? The problem is that we have no way of understanding the idea of *summation* from this example. What if instead I had written "Start with 0, then take one element from the list at a time and add it to the starting value as a running sum"? This is actually what summation is about, and it's not arbitrarily deciding 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're with me so far, then you're ready to understand folds.

There is a problem with the function above; it is *too specific*. It braids three ideas together without specifying any independently:

- iteration
- accumulation
- addition

It is easy to miss the difference between iteration and accumulation because most of the time we never give this a second thought. Most languages accidentally encourage us to miss the difference, actually, by having the same storage location change its value each iteration of a similar function.

It is easy to miss the independence of addition merely because of the way it is written in this example because "+" looks like an "operation", not a function.

What if I had said "Start with 1, then take one element from the list at a time and multiply it by the running value"? We would still be doing the list processing in exactly the same way, but with two examples to compare it is pretty clear that multiplication and addition are the only difference between the two:

```
prod(List) -> prod(List, 1).
prod([], A) -> A;
prod([H|T], A) -> prod(T, H * A).
```

This is exactly the same flow of execution but for the inner operation and the starting value of the accumulator.

So let's make the addition and multiplication bits into functions, so we can pull that part of the pattern out:

```
add(A, B) -> A + B.
mul(A, B) -> A * B.
```

How could we write the list operation on its own? We need to pass a function in -- addition or multiplication -- and have it operate over the values. Also, we have to pay attention to the *identity* of the *type* and *operation* of things we are operating on or else we will screw up the magic that is value aggregation. "add(0, X)" always returns X, so this idea (0 + Foo) is the *addition identity operation*. In multiplication the identity operation is to multiply by 1. So we *must* start our accumulator at 0 for addition and 1 for multiplication (and for building lists an empty list, and so on). So we can't write the function with an accumulator value built-in, because it will only be correct for some type+operation pairs.

So this means to write a fold we need to have a list argument, a function to do things argument, and an accumulator argument, like so:

```
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 mul/2, 1).
```

And they are functionally *identical* to the one we wrote above, but the notation is more clear and we don't have to write a bunch of recursive details that tangle the idea of iteration with the idea of accumulation with the idea of some specific operation like multiplication or addition.

In the case of the RPN calculator the idea of aggregate list operations is combined with the concept of selective dispatch (picking an operation to perform based on what symbol is encountered/matched). The RPN example is relatively simple and small (you can fit all the code in your head at once, it's just a few lines), but until you get used to functional paradigms the process it manifests can make your head hurt. In functional programming a tiny amount of code can create an arbitrarily complex process of unpredictable (or even evolving!) behavior, based just on list operations and selective dispatch; this is very different from the conditional checks, input validation and procedural checking techniques used in other paradigms more common today. Analyzing such behavior is *greatly* assisted by single assignment and recursive notation, because each iteration is a conceptually independent *slice of time* which can be contemplated in isolation of the rest of the system. I'm talking a little ahead of the basic question, but this is a core idea you may wish to contemplate as you consider *why* we like to use operations like folds and recursive notations instead of procedural, multiple-assignment loops.

I hope this helped more than confused.

- Recursively merge two associative 2d arrays
- Jinja templating with recursive in dict doesn't works
- Trace a recursive method
- JS - recursive function on multidimensional array to filter out only "checked" items (and its parents if a child is selected)
- Codility OddOccurrencesInArray Problem - Recursion and Python
- Check if a multidimensional array has any non-empty leaf nodes
- Is this a top down or bottom up recursion
- Convert recursion to iteration
- Space complexity for recursive calls on binary search tree
- Real-world examples of recursion
- How to obtain n-th even triangle number using recursive algorithm
- ArrayIndexOutOfBoundsException while walking 2D array recursively to solve a maze
- Is such a function structure tail recursive?
- Flatten multidimensional array 1 level php
- extract list from cell and add new rows to a df
- Fastest way to divide a 2D array in python into counterclockwise patches
- Merge two associative multidimensional arrays
- Octree implementation in Rust: why is the insert function duplicating insertions and how could I go about fixing this?
- convert binary to decimal using single linked list and recursive method in java
- How to use recursive SQL to find the parent ID
- Recursion function for counting the number of digits in a number?
- C# Dictionary recursion
- How to transform flat array to a list of hierarchical trees based on a field with a list of enums denoting the level
- How can I Create folders recursively in Delphi?
- What is the difference between divide and conquer, and branch and reduce?
- Linked-list population via recursion in C++
- How to calculate a unit price with a recursive Tree structure in a database
- Fastest way to combine image patches given as 4D array in python
- Recursively replace empty arrays with their key
- Are there any examples of mutual recursion?