Erlang Thursday – lists:foldl/3 and lists:foldr/3

Today’s Erlang Thursday is lists:foldl/3 and lists:foldr/3.

lists:foldl/3 is Erlang’s version of the reduce function. lists:foldl/3 takes a function, an initial accumulator value, and a list, and returns a single value.

The first argument given to foldl is a function that takes two arguments, the item currently iterating over, and the accumulated value. The result of applying this function is used as new new value for the accumulator for the following item, or if no items are left it becomes the result of foldl.

The next argument to lists:foldl/3 is an initial value of the accumulator. This is different than some other languages, as those languages will take the initial value for the accumulator as an optional value and use the first item to be traversed as the default value for the accumulator. But in Erlang an initial value for the accumulator is a required argument to both lists:foldl/3 and lists:foldr/3.

The third, and last, argument to foldl is the list to iterate over.

lists:foldl(fun(X, Sum) -> Sum + X end, 0, [1, 2, 3, 4, 5]).
% 15
lists:foldl(fun(X, Product) -> Product * X end, 1, [1, 2, 3, 4, 5]).
% 120
lists:foldl(fun(X, Accum) -> io:format("~p ", [X]) end, void, [1, 2, 3, 4, 5]).
% 1 2 3 4 5 ok
lists:foldl(fun(X, Accum) -> io:format("~p ", [X]), Accum end, void, [1, 2, 3, 4, 5]).
% 1 2 3 4 5 void
lists:foldl(fun(X, Accum) -> Accum + X end, 1, []).               
% 1
lists:foldl(fun(X, Result) -> lists:umerge(Result, X) end, [], [[1, 2, 3], [3, 5, 8], [11, 13, 17]]).
% [1,2,3,5,8,11,13,17]

The Erlang lists module also contains the function foldr/3 which traverses the list from left to right, or from the last item in the list to the first.

lists:foldr(fun(X, Accum) -> io:format("~p ", [X]), Accum end, void, [1, 2, 3, 4, 5]).
% 5 4 3 2 1 void
lists:foldr(fun(X, Accum) -> Accum + X end, 1, []).
% 1

The Erlang documentation points out that lists:foldl/3 is generally preferable over lists:foldr/3 because lists:foldl/3 is tail recursive, where lists:foldr/3 is not.