LUA / Sets y bags

Bienvenidos sean a este post, supongamos que quieres listar todos los identificadores usados en un codigo fuente, de alguna forma necesitas filtrar las palabras reservadas de tu listado, los programadores de C puede sentir la tentacion de utilizar un conjunto (set) de palabras reservadas como un array de cadenas para luego buscar en el mismo y saber cuando una palabra de estas esta en el conjunto, inclusive para acelerar la busqueda podriamos incluso usar un arbol binario para representar el conjunto.

En Lua una forma eficiente y simple para representas tales conjuntos es poner el conjunto de elementos como indices de una tabla, luego en lugar de buscar en la tabla por un elemento informado solo indexa la tabla y verifica que el resultado es nil o no, para ejemplificar esto podemos usar el siguiente codigo:

reservada = {
	["while"] = true,	["and"] = true,
	["function"] = true,	["local"] = true,
}

for p in palabrasTodas() do
	if not reservada[p] then
		< ... instrucciones con p ... >
	end
end

Primero creamos una tabla donde almacenamos las palabras reservadas que queremos omitir, en todos los casos le asignamos el valor de true, nuestro siguiente paso sera un bucle for para buscar palabra por palabra por medio de palabrasTodas, en el bucle chequearemos que de la tabla reservada con el indice p sea distinta de true, o sea false, y en este caso ejecutaremos instrucciones relacionadas a esa palabra omitiendo a la palabra reservada.

Nota: La sintaxis utilizada en la tabla es debido a que al ser reservadas no pueden usadas directamente como identificadores, p.e while = true, y por eso debemos usar ese tipo de anotacion.  

Para iniciar de forma mas clara nuestro conjunto podemos usar una funcion auxiliar como en el siguiente codigo:

function Set (lista)
	local set = {}
	for _,l in ipairs(lista) do set[l] = true end
	return set
end

reservada = { "while", "and", "function", "local", }

En este caso crearemos una funcion llamada Set la cual recibira una lista (o una tabla), primero crearemos una tabla local llamada set, luego usaremos un bucle donde haremos que use ipairs para que pase por lista y cada una de ellas la agregara a set con el indice l y le asignara el valor true, despues regresara el valor final de set, observen como en reservada ahora solamente pasamos las palabras reservadas sin ningun valor.

Nota: la variable _ que se utilizo en el for es una variable desechable, no tiene un significado real sino que simplemente representa que el valor indicado no es importante, tambien suele usarse mucho en iteradores.

Bolsos (bags) son tambien llamados multiconjuntos (multisets) difieren de los conjuntos regulares en que cada elemento podria aparecer multiples veces, una representacion simple para los bolsos en Lua es similar a la representacion previa de los conjuntos pero donde asociamos un contador con cada clave, veamos a continuacion un ejemplo de como insertar un dato:

function insertar(bolso, elemento)
	bolso[elemento] = (bolso[elemento] or 0) + 1
end

Para removerlo solamente debemos reducir su contador:

function remover(bolso, elemento)
	local contar = bolso[elemento]
	bolso[elemento] = (contar and contar > 1) and contar -1 or nil
end

Solo mantenemos el contador si todavia existe y si es mayor que cero.

En resumen, hoy hemos vistos conjuntos (sets) y bolsos (bags), como son, para que se usan, como se implementan y que facilidades nos proveen, espero les haya sido util sigueme en Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.