Folds versus recursion in Erlang

Question

According to Learn you some Erlang :

Pretty much any function you can think of that reduces lists to 1 element can be expressed as a fold. [...] This means fold is universal in the sense that you can implement pretty much any other recursive function on lists with a fold

My first thought when writing a function that takes a lists and reduces it to 1 element is to use recursion.

What are the guidelines that should help me decide whether to use recursion or a fold?

Is this a stylistic consideration or are there other factors as well (performance, readability, etc.)?

Answer 1

I personally prefer recursion over fold in Erlang (contrary to other languages e.g. Haskell). I don't see fold more readable than recursion. For example:

fsum(L) -> lists:foldl(fun(X,S) -> S+X end, 0, L).

or

fsum(L) ->
    F = fun(X,S) -> S+X end,
    lists:foldl(F, 0, L).

vs

rsum(L) -> rsum(L, 0).

rsum([], S) -> S;
rsum([H|T], S) -> rsum(T, H+S).

Seems more code but it is pretty straightforward and idiomatic Erlang. Using fold requires less code but the difference becomes smaller and smaller with more payload. Imagine we want a filter and map odd values to their square.

lcfoo(L) -> [ X*X || X<-L, X band 1 =:= 1].

fmfoo(L) ->
  lists:map(fun(X) -> X*X end,
    lists:filter(fun(X) when X band 1 =:= 1 -> true; (_) -> false end, L)).

ffoo(L) -> lists:foldr(
    fun(X, A) when X band 1 =:= 1 -> [X|A];
      (_, A) -> A end,
    [], L).

rfoo([]) -> [];
rfoo([H|T]) when H band 1 =:= 1 -> [H*H | rfoo(T)];
rfoo([_|T]) -> rfoo(T).

Here list comprehension wins but recursive function is in the second place and fold version is ugly and less readable.

And finally, it is not true that fold is faster than recursive version especially when compiled to native (HiPE) code.

Edit: I add a fold version with fun in variable as requested:

ffoo2(L) ->
    F = fun(X, A) when X band 1 =:= 1 -> [X|A];
           (_, A) -> A
        end,
    lists:foldr(F, [], L).

I don't see how it is more readable than rfoo/1 and I found especially an accumulator manipulation more complicated and less obvious than direct recursion. It is even longer code.

Answer 2

folds are usually both more readable (since everybody know what they do) and faster due to optimized implementations in the runtime (especially foldl which always should be tail recursive). It's worth noting that they are only a constant factor faster, not on another order, so it's usually premature optimization if you find yourself considering one over the other for performance reasons.

Use standard recursion when you do fancy things, such as working on more than one element at a time, splitting into multiple processes and similar, and stick to higher-order functions (fold, map, ...) when they already do what you want.

Answer 3

I expect fold is done recursively, so you may want to look at trying to implement some of the various list functions, such as map or filter, with fold, and see how useful it can be.

Otherwise, if you are doing this recursively you may be re-implementing fold, basically.

Learn to use what comes with the language, is my thought.

This discussion on foldl and recursion is interesting:

Easy way to break foldl

If you look at the first paragraph in this introduction (you may want to read all of it), he states better than I did.

http://www.cs.nott.ac.uk/~gmh/fold.pdf