Fold section - relating it to map

[EdmundsEcho]

A great place to learn about fold is in a paper called “Why FP Matters”. In a nutshell, fold is the universal constructor because it has the power to take a collection to a single value. An accumulator is always at least conceptually involved. The closely related map function can be implemented using fold. So fold is all you need to reproduce map. In the map case the accumulator is the same collection type as the original collection (e.g., Vec<T> -> Vec<U>). The fold always creates something new; map always creates a copy of the hosting structure (map over a Vec, the accumulator starts as an empty Vec) while transforming the values therein (T -> U).

To help to see what’s going on when it looks static (if you will), like seeing 3 as 3 x 1, a fold can max out the “crushing” of the data by say returning the sum of all numbers in a list. It could also “punt” the job of crunching the numbers by simply returning the Vec of numbers “as is” (3 x 1). In other words, if your not ready to lose the detail of what you have in your collection, dump them into Vec, the universal accumulator. Finally, the distinction in what I described is simply whether you see a Vec as many values of T or a single Vec. With this in mind a fold always generates a single value (e.g., Vec or a single number that is the sum of what was in the collection), a map generates a copy of your values transformed by whatever closure was included.

Lastly, if this is not already evident, a fold is not limited to producing a single value nor all the values. It could use say the first 10 values in a collection to create the first value in a new collection, and the next 10 to create the next value in the new collection etc. The method used to construct the new value can be infinitely complex. This pattern is used a bunch to build a HashMap from a Vec for instance. That is a fold, not a map because the “subject” of the transformation includes the hosting collection structure i.e., the Collection in Collection<T>. In this case, it’s conceptually more useful to see what is returned as a single value from a collection of values. And lastly, a fold captures going from a single value to another value; think [u32, 1] -> String, and given that the array is isomorphic with the value it hosts in this case.

In relation to the visitor pattern, I could conceptualize it as an optimized map function where we reuse the current memory (overwrite aka update). As such, depending on how you think about visitor, relate what we did to a for each loop. Now I can relate the fold machinery to returning a side effect.

[Trequetrum]

Let me pile on a bit too:

Iterators have a fold method, however this folds a data structure into a value, rather than into a new data structure.

This is a confused/confusing thing to say. Data structures ARE values.

For example, a below has a value and that value is a also a data structure.

let a = vec![1,2,3];