Práctica 4 - Ejercicio 16

Avisen si algo está mal... 😉

I) problema cantApariciones (l:[T]) = res:[(T,int)], que devuelve la lista con todos los elementos de l, sin duplicados y en el mismo orden, cada uno junto con su cantidad de apariciones.

problema cantApariciones (l:[T]) = res:[(T,int)]{
requiere |l|>0;
asegura \(\forall i,j \in [0..|l|), |res| = = |[l_i | l_i \not= l_j, i\not=j]|;\)
asegura \(\forall i \in [0..|res|), j \in [0..|l|), prm (res _i) = = l_j;\)
asegura \(\forall i \in [0..|res|), sgd (res_i) = = cuenta (prm (res_i), l);\)
}

V) problema interseccionMultiple (ls:[[T]]) = l:[T], que devuelve en l el resultado de la intersección de todas las listas de ls. Es importante no imponer un orden.

problema interseccionMultiple (ls:[[T]]) = l:[T] {
requiere |ls|>0
asegura \(\forall i \in [0..|l|), mismos (l,[interseccion(ls_i)]);\)
aux \(interseccion (a,b:[T]):[T] = [c|c \in a \wedge c \in b];\)
}

Gracias!

Hola Gise, te cuento lo que me pareció ver...

En cantApariciones, por qué requeris que la lista sea no vacía? Estás segura de que esto te devuelve los elementos nuevos en el mismo orden en el que estaban antes? Podés armar la lista por comprensión recorriendo las posiciones de los elementos, para garantizar el orden. Algo de la forma \([l_i | i \leftarrow [0..|l|)]\).

En la intersección lo mismo, podrías intersecar dos listas vacías y te daría una lista vacía. En general pedís que la lista sea no vacía cuando el resultado es un elemento, con lo cual necesitás sí o sí que haya algún elemento en el argumento.

Esto me parece que no tipa \((\forall i \leftarrow [0..|l|))(mismos(l, [interseccion(ls_i)]))\), fijate que la función intersección recibe 2 listas.

Cualquier cosa preguntá, saludos ^^

Mmm... cierto... se me escapó ese detalle.

A ver si ahi queda mejor el (V):

problema interseccionMultiple (ls:[[T]]) = l : [T] {
asegura \(\forall i,j \leftarrow [0..|ls|) i \neq j, mismos(l, interseccion (ls_i, ls_j));\)
}
aux \(interseccion (a,b : [T]) : [T] = [c | c \in a \wedge c \in b];\)

Como en el caso anterior, buscá ejemplos que te den una idea. Mirá este contrajemplo con la lista \([[1],[1,2],[1,2,3]]\)

\(interseccionMultiple([[1],[1,2],[1,2,3]])\) me asegura (según tu solución) que \([1,2]\) es una solución posible, porque si para todo par de índices distintos entre sí, se cumple el asegura, en particular se cumple para los índices \(i=1, \, j=2\) entonces por ejemplo \(mismos(l,interseccion([1,2],[1,2,3])) = mismos(l, [1,2]) \rightarrow l = [1,2]\), sin embargo, la solución debería ser \([1]\)

Por otra parte, como \(mismos\) no me dice si hay o no elementos repetidos en las listas (sólo me dice si son los mismos)... entonces \(l= [1,2,1,1,2]\) también es una solución... total sigue teniendo los mismos elementos. Para evitar esto, tenés que explicitar además cuántos elementos va a tener el resultado, por ejemplo \(asegura \, |l| = n\).

Moraleja, buscá ejemplos sencillos que te den una intuición de lo que querés formalizar.