Fałdy porównaniu rekursji w Erlang

Question

Według Learn you some Erlang:

Prawie każdy funkcji można myśleć, że ogranicza listę do 1 elementu może być wyrażona jako krotnie. [...] Oznacza to rozkładana jest uniwersalny w tym sensie, że można realizować praktycznie żadnej innej funkcji rekurencyjnej na listach z fałdą

Moja pierwsza myśl pisząc funkcję, która pobiera listy i redukuje go do 1 elementem jest użycie rekursji.

Jakie są wytyczne, które powinny pomóc mi zdecydować, czy użyć rekursji czy zgięcia?

Czy jest to kwestia stylistyczna, czy też istnieją inne czynniki (wydajność, czytelność itp.)?

Answer 1

fałdy są zwykle zarówno bardziej czytelne (ponieważ wszyscy wiedzą, co robią) i szybsze dzięki zoptymalizowanym wdrożeń w środowisku wykonawczym (zwłaszcza foldl które zawsze powinny być ogon rekurencyjne). Warto zauważyć, że są one tylko stałym czynnikiem szybszym, a nie na innym zamówieniu, więc zwykle jest to przedwczesna optymalizacja, jeśli zastanowisz się nad jednym ze względu na wydajność.

Używaj standardowej rekursji, gdy robisz fantazyjne rzeczy, takie jak praca na więcej niż jednym elemencie naraz, dzielenie na wiele procesów i podobne i trzymaj się funkcji wyższego rzędu (fold, map, ...), kiedy już rób, co chcesz.

Answer 2

Spodziewam się, że fold jest wykonywany rekurencyjnie, więc możesz spróbować zaimplementować niektóre z różnych funkcji list, takich jak mapa lub filtr, z foldem i zobaczyć, jak użyteczne może być.

W przeciwnym razie, jeśli robisz to rekurencyjnie, możesz w zasadzie ponownie wprowadzić fałdę.

Naucz się używać tego, co pochodzi z językiem, to moja myśl.

Ta dyskusja na foldl i rekursji jest ciekawe:

Easy way to break foldl

Jeśli spojrzeć na pierwszego akapitu w tym wstępie (może chcesz przeczytać to wszystko), stwierdza on lepiej niż ja.

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

Answer 3

Ja osobiście wolę rekursję niż spasować w Erlang (w przeciwieństwie do innych języków, np. Haskell). Nie widzę, aby fałd był bardziej czytelny niż rekursja. Na przykład:

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

lub

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

wydaje się kod, ale to jest dość proste i idiomatyczne Erlang. Używanie spasowania wymaga mniej kodu, ale różnica staje się mniejsza i mniejsza przy większej ładowności. Wyobraźmy sobie, że chcemy filtra i mapujemy wartości nieparzyste na ich kwadrat.

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

Oto lista wygrywa ze zrozumieniem, ale funkcja rekurencyjna jest na drugim miejscu i złożyć wersja jest brzydkie i mniej czytelny.

I na koniec nie jest prawdą, że fold jest szybszy niż wersja rekursywna, zwłaszcza gdy jest skompilowany do natywnego kodu (HiPE).

Edit: dodaję krotny wersję z zabawy w zmiennej zgodnie z żądaniem:

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

nie widzę jak to jest bardziej czytelny niż rfoo/1 i znalazłem szczególnie manipulacja bardziej skomplikowane i akumulatorów mniej oczywiste niż bezpośrednia rekursja. Jest to nawet dłuższy kod.