aprendiendo ( Erlang ).

miércoles, 28 de septiembre de 2011

Colas (queues)

| 0 comentarios |

Tengamos en mente una fila ( a partir de ahora cola (Queue)) de personas esperando turno. El primero de la fila es la persona que más tiempo lleva y por tanto la primera en ser atendida. Y consecuentemente, el último de la cola será el menos tiempo lleva esperando y el último en ser atendido. Esto es lo que, en el argot se llama una estructura de datos FIFO (First Input First Output), es decir, el primero en entrar es el primero en salir.
Erlang implementa este TAD en el módulo queue de forma eficiente. Se trata de una implementación muy completa que nos permite hacer operaciones inversas (sufijo "_r"). La implementación de operaciones invertidas o inversas nos permitirá utilizar la cola como una cola LIFO (Last Input First Output), es decir, una pila (Stack). De echo, Erlang no provee de un módulo para la implementación del TAD pila.
El módulo incorpora tres conjuntos de funciones:
  1. API Original
  2. API Extendida
  3. API Okasaki

API Original

Implementación original del TAD. Se trata de una implementación completa de cola, con la cual ya podemos trabajar y tener toda la funcionalidad necesaria. Las funciones de la implementación son:
  • new() -> Cola: crea una cola vacía.
  • is_queue(Término) -> true | false: si el término es una cola entonces true.
  • is_empty(Cola) -> true | false: comprueba si la cola esta vacía.
  • len(Cola) -> N: calcula la longitud de la cola.
  • in(Elemento, Cola1) -> Cola2: encola el elemento, es decir, lo introduce al final.
  • in_r(Elemento, Cola1) -> Cola2: introduce el elemento al principio de la cola.
  • out(Cola1) -> {{value, Elemento}, Cola2} | {empty, Cola1}: saca el primer elemento de la cola. Devuelve el elemento y la cola sin el elemento. Si la cola es vacía devuelve {empty, Cola1}.
  • out_r(Cola1) -> {{value, Elemento}, Cola2} | {empty, Cola1}: saca el último elemento de la cola.
  • from_list(Lista) -> Cola: crea una cola con los elementos, y orden, de la lista.
  • to_list(Cola) -> Lista: retorna una lista como representación de la cola.
  • reverse(Cola1) -> Cola2: devuelve la cola invertida.
  • split(N, Cola1) -> {Cola2, Cola3}: divide una cola en dos. Los n primeros elementos en la primera Cola y el resto en otra.
  • join(Cola1, Cola2) -> Cola3: concatena dos colas
  • filter(Fun, Cola1) -> Cola2: realiza un filtro sobre la Cola, en el orden de cabeza a cola. La función Fun tiene el formato fun(Elemento) -> boolean | Lista. Si nuestra función Fun para el filtro retorna un booleano el comportamiento es el normal, es decir, si true incluye el elemento en la cola resultante, sino lo ignora. Pero si la función Fun devuelve una lista en la posición donde debe ir el elemento incluirá los elemento de la lista.
  • member(Elemento, Cola) -> Boolean: comprueba si el elemento esta en la cola.
Vamos a crear las estructuras de datos necesarias para trabajar. Un par de colas A = [1,2,3], B=[4,5,6,7] y sobre ellas realizaremos las operaciones.
1> A = queue:from_list([1,2,3]).
{[3],[1,2]}
2> B = queue:from_list([4,5,6,7]).
{[7,6],[4,5]}
3> queue:len(A).
3
4> queue:len(B).
4
5> queue:to_list(queue:reverse(A)).
[3,2,1]
6> queue:to_list(queue:reverse(B)).
[7,6,5,4]
7> queue:to_list(queue:join(A,B)). 
[1,2,3,4,5,6,7]
8> queue:split(2,A).               
{{[2],[1]},{[],[3]}}
9> queue:is_empty(A).
false
10> queue:is_empty(queue:new()).
true
11> queue:to_list(queue:in(4,A)).  
[1,2,3,4]
12> queue:to_list(queue:in_r(0,A)). 
[0,1,2,3]
13> queue:out(A).               
{{value,1},{[3],[2]}}
14> queue:out_r(A).
{{value,3},{[2],[1]}}
15> queue:member(2, A).
true
16> F1 = fun (X) -> X >= 3 end.
#Fun
17> F2 = fun (X) -> [{ok, X}] end.
#Fun
18> queue:to_list(queue:filter(F1, A)).
[3]
19> queue:to_list(queue:filter(F2, A)).
[{ok,1},{ok,2},{ok,3}]
Por último, decir que, el comportamiento habitual de una cola es el FIFO y para este comportamiento utilizaremos la funciones no inversas (in/2 y out/1). Para el comportamiento LIFO utilizaremos la funciones invertidas o reversas (in_r/2 y out_r/1).

