aprendiendo ( Erlang ).

viernes, 1 de abril de 2011

Listas

| 0 comentarios |

Ahora que ya hemos visto las Fun's y la funciones de alto nivel, vamos a profundizar un poco más en el tema de las listas. Ya vimos los conceptos básicos en el post de tipos básicos.
Empecemos por crear una función muy muy clásica, sum. Todas la funciones de este post's las englobare en un módulo llamado originalmente listas.erl.
sum([H|T]) ->
    H + sum(T);
sum([]) ->
    0.
Creo que todo el mundo, llegará a la misma conclusión que yo, esta función recorre una lista y suma sus elementos.
La primera clausula, es lo que se llama en el argot caso general, tomamos el primer elemento de la lista, cabeza, y aplicamos la suma al resto de lista, cola. Lo normal es que existan más de un caso general.
La segunda clausula, es lo que se llama caso base, ¿qué pasa si ya no tenemos elementos? pues nada, la suma de una lista vacía es 0. Puede existir más de un caso base.
NOTA: El orden de las clausulas son importantes, no en el caso de sum. Erlang comprueba, según el orden de implementación, con que clausulas hace matching y puede ejecutar. Hay que tener cuidado con esto.
1> c(listas).
{ok,listas}
2> listas:sum([4,2,4,5]).
15
Bueno, ya hemos comprobado que funciona nuestra función y vemos que hace lo que esperábamos. Pero... ¿cómo ha evaluando la función?
  1. listas:sum([4,2,4,5]) comprueba con que clausula hace matching en el módulo y determina que la primera clausula es la que debe ejecutar.
  2. sum([4,2,4,5]) = 4 + sum([2,4,5])
  3. sum([2,4,5]) = 2 + sum([4,5])
  4. sum([4,5]) = 4 + sum([5])
  5. sum([5]) = 5 + sum([])
  6. sum([]) = 0 caso base
  7. sum([5]) = 5 + 0 = 5
  8. sum([4,5]) = 4 + 5 = 9
  9. sum([2,4,5]) = 2 + 9 = 11
  10. sum([4,2,4,5]) = 4 + 11 = 15
Es interesante saber como se comporta Erlang, y cualquier lenguaje, al evaluar una función tan básica ya que vamos ha realizar y evaluar alguna más complejas.
map(_, []) ->
    [];
map(F, [H|T]) ->
    [F(H) | map(F, T)].
Pero tío, te has pasado, pero ¿qué es esto? suena a chino. No pasada nada tenemos conocimiento de sobra para implementar nuestra propia función map. Recordemos lo que vimos en el post anterior (Funciones de alto nivel. Fun's.). La función map toma como argumentos una función de aridad 1 y una lista, y evalúa para cada elemento de la lista la función pasada. El resultado es una nueva lista resultante de aplicar la función a los elementos de la lista original.
La primera clausula, recibe un me da igual (_) y una lista vacía, es decir, que cuando recibe un lista sin elementos a los que aplicar la función, devolvemos una lista vacía. Es nuestro caso base para esta función.
La segunda clausula o caso general, aplicamos la función a la cabeza de la lista y lo ponemos a la cabeza de la nueva lista y como cola el resultado de aplicar la función F a los elementos de la cola original. Leches ... si es el resultado de hacer map a la cola de la lista original.
Funcionará... haber, haber...
3> c(listas).
{ok,listas}
4> listas:map(fun(X) -> X+1 end, [4,2,4,5]).
[5,3,5,6]
Tachaaaaann. Aunque es una implementación valida he de decir que existen otras formas más elegantes de implementar un map.
Pues ya que estamos lanzados, vamos ha realizar una implementación de filter. Veamos como:
filter(_,[]) ->
    [];
filter(F,[H|T]) ->
    filter(F(H),F,H,T).

filter(true,F,H,T) ->
    [H | filter(F,T)];
filter(false,F,_,T) ->
    filter(F,T).
Si, yaaaa... Se que existen formas mejores de implementarlo pero es que aun no hemos visto ni listas por compresión, ni guardas, ni sentencias de control. Bueno, la implementación no es la más efectiva pero como nos puede valer.
La función filter/2 tiene como en el caso de map dos clausulas, el caso base y el caso general. Además se a implementado una función auxiliar que nos hace las veces de sentencia if. Es decir, que si la función pasada es true añade el elemento a la lista resultante y en otro caso, no. Veamos si funciona.
5> c(listas).
{ok,listas}
6> listas:filter(fun(X) -> X rem 2 =:= 0 end, [1,2,4,2,1,5]).
[2,4,2]
Vamos con la última implementación casera. Ahora le va a tocar a la función delete/2, y su misión es eliminar un elemento de la lista.
delete(_,[]) ->
    [];
delete(X,[X|T]) ->
    T;
delete(X,[H|T]) ->
    [H | delete(X,T)].
En este caso, tenemos dos casos base y uno general. La primera clausula es la típica situación en la cual ya no hay más elementos. La segunda es para el caso en el que encontramos el elemento en la lista y en ese caso, ignoramos el elemento y nos quedamos con el resto. Y el caso general, es para cuando no hemos encontrado el elemento, por lo que, generamos una nueva lista con la cabeza actual y el resultado de seguir borrando en la cola.
7> c(listas).
{ok,listas}
8> listas:delete(1,[2,4,1,4,2,1,9]).
[2,4,4,2,1,9]
Vemos como nuestra función delete/2 realiza lo que esperamos de ella. En este caso, el orden de las clausulas es determinante. Prueba a intercambiar las dos últimas clausulas. Jijijiji ;).
Todas estas funciones y más están implementadas en el módulo lists y podemos hacer uso de ellas realizando la correspondiente importación -import(lists, [map/2, sum/1]).

Publicar un comentario

0 comentarios:

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