Skip to 0 minutes and 5 secondsWIM: 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 secondsAnd suppose the function f is simply something like x times x plus 1.
Skip to 0 minutes and 48 secondsSuppose lst is just a list of numbers.
Skip to 0 minutes and 57 secondsThen we can print this computation.
Skip to 1 minute and 27 secondsSo, 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 secondsAnd then we create the lists, lst is an empty list. And then we populate it with the range.
Skip to 2 minutes and 11 secondsNow, we create the result list.
Skip to 2 minutes and 16 secondsAnd we apply the map.
Skip to 2 minutes and 36 secondsAnd then we simply print this.
Skip to 2 minutes and 46 secondsLet's try this.
Skip to 2 minutes and 59 secondsSo 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 secondsAnd 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 secondsSo we can print this now and see what we get.
Skip to 4 minutes and 3 secondsSo, 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 secondsAnd we have acc/elt. And then we have a loop.
Skip to 4 minutes and 30 secondsAnd we start with qcc = 1.0. And we apply the function to the accumulator
Skip to 4 minutes and 45 secondsAnd we can try it out.
Skip to 4 minutes and 53 secondsIndeed, 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 secondsAnd g prime is just the same as g.
Skip to 5 minutes and 20 secondsAnd so we can simply print with the new accumulator. And try that.
Skip to 5 minutes and 31 secondsAnd 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 secondsAnd we have our for loop.
Skip to 5 minutes and 56 secondsWhere we reverse the list, so that we can start at the end.
Skip to 6 minutes and 6 secondsWe can inspect this.
Skip to 6 minutes and 16 secondsAnd 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 secondsNote, 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