API extendida

Conjunto de funciones alternativas a la implementación original. Estas funciones son más limpias, en el sentido de que no retornan estructuras del tipo {{value, Elemento}, Cola}, como el API Original. Proporcionando o permitiendo tener un código más limpio al usuario del módulo.
  • get(Cola) -> Elemento: devuelve el primer elemento de la cola (Falla si la cola es vacía).
  • get_r(Cola) -> Elemento: devuelve el último elemento de la cola (Falla si la cola es vacía).
  • drop(Cola1) -> Cola2: elimina de la cola el primer elemento (Falla si la cola es vacía).
  • drop_r(Cola1) -> Cola2: elimina de la cola el último elemento (Falla si la cola es vacía).
  • peek(Cola) -> {value,Elemento} | empty: devuelve el primero elemento de la cola o empty si es vacía.
  • peek_r(Cola) -> {value,Elemento} | empty: devuelve el último elemento de la cola o empty si es vacía.
Veamos su comportamiento en la consola.
20> queue:get(A).
1
21> queue:get_r(A).
3
22> queue:to_list(queue:drop(A)).      
[2,3]
23> queue:to_list(queue:drop_r(A)).
[1,2]
24> queue:peek(A).                 
{value,1}
25> queue:peek_r(A).
{value,3}
Para gustos ... colores. Se pueden ver dos grandes diferencias entre la implementaciones:
  1. En la implementación extendida hay que tener en cuenta que la cola no sea vacía.
  2. En la implementación original utilizábamos out/1 para sacar elementos y borrarlos de la cola. En la extendida se realiza en dos pasos: el primero los obtenemos con get/1 o peek/1; y por último, lo borramos con drop/1.

API Okasaki

El señor Chris Okasaki en la Universidad de Carnegie & Mellon, tuvo a bien obsequiarnos con su tesis Purely functional data structures. El módulo Queue implementa el concepto de cola señor Okasaki. Esta interfaz puede resultar extraña por la nomenclatura que utiliza.
  • cons(Elemento, Cola1) -> Cola2: inserta el elemento en la cabeza de la cola.
  • snoc(Cola1, Elemento) -> Cola2: inserta el elemento al final.
  • head(Cola) -> Elemento: retorna el primer elemento (Puede falla si la cola es vacía).
  • daeh(Cola) -> Elemento: retorna el último elemento (Puede falla si la cola es vacía).
  • last(Cola) -> Elemento: retorna el último elemento (Puede falla si la cola es vacía).
  • tail(Cola1) -> Cola2: devuelve una cola sin el primer elemento (Puede falla si la cola es vacía).
  • liat(Cola1) -> Cola2: devuelve una cola sin el último elemento (Puede falla si la cola es vacía).
  • init(Cola1) -> Cola2: devuelve una cola sin el último elemento (Puede falla si la cola es vacía).
Lo más llamativo de esta implementación es la nomenclatura. Utiliza nombres de funciones (head) para realizar una acción y el mismo nombre al revés (daeh) para realizar la funcionalidad inversa.
26> queue:head(A).               
1
27> queue:daeh(A).
3
28> queue:to_list(queue:tail(A)).
[2,3]
29> queue:to_list(queue:liat(A)).
[1,2]
30> queue:to_list(queue:cons(0,A)).
[0,1,2,3]
31> queue:to_list(queue:snoc(A,4)).  
[1,2,3,4]
32> queue:to_list(queue:init(A)).
[1,2]
33> queue:last(A).               
3
Desde mi punto de vista, esta implementación queda poco clara y confusa. Prefiero las otras implementaciones.

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.