Bolsa (informática)

Una bolsa es, en informática, un tipo abstracto de datos. Se trata de una colección de un número arbitrario de elementos (todos del mismo tipo) que no son necesariamente distintos, junto con una serie de procedimientos de acceso.

La especificación es muy parecida a la del TAD conjunto. La diferencia es que si hay elementos repetidos permanecen todas las ocurrencias. En los conjuntos solo queda una de las ocurrencias. Al número de veces que un elemento aparece en la bolsa se denomina multiplicidad.

Operaciones

Crear: crea una bolsa vacía.
Eliminar: solo elimina una ocurrencia del elemento que se borra.
Cardinal: cuenta como distintas todas las repeticiones de un mismo elemento.
Agregar: agrega el elemento en la bolsa no importa si esta antes.

Bolsa en MAUDE

A continuación mostraremos una posible especificación del tipo abstracto Bolsa para Maude con sus operaciones más usuales.

fmod BOLSA {X :: TRIV} is
pr INT .
sort Bolsa{X} .

*** generadores

op crear : -> Bolsa{X} [ctor] .
op {_} : X$Elt -> Bolsa{X} [ctor] .
op _U_ : Bolsa{X} Bolsa{X} -> Bolsa{X} [ctor comm assoc id: crear] .

*** constructores

op agregar : X$Elt Bolsa{X} -> Bolsa{X} .
op eliminar : X$Elt Bolsa{X} -> Bolsa{X} .
ops interseccion : Bolsa{X} Bolsa{X} -> Bolsa{X} [assoc comm] .
ops diferencia : Bolsa{X} Bolsa{X} -> Bolsa{X} .
*** selectores
op _perteneceA_ : X$Elt Bolsa{X} -> Bool .
op cardinal : Bolsa{X} -> Nat .
op repeticiones : X$Elt Bolsa{X} -> Nat .

*** variables

vars E E2 : X$Elt .
vars B B2 B3 : Bolsa{X} .
*** ecuaciones
eq agregar(E, B) = {E} U B .

eq eliminar(E, crear) = crear .
eq eliminar(E, {E2}) = if E == E2 then
crear
else
{E2}
fi .
eq eliminar(E, B U B2) = if E perteneceA B then
eliminar(E, B) U B2
else
B U eliminar(E, B2)
fi .

eq repeticiones(E, crear) = 0 .
eq repeticiones(E, {E2}) = if E == E2 then
1
else
0
fi .
eq repeticiones(E, B U B2) = repeticiones(E, B) + repeticiones(E, B2).

eq E perteneceA crear = false .
eq E perteneceA {E2} = E == E2 .
eq E perteneceA B U B2 = E perteneceA B or E perteneceA B2 .

eq cardinal(crear) = 0 .
eq cardinal({E}) = 1 .
eq cardinal(B U B2) = cardinal(B) + cardinal(B2) .

eq interseccion(crear, B) = crear .
eq interseccion({E}, B) = if E perteneceA B then
{E}
else
crear
fi .
eq interseccion({E} U B, B2) = if E perteneceA B2 then
{E} U interseccion(B, eliminar(E, B2))
else
interseccion(B, B2)
fi .

eq diferencia(B, crear) = B .
eq diferencia(B, {E}) = if E perteneceA B then
eliminar(E, B)
else
B
fi .
eq diferencia(B, B2 U B3) = diferencia(diferencia(B, B2), B3) .

endfm

Datos: Q5731640