在Erlang中折叠与递归

Question

据了解一些Erlang:

几乎任何你能想到的功能都可以将列表减少为1个元素,可以表示为折叠.[...]这意味着折叠是通用的,你可以在带有折叠的列表上实现几乎任何其他递归函数

我在编写一个带有列表并将其减少为1个元素的函数时的第一个想法是使用递归.

有哪些指导方针可以帮助我决定是使用递归还是折叠？

这是一种风格考虑还是还有其他因素(性能,可读性等)？

Answer 1

我个人更喜欢Erlang中的递归折叠(与其他语言相反,例如Haskell).我不认为折叠比递归更具可读性.例如:

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

要么

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

看起来更多的代码,但它是非常简单和惯用的Erlang.使用折叠需要更少的代码,但差异越来越小,有效载荷越来越大.想象一下,我们想要一个过滤器并将奇数值映射到它们的方块.

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

这里列表理解获胜但递归函数位于第二位,折叠版本丑陋且可读性较差.

最后,折叠比递归版本更快,尤其是在编译为本机(HiPE)代码时.

编辑:我根据要求在变量中添加了一个有趣的折叠版本:

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

我没有看到它的可读性如何rfoo/1,我发现特别是累加器操作比直接递归更复杂,更不明显.它甚至更长的代码.

Answer 2

由于运行时优化的实现(特别是foldl总是应该是尾递归的),折叠通常更具可读性(因为每个人都知道它们做了什么)并且更快.值得注意的是,它们只是一个恒定的因素,而不是另一个顺序,所以如果你因为性能原因发现自己考虑一个而不是另一个,那么它通常会过早优化.

当你做一些奇特的东西时使用标准递归,例如一次处理多个元素,分成多个进程和类似的东西,并且当它们已经做了你的事情时,坚持使用更高阶的函数(fold,map,...)想.