Folds versus recursion in Erlang

Question

According to Find out what you have Erlang :

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

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

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

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

Answer 1

Folds

usually more readable (because everyone knows what they are doing) and faster thanks to optimized runtime implementations (especially foldl, which should always be tail recursive). It is worth noting that they are only a constant factor faster, and not in a different order, so this is usually a premature optimization if you think that you are considering one after another for performance reasons.

Use standard recursion when you do interesting things, for example, working on several elements at a time, splitting into several processes, etc. and stick to higher order functions (fold, map, ...) when they’re already doing what you want.

Answer 2

I personally prefer recursion over the fold in Erlang (unlike other languages ​​like Haskell). I do not see more understandable than recursion. For instance:

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). 

against

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

There seems to be more code, but this is a fairly simple and idiomatic Erlang. Using fold requires less code, but the difference becomes smaller and smaller with a larger payload. Imagine that we want the filter to display odd values ​​on 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 the gain in the list looks, but the recursive function is in second place, and the reset version is ugly and less readable.

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

Edit : I add a resettable version with the loss of a 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 much more readable this is than rfoo/1 , and I found that manipulating the battery is more complicated and less obvious than direct recursion. This is an even longer code.

Answer 3

I expect the reset to be done recursively, so you might want to try to implement some of the list functions, such as a map or filter, with a fold and see how useful this is.

Otherwise, if you do this recursively, you may be able to reset again.

Learn to use what comes with the tongue; this is my thought.

This discussion on folding and recursion is interesting:

Easy way to break foldl

If you look at the first paragraph in this introduction (you can read everything), it speaks better than me.

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