pliegues frente a la recursividad en Erlang

Question

Según Learn you some Erlang:

Casi cualquier función que se pueda imaginar que reduce las listas a 1 elemento se pueden expresar como un pliegue. [...] Esto significa veces es universal en el sentido de que se puede implementar casi cualquier otra función recursiva en las listas con un pliegue

Mi primer pensamiento al escribir una función que toma una lista y lo reduce a 1 elemento es usar recursión.

¿Cuáles son las pautas que deberían ayudarme a decidir si usar recursion o fold?

¿Es esto una consideración estilística o hay otros factores también (rendimiento, legibilidad, etc.)?

Answer 1

pliegues que generalmente son tanto más legible (como todo el mundo sabe lo que hacen) y más rápido debido a las implementaciones optimizadas en el tiempo de ejecución (especialmente foldl que siempre debe ser recursiva cola). Vale la pena señalar que solo son un factor constante más rápido, no en otro orden, por lo que suele ser una optimización prematura si se considera uno sobre el otro por motivos de rendimiento.

Utilice la recursión estándar cuando hace cosas sofisticadas, como trabajar en más de un elemento a la vez, dividir en múltiples procesos y similares, y mantener las funciones de orden superior (doblar, asignar, ...) cuando ya haz lo que quieras

Answer 2

Espero que el plegado se realice de forma recursiva, por lo que es posible que desee tratar de implementar algunas de las diversas funciones de la lista, como el mapa o el filtro, con fold, y ver qué tan útil puede ser.

De lo contrario, si lo hace de forma recursiva, es posible que vuelva a implementar fold, básicamente.

Aprender a usar lo que viene con el lenguaje, es mi pensamiento.

Esta discusión sobre foldl y recursividad es interesante:

Easy way to break foldl

Si nos fijamos en el primer párrafo de esta introducción (es posible que desee leer todos de la misma), se establece mejor que yo.

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

Answer 3

Personalmente, prefiero la recursión en exceso en Erlang (a diferencia de otros idiomas, por ejemplo, Haskell). No veo el doblez más legible que la recursión. Por ejemplo:

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

o

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

parece más código, pero es bastante sencillo e idiomático Erlang. Usar fold requiere menos código pero la diferencia se vuelve más y más pequeña con más carga útil. Imagina que queremos un filtro y asignamos valores impares a su cuadrado.

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

Aquí la lista de victorias de comprensión, pero es función recursiva en el segundo lugar y doblar versión es feo y menos legible.

Y, por último, no es cierto que el doblez sea más rápido que la versión recursiva, especialmente cuando se compila con código nativo (HiPE).

Editar: que añadir una versión pliegue con la diversión en la variable a lo solicitado:

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

no veo la forma en que es más fácil de leer que rfoo/1 y me encontré especialmente un acumulador de manipulación más complicada y menos obvio que la recursión directa. Es incluso un código más largo.