褶皺與遞歸二郎

Question

根據Learn you some Erlang：

差不多，你能想到的任何功能減少列表1元可表示爲一個摺疊。 [...] 這意味着折是在這個意義上通用的，你可以用摺疊落實名單幾乎任何其他遞歸函數

我首先想到寫一個函數，它接受一個列表，並減少了當1元素是使用遞歸。

什麼是應該幫助我決定是否使用遞歸或摺疊的指導方針？

這是一種文體考慮還是還有其他因素（性能，可讀性等）？

Answer 1

褶皺通常都更具有可讀性（因爲每個人都知道他們在做什麼）和更快由於在運行時優化的實現（特別是與foldl總是應該是尾遞歸）。值得注意的是，它們只是一個恆定的因素，而不是另一個訂單，所以如果您因性能原因而發現自己考慮了另一個，通常是不成熟的優化。

當你喜歡做某些事情時，使用標準遞歸，例如一次處理多個元素，分裂成多個進程和類似的東西，並且當他們使用高階函數時（摺疊，映射......）已經做到了你想要的。

Answer 2

我期望fold是遞歸完成的，所以你可能想看看試圖用fold實現一些各種列表函數，比如map或者filter，看看它是多麼有用。

否則，如果您正在遞歸執行此操作，則基本上可能會重新實現fold操作。

學會使用語言，是我的想法。

上與foldl和遞歸這個討論很有意思：

Easy way to break foldl

如果你看一下在此介紹的第一款（您可能需要閱讀所有的話），他說比我更好。

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

Answer 3

我個人比較傾向於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). 

在這裏列表理解勝，但遞歸函數是第二位，摺疊版本是醜陋的和可讀性較差。

最後，fold比遞歸版本更快，尤其是編譯爲本機（HiPE）代碼時。

編輯： 我添加了一個摺疊的版本與可變樂趣的要求：

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

我不明白它是如何比rfoo/1更具可讀性，我發現特別是蓄電池的操作更加複雜，比直接遞歸更不明顯。它甚至更長的代碼。