This is a supplemental answer to help explain maps and folds. For the examples below, I'll use this list. Remember, this list is immutable, so it will never change:
var numbers = [1, 2, 3, 4, 5]
I'll be using numbers in my examples because they lead to easy to read code. Remember though, folds can be used for anything a traditional imperative loop can be used for.
A map takes a list of something, and a function, and returns a list that was modified using the function. Each item is passed to the function, and becomes whatever the function returns.
The easiest example of this is just adding a number to each number in a list. I'll use pseudocode to make it language agnostic:
function add-two(n):
return n + 2
var numbers2 =
map(add-two, numbers)
If you printed numbers2, you would see [3, 4, 5, 6, 7] which is the first list with 2 added to each element. Notice the function add-two was given to map to use.
Folds are similar, except the function you're required to give them must take 2 arguments. The first argument is usually the accumulator (in a left fold, which are the most common). The accumulator is the data that's passed while looping. The second argument is the current item of the list; just like above for the map function.
function add-together(n1, n2):
return n1 + n2
var sum =
fold(add-together, 0, numbers)
If you printed sum you would see the sum of the list of numbers: 15.
Here are what the arguments to fold do:
This is the function that we're giving the fold. The fold will pass the function the current accumulator, and the current item of the list. Whatever the function returns will become the new accumulator, which will be passed to the function the next time. This is how you "remember" values when you're looping FP-style. I gave it a function that takes 2 numbers and adds them.
This is the initial accumulator; what the accumulator starts as before any items in the list are processed. When you're summing numbers, what's the total before you've added any numbers together? 0, which I passed as the second argument.
Lastly, as with the map, we also pass in the list of numbers for it to process.
If folds still don't make sense, consider this. When you write:
# Notice I passed the plus operator directly this time,
# instead of wrapping it in another function.
fold(+, 0, numbers)
You're basically putting the passed function between each item in the list, and adding the initial accumulator onto either the left or right (depending on if it's a left or right fold), so:
[1, 2, 3, 4, 5]
Becomes:
0 + 1 + 2 + 3 + 4 + 5
^ Note the initial accumulator being added onto the left (for a left fold).
Which equals 15.
Use a map when you want to turn one list into another list, of the same length.
Use a fold when you want to turn a list into a single value, like summing a list of numbers.
As @Jorg pointed out in the comments though, the "single value" need not be something simple like a number; it could be any single object, including a list or a tuple! The way I actually had folds click for me was to define a map in terms of a fold. Note how the accumulator is a list:
function map(f, list):
fold(
function(xs, x): # xs is the list that has been processed so far
xs.add( f(x) ) # Add returns the list instead of mutating it
, [] # Before any of the list has been processed, we have an empty list
, list)
Honestly, once you understand each, you'll realize almost any looping can be replaced by a fold or a map.
