Functional Maps and Folds versus Imperative Loops

WIM: Hi. In this tutorial, I want to explain the relationship between maps and folds in Haskell and loops in an imperative language. For the imperative language, I will use the scripting language Ruby, but you can do this really in any imperative language. So suppose we want to perform a map on a list using function f.

And suppose the function f is simply something like x times x plus 1.

Suppose lst is just a list of numbers.

Then we can print this computation.

So, now, if you want to do the same thing in Ruby, then we first need to create the function f.

And then we create the lists, lst is an empty list. And then we populate it with the range.

Now, we create the result list.

And we apply the map.

And then we simply print this.

Let’s try this.

So to get a bit similar result in Ruby, we can move this. And now it looks a bit more like the Haskell we saw. Clearly, the for loop is a very straightforward implementation of the map. So, for every element in the list, we push a new element on to the new list lst_. So what about folds. Now, suppose we have operation g is (/).

And then we can fold the division and using the left fold, foldl g and then an accumulator, which we can set to 1, and on our list.

So we can print this now and see what we get.

So, now, let’s do the same thing in Ruby. We have to create the function g. And we can’t do this neat thing like we do in Haskell, so we have to actually say def g(accumulator and element).

And we have acc/elt. And then we have a loop.

And we start with qcc = 1.0. And we apply the function to the accumulator

And we can try it out.

Indeed, we get the same thing. Now, if we do the same but with a right fold, so, obviously, the Haskell example is fairly simple.

And g prime is just the same as g.

And so we can simply print with the new accumulator. And try that.

And in Ruby, we need to define a new function g. And I can’t use a prime, so I’ll use an underscore. But note that we have to define it like this.

And we have our for loop.

Where we reverse the list, so that we can start at the end.

We can inspect this.

And indeed, we do get the same result. So, essentially, what we see is that the fold operations are actually loops that change updatable variable using a function that uses the same variable. So g uses acc and returns and a new value-based on acc and elt, and it sends this to acc. And g_ does the same thing. And you have to explicitly specify the order of the arguments, so that when you traverse the list from the right, you get the same result as in Haskell. For the map, it’s much simpler. So you take a list, you apply the function on each element of the list, and this result is pushed onto the new list.

Note, again, how much neater all this is in Haskell, so each of these folds and maps are just single lines. In Ruby, we have to write explicit functions for each of them. But the main message is that if you are in some doubt of how a fold, left or a right fold, or a map works in Haskell, you can always try and think of this alternative– how it works in an imperative language with for loops. And from there, you can easily reason about what your maps or folds should look like.