Mapas, filtros, pliegues y más

Implementemos la función map:

map(_, []) -> [];

map(F, [H|T]) -> [F(H)|map(F,T)].

Existen muchas otras abstracciones similares que se pueden construir a partir de funciones recursivas que ocurren comúnmente. Veamos estas funciones :

%% only keep even numbers

even(L) -> lists:reverse(even(L,[])).

 

even([], Acc) -> Acc;

even([H|T], Acc) when H rem 2 == 0 -> even(T, [H|Acc]);

even([_|T], Acc) -> even(T, Acc).

 

%% only keep men older than 60

old_men(L) -> lists:reverse(old_men(L,[])).

 

old_men([], Acc) -> Acc;

old_men([Person = {male, Age}|People], Acc) when Age > 60 ->

old_men(People, [Person|Acc]);

old_men([_|People], Acc) ->

old_men(People, Acc).

El primero toma una lista de números y devuelve sólo aquellos que son pares. El segundo revisa una lista de personas del tipo {Género, Edad} y solo mantiene aquellos que son hombres mayores de 60 años. Las similitudes son un poco más difíciles de encontrar aquí, pero tenemos algunos puntos en común. Ambas funciones operan en listas y tienen el mismo objetivo de mantener los elementos que superan alguna prueba (también un predicado) y luego descartar los demás. De esta generalización podemos extraer toda la información útil que necesitamos y abstraerla:

filter(Pred, L) -> lists:reverse(filter(Pred, L,[])).

 

filter(_, [], Acc) -> Acc;

filter(Pred, [H|T], Acc) ->

    case Pred(H) of

        true  -> filter(Pred, T, [H|Acc]);

        false -> filter(Pred, T, Acc)

    end.

Para usar la función de filtrado ahora solo necesitamos realizar la prueba fuera de la función. Compilemos el módulo hhfuns y pruébemoslo :

1> c(hhfuns).

{ok, hhfuns}

2> Numbers = lists:seq(1,10).

[1,2,3,4,5,6,7,8,9,10]

3> hhfuns:filter(fun(X) -> X rem 2 == 0 end, Numbers).

[2,4,6,8,10]

4> People = [{male,45},{female,67},{male,66},{female,12},{unknown,174},{male,74}].

[{male,45},{female,67},{male,66},{female,12},{unknown,174},{male,74}]

5> hhfuns:filter(fun({Gender,Age}) -> Gender == male andalso Age > 60 end, People).

[{male,66},{male,74}]

Estos dos ejemplos muestran que con el uso de la función filter/2, el programador sólo tiene que preocuparse por producir el predicado y la lista. Ya no es necesario pensar en el acto de recorrer la lista para descartar elementos no deseados. Esto es algo importante acerca de la abstracción de código funcional: intenta deshacerse de lo que siempre es igual y deja que el programador proporcione las partes que cambian.

Otro tipo de manipulación recursiva que aplicamos a las listas fue observar cada elemento de una lista uno tras otro y reducirlos a una única respuesta. Esto se llama pliegue y se puede utilizar en las siguientes funciones:

%% find the maximum of a list

max([H|T]) -> max2(T, H).

 

max2([], Max) -> Max;

max2([H|T], Max) when H > Max -> max2(T, H);

max2([_|T], Max) -> max2(T, Max).

 

%% find the minimum of a list

min([H|T]) -> min2(T,H).

 

min2([], Min) -> Min;

min2([H|T], Min) when H < Min -> min2(T,H);

min2([_|T], Min) -> min2(T, Min).

 

%% sum of all the elements of a list

sum(L) -> sum(L,0).

 

sum([], Sum) -> Sum;

sum([H|T], Sum) -> sum(T, H+Sum).

Para encontrar cómo debería comportarse el pliegue, tenemos que encontrar todos los puntos comunes de estas acciones y luego qué es diferente. Como se mencionó anteriormente, siempre tenemos una reducción de una lista a un valor único. En consecuencia, nuestro grupo solo debería considerar la iteración manteniendo un solo elemento, sin necesidad de crear listas. Entonces debemos ignorar los guardias, porque no siempre están ahí: deben estar en la función del usuario. En este sentido, nuestra función de plegado probablemente se parecerá mucho a la suma.

Un elemento sutil de las tres funciones que no se mencionó todavía es que cada función debe tener un valor inicial con el que empezar a contar. En el caso de suma/2, usamos 0 mientras sumamos y dado X = X + 0, el valor es neutral y no podemos estropear el cálculo comenzando allí. Si estuviéramos haciendo una multiplicación, usaríamos 1 dado X = X * 1. Las funciones min/1 y max/1 no pueden tener un valor inicial predeterminado: si la lista fuera solo de números negativos y comenzamos en 0, la respuesta estaría mal. Como tal, necesitamos utilizar el primer elemento de la lista como punto de partida. Lamentablemente, no siempre podemos decidir de esta manera, por lo que dejaremos esa decisión al programador. Tomando todos estos elementos, podemos construir la siguiente abstracción:

fold(_, Start, []) -> Start;

fold(F, Start, [H|T]) -> fold(F, F(H,Start), T).

Y si compilamos:

6> c(hhfuns).

{ok, hhfuns}

7> [H|T] = [1,7,3,5,9,0,2,3].   

[1,7,3,5,9,0,2,3]

8> hhfuns:fold(fun(A,B) when A > B -> A; (_,B) -> B end, H, T).

9

9> hhfuns:fold(fun(A,B) when A < B -> A; (_,B) -> B end, H, T).

0

10> hhfuns:fold(fun(A,B) -> A + B end, 0, lists:seq(1,6)).

21

Prácticamente cualquier función que se te ocurra y que reduzca listas a 1 elemento se puede expresar como un pliegue.

Lo curioso es que puedes representar un acumulador como un solo elemento (o una sola variable), y un acumulador puede ser una lista. Por lo tanto, podemos usar un pliegue para construir una lista. Esto significa que plegar es universal en el sentido de que puedes implementar prácticamente cualquier otra función recursiva en listas con un map y filtro plegado, uniforme:

reverse(L) ->

fold(fun(X,Acc) -> [X|Acc] end, [], L).

 

map2(F,L) ->

reverse(fold(fun(X,Acc) -> [F(X)|Acc] end, [], L)).

 

filter2(Pred, L) -> F = fun(X,Acc) ->

    case Pred(X) of

        true  -> [X|Acc];

        false -> Acc

    end

end,

reverse(fold(F, [], L)).

Y todos funcionan igual que los escritos a mano antes. ¿Qué te parece eso de abstracciones poderosas?

Mapa, filtros y pliegues son sólo una de las muchas abstracciones de las listas proporcionadas por la biblioteca estándar de Erlang. Otras funciones incluyen all/2 y any/2, que toman un predicado y prueban si todos los elementos devuelven verdadero o si al menos uno de ellos devuelve verdadero, respectivamente. Luego tienes drop while/2 que ignorará los elementos de una lista hasta que encuentre uno que se ajuste a un determinado predicado, su opuesto, take while/2, que mantendrá todos los elementos hasta que haya uno que no devuelva verdadero al predicado. Una función complementaria a las dos anteriores es partition/2, que tomará una lista y devolverá dos: una que tiene los términos que satisfacen un predicado determinado, y una lista para los demás. Otras funciones de listas utilizadas con frecuencia incluyen flatten/1, flatlength/1, flatmap/2, merge/1, nth/2, nthtail/2, split/2 y muchas otras.