I’ve been reading “Introduction to Elixir” and I’m trying to understand where List.foldl and List.foldr would be useful. Basically, I’m looking for a use case. In what situation would the lightbulb go on that hey I should fold the list in this situation.
I believe List fold is very cheap to use (as long as it’s List.foldl as it’s tail recursive) but many people fail to understand a situation where it may be the tool for the job.
Thanks!
Well, you know all those iterators in Enum? The truth is that you could choose to handle most of that with fold*(). Here are examples for map(), sum(), and filter():
iex(1)> nums = [1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]
iex(2)> List.foldr(nums, [ ], fn n, doubles -> [n * 2 | doubles] end)
[2, 4, 6, 8, 10]
iex(3)> List.foldl(nums, 0, fn n, sum -> n + sum end)
15
iex(4)> require Integer
nil
iex(5)> List.foldr(nums, [ ], fn n, evens -> if Integer.is_even(n), do: [n | evens], else: evens end)
[2, 4]
Here is an explanation of folds on lists: List Folds at BFPG
I only briefly read through the slides, so I can’t comment on the presentation, but I believe it should shed some light on the mystery of folds. Folds for Imperative Programmers is just what the title says. The code is in Scala, but it should be navigable.
I’ve read some of Tony’s other work and he knows his category theory concepts. His Monad Exercises in Scala (Haskell too) will change the way you think about programming.
Not to nit pick, but the doubles example would probably benefit from using List.foldl as multiplication doesn’t matter if it is left to right or right to left. Granted, in such a simple example, it won’t make much of a difference in efficiency.
It reverses the order of the list as it works, if you use foldl().
Ahh, I should have run it in iex before. Now I see. List.foldl traverses left to right but reverses the result, hence Fold. I was remembering an example in the book and they mentioned that if order doesn’t change the result, then use Lsit.foldl. In the example in the book they were using an accumulator so with multiplication it didn’t matter. But, in your example you were returning the List doubled.
Also, I’m a bit confused what fn n, doubles -> [n * 2 | doubles] end) is doing. You have an anonymous function which is passing in each list item and multiplying by 2. But, is doubles the resulting list? It is an empty list to begin with and each iteration is passing the original list item multiplied by 2?
So, you start with [1,2,3,4,5]
Then the doubles list ends up being [10,8,6,4,2]
and the List.foldr flips it making doubles [2.4.6.8.10]?
No, I think I am wrong again. What’s happening is this:
original list is [1,2,3,4,5]
List.foldr traverses the list right to left so we start with n being 5 and work right to left. But you are making each iteration through the list part of the tails, basically reordering the list from small to big, like so:
doubles = [10] //first pass
doubles = [8,10] //seconds pass
doubles = [6,8,10] //third pass
etc…
I think I got it.
More like you are stepping down the whole list to the end then on the way back up you folding the accumulator through function and returning the result.
Why does this give a funny result?
List.foldl(nums, [ ], fn n, doubles -> [doubles | n * 2] end)
I think that folds are best understood when source is provided.
Therefore I’ll do a quick translate of my haskell-lecture-notes to elixir
without taking optimisations into accont. I use my haskell notes since they are
(nearly) always around my desk 
defmodule Folds do
def foldl(list, fun, acc)
def foldl([], _fun, acc), do: acc
def foldl([x|xs], fun, acc), do: foldl(xs, fun, fun.(x, acc))
def foldr(list, fun, acc)
def foldr([], _fun, acc), do: acc
def foldr([x|xs], fun, acc), do: fun.(x, foldr(xs, fun, acc))
end
Using these definitions, I will use each of the folds with 2 very simple
functions:
foldr [1,2,3], &(&1 + &2), 0foldl [1,2,3], &(&1 + &2), 0foldr [1,2,3], &([&1|&2]), []foldl [1,2,3], &([&1|&2]), []1. foldr [1,2,3], &(&1 + &2), 0
=> foldr [1|[2,3]], &(&1 + &2), 0
=> &(&1 + &2).(1, foldr([2,3], &(&1 + &2), 0))
=> &(&1 + &2).(1, foldr([2|[3]], &(&1 + &2), 0))
=> &(&1 + &2).(1, &(&1 + &2).(2, foldr([3], &(&1 + &2), 0)))
=> &(&1 + &2).(1, &(&1 + &2).(2, foldr([3|[]], &(&1 + &2), 0)))
=> &(&1 + &2).(1, &(&1 + &2).(2, &(&1 + &2).(3, foldr([], &(&1 + &2), 0))))
=> &(&1 + &2).(1, &(&1 + &2).(2, &(&1 + &2).(3, 0)))
=> &(&1 + &2).(1, &(&1 + &2).(2, 3 + 0))
=> &(&1 + &2).(1, &(&1 + &2).(2, 3))
=> &(&1 + &2).(1, 2 + 3)
=> &(&1 + &2).(1, 5)
=> 1 + 5
=> 6
2. foldl [1,2,3], &(&1 + &2), 0
=> foldl [1|[2,3]], &(&1 + &2), 0
=> foldl [2,3], &(&1 + &2), &(&1 + &2).(1, 0)
=> foldl [2,3], &(&1 + &2), 1 + 0
=> foldl [2|[3]], &(&1 + &2), 1
=> foldl [3], &(&1 + &2), &(&1 + &2).(2, 1)
=> foldl [3], &(&1 + &2), 2 + 1
=> foldl [3|[]], &(&1 + &2), 3
=> foldl [], &(&1 + &2), &(&1 + &2).(3, 3)
=> foldl [], &(&1 + &2), 3 + 3
=> foldl [], &(&1 + &2), 6
=> 6
3. foldr [1,2,3], &([&1|&2]), []
=> foldr [1|[2,3]], &([&1|&2]), []
=> &([&1|&2]).(1, foldr([2,3], &([&1|&2]), []))
=> &([&1|&2]).(1, foldr([2|[3]], &([&1|&2]), []))
=> &([&1|&2]).(1, &([&1|&2]).(2, foldr([3], &([&1|&2]), [])))
=> &([&1|&2]).(1, &([&1|&2]).(2, foldr([3|[]], &([&1|&2]), [])))
=> &([&1|&2]).(1, &([&1|&2]).(2, &([&1|&2]).(3, foldr([], &([&1|&2]), []))))
=> &([&1|&2]).(1, &([&1|&2]).(2, &([&1|&2]).(3, [])))
=> &([&1|&2]).(1, &([&1|&2]).(2, [3]))
=> &([&1|&2]).(1, [2,3])
=> [1,2,3]]
4. foldl [1,2,3], &([&1|&2]), []
=> foldl [1|[2,3]], &([&1|&2]), []
=> foldl [2,3], &([&1|&2]), &([&1|&2]).(1, [])
=> foldl [2,3], &([&1|&2]), [1]
=> foldl [2|[3]], &([&1|&2]), [1]
=> foldl [3], &([&1|&2]), &([&1|&2]).(2, [1])
=> foldl [3], &([&1|&2]), [2,1]
=> foldl [3|[]], &([&1|&2]), [2,1]
=> foldl [], &([&1|&2]), &([&1|&2]).(3, [2,1])
=> foldl [], &([&1|&2]), [3,2,1]
=> [3,2,1]
Personally I think, the best way to understand higher order functions, is just
to take a small example output, look at the definition and go through it by
hand. We had to do this a lot during FP exercises…
Pen and Paper, vim, emacs, whatever you like most, but beeing capable of
monospaced fonts helps a lot
edit
I’ve seen @alamba78’s latest reply to late, but I had not used that function anyway, since it produces improper lists!
Improper lists are something you want to avoid, that are lists, where the last “element” is not the empty list, but something else. They can really confuse your code. The example you are showing is even nesting them…
You are building the list in the wrong direction. You cannot use the [ | ] syntax to add an element to the end of the list, only to the front of the list in which case you would write [n * 2 | double]. There is no efficient way to add an element to the end of a list. So if you use List.foldl to build a list you will get the resulting in the “wrong” order. Think stack. To build in the “right” order you would use List.foldr.
Thanks for the feedback guys. Very helpful. I didn’t realize there was a concept of improper lists. It makes a lot more sense now that the last two replies came in. Thanks again!
Yep, you’ve got it now.
© Copyright Elixir Forum | Terms | Privacy & Cookies
