aprendiendo ( Erlang ).

martes, 20 de septiembre de 2011

Conjuntos (Sets).

| 0 comentarios |

En este post, vamos a trabajar con el módulo sets, conjuntos como su propio nombre indica. Se trata de un módulo para el tratamiento del tipo abstracto de datos conjunto.

Todos sabemos que un conjunto es una colección de objetos cuyos elementos no tienen un orden específico, ni se pueden repetir.

Las funciones que contiene el módulo sets son:
  • add_element(Elemento, Conjunto1) -> Conjunto2: añade un elemento al conjunto.
  • del_element(Elemento, Conjunto1) -> Conjunto2: borra un elemento del conjunto.
  • filter(Predicado, Conjunto1) -> Conjunto2: realiza un filtro sobre el conjunto de elementos.
  • fold(Función, Acc0, Conjunto) -> Acc1: realiza un fold sobre el conjunto de elementos.
  • from_list(Lista) -> Conjunto: crea un conjunto con los elementos de la lista.
  • intersection(Lista_Conjuntos) -> Conjunto: realiza la intersección de los conjuntos de la lista.
  • intersection(Conjunto1, Conjunto2) -> Conjunto3: realiza la intersección de dos conjuntos.
  • is_element(Elemento, Conjunto) -> bool(): indica si el elemento pertenece al conjunto.
  • is_set(Conjunto) -> bool(): test de comprobación de tipo.
  • is_subset(Conjunto1, Conjunto2) -> bool(): comprueba si un conjunto es subconjunto de otro.
  • new() -> Conjunto: crea un conjunto vacío.
  • size(Conjunto) -> int(): devuelve el número de elementos del conjunto.
  • subtract(Conjunto1, Conjunto2) -> Conjunto3: realiza la diferencia de conjuntos.
  • to_list(Conjunto) -> Lista: convierte un conjunto a lista.
  • union(Lista_Conjuntos) -> Conjunto: realiza la unión de todos los conjuntos de la lista.
  • union(Conjunto1, Conjunto2) -> Conjunto3: realiza la unión de dos conjuntos.
Para comprobar el comportamiento y explicar la funcionalidad de este TAD, voy a crear tres conjuntos numéricos A={1,2,3,5}, B={2,3,4}, y C={3,5,6} de la siguiente forma:
1> A = sets:from_list([1,2,3,5]).
{set,4,16,16,8,80,48,
     {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
     {{[],[3],[],[],[],[],[2],[5],[],[],[],[1],[],[],[],[]}}}
2> B = sets:from_list([2,3,4]).   
{set,3,16,16,8,80,48,
     {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
     {{[],[3],[],[],[],[],[2],[],[],[],[],[],[4],[],[],[]}}}
3> C = sets:from_list([3,5,6]).
{set,3,16,16,8,80,48,
     {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
     {{[],[3],[6],[],[],[],[],[5],[],[],[],[],[],[],[],[]}}}
4> sets:size(A). 
4
Ahora, lo que toca es realizar operaciones con los conjuntos A, B y C. He convertido todos los resultado de conjuntos a listas, para comprobar visualmente los resultados.
5> sets:to_list(sets:union(A,B)).
[3,2,5,1,4]
6> sets:to_list(sets:union([A,B,C])).
[3,6,2,5,1,4]
7> sets:to_list(sets:intersection(A,B)).
[3,2]
8> sets:to_list(sets:intersection(B,C)).
[3]
9> sets:to_list(sets:intersection([A,B,C])).
[3]
10> sets:to_list(sets:subtract(A,B)).
[5,1]
11> sets:to_list(sets:subtract(B,A)).
[4]
12> sets:to_list(sets:subtract(A,C)).
[2,1]
Para modificar los conjuntos tenemos el sets:add_element/2 y el sets:del_element/2 que nos permite añadir y borrar elementos del conjunto. Recuerda que los conjuntos no admiten elementos duplicados (comando 15).
13> sets:to_list(sets:add_element(7, B)).
[3,2,4,7]
14> sets:to_list(sets:add_element(7, C)).
[3,6,5,7]
15> sets:to_list(sets:add_element(3, C)).
[3,6,5]
17> sets:to_list(sets:del_element(3, C)).
[6,5]
16> sets:is_element(3, C).              
true
Y para finalizar, las funciones de alto nivel. El filtro (sets:filter/2) y la función fold (sets:fold/3) implementadas para conjuntos.
17> Predicado = fun (X) -> X > 5 end.
#Fun
18> sets:to_list(sets:filter(Predicado, C)).
[6]
19> Funcion = fun (X, Acc) -> Acc + X end.
#Fun
20> sets:fold(Funcion, 0, C).               
14
Para ilustrar la función sets:filter/2 he realizado un filtro para elementos mayores que cinco, sobre el conjunto C. Y para comprobar el comportamiento de la función sets:fold/3 he realizado el sumatorio sobre los elementos del conjunto C.
Pero ..., ¿es qué no hay foldr ni foldl? Pues no, no hay, y la respuesta es bien sencilla, No hay orden y por lo tanto, ¿cuál es el lado derecho o izquierdo del conjunto?

Publicar un comentario en la entrada

0 comentarios:

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