Scala de la muerte

¡Cuanto tiempo!  A punto de comenzar de nuevo la universidad he estado haciendo ciertos cursos en los que estoy aprendiendo Scala y Python.  Hoy os voy a poner un ejercicio que he tenido que hacer en Scala.

Tenemos que implementar de alguna manera los conjuntos. Es decir, secuencias finitas o infinitas de números agrupados por una función.
Ejemplos:  El conjunto V = { 1,3,5,7}  es un conjunto que me acabo de inventar. Tiene 4 números primos como podemos ver pero es finito por lo que no son todos los números primos. Otro conjunto sería los pares, osea “Para todo x € Z | x % 2 == 0”, esto es { …,-4 -2, 0, 2, 4…} y por tanto infinito.

Así que la primera duda será: ¿ Cómo logramos definir algo infinito en un ordeandor? La pregunta no es sencilla pero la respuesta sí: Con un booleano. Si nos fijamos los pares cumplen la condición x % 2 == 0, así que el conjunto será dado un entero, ¿Esté pertenece o no al conjunto?

type Set = Int => Boolean

Y así definimos el tipo conjunto (Set).
Ahora deberíamos pensar en como hacer conjuntos finitos. Para esto no podemos usar simplemente una expresión booleana sino que tendremos que añadirlos uno a uno. Así que definimos una función tal que pasado un elemento nos devuelva un set con sólo ese elemento:

  def singletonSet(elem: Int): Set = a => a == elem

Muy bien, ahora usando

val s1 = singletonSet(1)

podemos crear un set de un sólo elemento. ¿Y cómo añadimos más? Para eso podemos ver en la wikipedia las operaciones posibles. *** NOTA: Operaciones entre conjuntos DAN como resultado conjuntos ***

Para unir conjuntos tenemos que usar la unión de ellos, es decir, dado dos conjuntos un elemento esta en uno o en el otro:

def union(s: Set, t: Set): Set = a => s(a) || t(a)

¿Y para saber cuales elementos tienen en común? La intersección:

  def intersect(s: Set, t: Set): Set = a => s(a) && t(a)

¿Y si no queremos que en un conjunto haya elementos del otro? La diferencia:

  def diff(s: Set, t: Set): Set = a => s(a) && !t(a)

Podemos hace más operaciones así. Pero ahora nos piden otra cosa. Para un conjunto S, ¿Qué elementos de ese conjunto cumplen la propiedad p?

  def filter(s: Set, p: Int => Boolean): Set = a => s(a) && p(a)

Fácil, ¿No?

¿Y si queremos comprobar que TODOS los elementos en S cumplen la propiedad p? Para conjuntos infinitos eso puede ser una tarea… eh… infinita. Así que nos vemos obligados(para esta implementación, sé que hay gente lo ha hecho de otra manera) a poner un límite.

val bound = 1000

Una vez que tenemos el límite ya podemos iterar sobre cada elemento, uno a uno, y comprobar que satisface o no p:

  def forall(s: Set, p: Int => Boolean): Boolean = {
    def iter(a: Int): Boolean = {
      if (a > bound) true
      else if (s(a) && !p(a)) false
      else iter(a + 1)
    }
    
    iter(-bound)
  }

Notar que empezamos en -bound, es decir, desde -1000 hasta 1000.

Ya casi para terminar podemos exigirle al conjunto que nos diga si almenos un elemento, osea, existe un elemento en S que cumpla P. Al menos uno, no todos ni ninguno, con que haya uno nos vale.
De nuevo, ¡Wikipedia al rescate!

Si nos fijamos en la relación que tienen:
Relacion
Se lee: Para todo x € S se cumple P ES EQUIVALENTE A que NO hay al menos un elemento que NO cumpla P. Es decir que todos lo cumplen.
Podemos cambiarla de tal manera que el “Para todos” este en el lugar de “Existe” y viceversa. Con lo cual se leería: Existe x € S que cumple P ES EQUIVALENTE A que NO todos x€S NO cumplen P. Es decir que si de todos los elementos de S al decir que no cumplen P devuelve Falso, entonces es que hay al menos uno que SI lo cumple.

 def exists(s: Set, p: Int => Boolean): Boolean = !forall(s, x => !p(x))

Para terminar el más complicado de todos y con el que más ayuda me hizo falta porque no lo entendía.
Dado un conjunto aplicarle una función. Por ejemplo, si nos dan el conjunto de los pares y le aplicamos la funcion (x + 1), tenemos el conjunto de los impares. Si tenemos los números primos y la función (x * 2) tendremos el doble de los números primos.

 def map(s: Set, f: Int => Int): Set =  elem => exists(s, x => f(x) == elem)

Lo voy a leer literalmente: Dado un elemento elem pertenece al conjunto si existe en el conjunto S una x que al aplicarle la función sea igual al elemento. ¿Tiene su lógica no? Pues fue difícil y creo que sin ayuda de mi amigo no lo hubiese logrado >.<

Sin más esto es todo por hoy. Como siempre el proyecto estará en la carpeta de dropbox.

Un saludo!

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s