aprendiendo ( Erlang ).

viernes, 13 de mayo de 2011

listas IV. Plegados. Folds.

| 2 comentarios |

El Fold es una herramienta muy poderosa cuando la conoces bien. La función Fold, también conocida como plegado o reduce, toma una lista, un caso base y una función que se aplica a dos elementos.
La sintaxis es fold(F=fun (X, Acc), V0, Lista). La función F toma un valor de la lista y un valor acumulado (realiza la operación de plegado). V0 es el valor inicial o caso base y se trata del primer acumulador pasado a la primera llamada a F.
El módulo lists implementa dos funciones fold: foldr o plegado de derecha a izquierda; y foldl o plegado de izquierda a derecha. Veamos un ejemplo de uso:
1> Suma = fun (A, B) -> A + B end.                                                            
#Fun
2> lists:foldr ( Suma, 0, lists:seq(1,5) ).
15
3> lists:foldl ( Suma, 0, lists:seq(1,5) ). 
15
El ejemplo es simple, hemos realizado una suma de todos los elementos de la lista. Y aparentemente, ambas funciones realizan lo mismo. Lo cierto es que no es así.
4> Suma2 = fun (A, B) -> io:format ("valor: ~p; acumulado: ~p~n", [A, B]), Suma(A,B) end.
#Fun
5> lists:foldr ( Suma2, 0, lists:seq(1,5) ).  
valor: 5; acumulado: 0
valor: 4; acumulado: 5
valor: 3; acumulado: 9
valor: 2; acumulado: 12
valor: 1; acumulado: 14
15
6> lists:foldl ( Suma2, 0, lists:seq(1,5) ). 
valor: 1; acumulado: 0
valor: 2; acumulado: 1
valor: 3; acumulado: 3
valor: 4; acumulado: 6
valor: 5; acumulado: 10
15
Ahora si vemos con mayor claridad la diferencia entre las dos funciones. Foldr tiene su caso base en el valor 5, es decir, realiza los plegados de derecha a izquierda como se ha comentado: 1 + (2 + (3 + (4 + (5 + 0)))). Foldl tiene su caso base en el valor 1, es decir, que realiza: ((((0 + 1) + 2) + 3) + 4) + 5.
En este ejemplo, el resultado es igual por que la operación de suma es conmutativa, pero no es siempre este el caso. Ahora realicemos la misma operación con la función concatenar.
7> Concatenar = fun (A, B) -> [A|B] end.
#Fun
8> lists:foldr ( Concatenar, [], lists:seq(1,5) ).
[1,2,3,4,5]
9> lists:foldl ( Concatenar, [], lists:seq(1,5) ).
[5,4,3,2,1]
El foldr nos devuelve la misma lista y foldl, de la función concatenar, nos permite invertir la lista.
Pues bien, queda demostrado que vamos a depender de la función que le pasemos, de las necesidades que tengamos y de nuestra imaginación para utilizar uno u otro plegado.

Publicar un comentario

2 comentarios:

  1. Anónimo dijo...

    Muchas Gracias, con esto pudé entender como funcionan los folds.

  2. Verdi dijo...

    Me alegra saber que te ha sido útil.

    Gracias.

 
Licencia Creative Commons
Aprendiendo Erlang por Verdi se encuentra bajo una Licencia Creative Commons Atribución-NoComercial-CompartirIgual 3.0 Unported.