Skip to 0 minutes and 5 seconds 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.
Skip to 0 minutes and 39 seconds And suppose the function f is simply something like x times x plus 1.
Skip to 0 minutes and 48 seconds Suppose lst is just a list of numbers.
Skip to 0 minutes and 57 seconds Then we can print this computation.
Skip to 1 minute and 27 seconds So, now, if you want to do the same thing in Ruby, then we first need to create the function f.
Skip to 1 minute and 47 seconds And then we create the lists, lst is an empty list. And then we populate it with the range.
Skip to 2 minutes and 11 seconds Now, we create the result list.
Skip to 2 minutes and 16 seconds And we apply the map.
Skip to 2 minutes and 36 seconds And then we simply print this.
Skip to 2 minutes and 46 seconds Let’s try this.
Skip to 2 minutes and 59 seconds 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 (/).
Skip to 3 minutes and 32 seconds 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.
Skip to 3 minutes and 53 seconds So we can print this now and see what we get.
Skip to 4 minutes and 3 seconds 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).
Skip to 4 minutes and 19 seconds And we have acc/elt. And then we have a loop.
Skip to 4 minutes and 30 seconds And we start with qcc = 1.0. And we apply the function to the accumulator
Skip to 4 minutes and 45 seconds And we can try it out.
Skip to 4 minutes and 53 seconds 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.
Skip to 5 minutes and 14 seconds And g prime is just the same as g.
Skip to 5 minutes and 20 seconds And so we can simply print with the new accumulator. And try that.
Skip to 5 minutes and 31 seconds 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.
Skip to 5 minutes and 47 seconds And we have our for loop.
Skip to 5 minutes and 56 seconds Where we reverse the list, so that we can start at the end.
Skip to 6 minutes and 6 seconds We can inspect this.
Skip to 6 minutes and 16 seconds 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.
Skip to 7 minutes and 18 seconds 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.
Functional Maps and Folds versus Imperative Loops
This tutorial explains the relationship between the higher-order list operations
foldr and loops in an imperative language.
The source code can be found on GitHub
map : loop over list element-by-element, append new element to new list
foldl : loop over list element-by-element, update accumulator using current accumulator and element
foldr : loop over reverse list element-by-element, update accumulator using current accumulator and element
map :: (a -> b) -> [a] -> [b] foldl :: (b -> a -> b) -> b -> [a] -> b foldr :: (a -> b -> b) -> b -> [a] -> b
© Wim Vanderbauwhede