Estructuras de datos en lenguajes dinámicos. Clojure

En una lección anterior discutimos las estructuras y tipos de datos, pero nos enfocamos en Java exclusivamente, el cual es un lenguaje de tipado fuerte y estático. ¿Qué quiere decir esto? Fuerte quiere decir que la conversión de un tipo de dato a otro está limitada por reglas estrictas y estático quiere decir que el compilador hace el chequeo de tipos en tiempo de compilación, esto es, antes de que el programa se ejecute (tiempo de ejecución).

El conocimiento y familiaridad con las estructuras y tipos de datos es fundamental para resolver cualquier problema de programación. Y es que debemos darle expresión a nuestro problema de dominio mediante una o más estructuras de datos concretas, más allá del tipo de dato específico que tome un dato singular.

Una idea importante dentro de estructuras de datos es la de colección. Como el nombre lo sugiere una colección es un conjunto de cosas, esas cosas en programación son tipos de datos nativos o básicos, esto es, enteros, números de tipo flotante (int y float en Java), cadenas de caracteres (String en Java), booleanos (true o false). Por supuesto, también podemos tener colecciones de tipos de datos compuestos como lo son los structs en Julia y Racket y las clases en lenguajes como Scala, Java, Racket y Python, entre muchos otros.

Ahora bien, una colección no es un conjunto, es una idea más abstracta. De hecho, un conjunto es un tipo de colección. En Clojure tenemos las siguientes colecciones: listas '( ), vectores [ ], mapas { } y conjuntos #{}. Una de las ventajas de Clojure sobre lenguajes como Java y Scala, por ejemplo, es que puedes crear colecciones usando simplemente el literal que identifica a cada colección, en vez de tener que invocar un clase y crear un objeto respectivo. Otra ventaja consiste en que en Clojure existe una misma API (Application Programming Interface), lo que en este contexto significa un conjunto específico de funciones, que puedes usar para trabajar con todo tipo de colección. Eso sí, distinguiendo entre las asociativas como los mapas y las secuenciales como los vectores y listas.

Es importante destacar que pueden agregar celdas en cualquier lugar de la notebook, pueden incluso cambiar su contenido, tomar sus propias notas, etc. Se sugiere mantener la versión original en otra pestaña, en caso que hayan realizado diferentes cambios y hayan perdido el contenido original.

Dicho esto, continuemos.

Listas y vectores

Comencemos con las estructuras de datos secuenciales. En Clojure podemos crear una lista de dos maneras:

(def c (list 1.32 2.3 4.3 4.22 4.023 3.02))

(def l '(13 313 "alfa" :final avalon))

Noten que avalon es un símbolo, pero no está citado (') porque toda la lista ya lo está. Si en otra estructura de datos, como la de arriba, no lo citamos, Clojure tratará de buscar la definición avalon, es decir, lo interpretará como una función. Y al no poder encontrarla, nos arrojará una excepción.

Ahora creemos algunos vectores.

(def v [1233 31434 456 4546 543 23432])

También podemos crear un vector con la función homónima:

(def z (vector 213 424 34 2349439 3893428 1034803403 834390 34894328))

También es posible crear un vector a partir de otra colección, incluso si es asociativa. Para esto usamos la función vec:

(def nums (vec '(1 13 43 34 542 2 24 1 53 2 423)))

(def nums2 (vec #{2 34 21 902 211}))

(def num_map (vec {:a 1 :b 3 :c 334 :d 232}))

Ahora realicemos las operaciones más comunes con colecciones secuenciales, esto es, insertar y remover elementos u obtener el primer elemento, el último, la cola, etc.

Si deseamos agregar un elemento a nuestra lista o vector, empleamos la función conj (que viene del inglés conjoin):

(conj v 23)

(conj l 123312)

No olviden que abajo de la celda, donde se muestra el resultado, pueden hacer click en la flechita y explorar el resultado. Resulta muy útil especialmente en el caso en que obtengamos estructuras anidadas como output.

Ahora bien, inspeccionen las celdas de arriba y noten lo siguiente: en la lista conj agregó el nuevo elemento en primer lugar, mientras que en el vector lo agregó de último. Aunque se trata de la misma función, su conducta es ligeramente diferente en cada estructura de datos. Las razones tienen que ver con la eficiencia de las operaciones, pero no entraremos en ese tema ahora.

Pero si deseamos que nuestro vector tenga el nuevo elemento en primer lugar, podemos usar la función cons:

(cons 12323 v)

Ahora tratemos de quitar un elemento de nuestras colecciones secuenciales. Para ello utilizamos la función pop:

(pop l) 

(pop z)

De nuevo, observen cómo pop tiene una conducta diferente según sea una lista o un vector. Pop remueve el último elemento del vector, mientras que en la lista es el primer elemento el que queda fuera.

Vale la pena destacar que en Clojure las estructuras de datos son inmutables, esto es, no se pueden modificar una vez creadas. Si deseamos transformar una estructura de datos, debemos nombrar la operación de transformación para así obtener la nueva colección (e.g. (def nuevo-vc (conj vc 2323)) ). En cierto sentido, las funciones que estamos conociendo nos sirven para consultar el contenido de la estructura de datos y/o para realizar ciertas transformaciones temporales sobre ella.

Ahora vamos a ver cómo podemos obtener elementos específicos de nuestra colección. Si queremos el primero utilizamos la función first:

(first nums)

(first c)

Podemos incluso pedir el segundo ¡Adivinen! Sí, second:

(second l)

Si deseamos el último llamamos a la función last y, como venimos haciendo, le pasamos como argumento la colección en cuestión:

(last z)

Pero digamos que soy tan caprichoso que quiero el penúltimo también. ¡No hay problema! :

(-> z

  butlast

  last)

¡A ver! ¡¿Qué cosa tan extraña hicimos acá?! Básicamente utilizamos la función butlast que, como su nombre nos sugiere, nos devuelve todo menos el último elemento y sobre el resultado de esta operación llamamos a last. Esta operación está envuelta convenientemente en un macro llamado single threading macro (que sería algo así como macro de hilado simple) que básicamente nos simplifica esta expresión => (last (bustlast z)). Ambas expresiones son equivalentes, pero los macros de hilado hacen el código más legible y elegante.

Si deseo el resto de mi colección, es decir, todo menos la cabeza, uso la función rest:

(rest c)

Noten que los nombres de las funciones son muy intuitivos. Y si tienen alguna duda ya saben que pueden utilizar las funciones doc y find-doc.

Si deseamos algún otro elemento podemos acceder a cualquier lugar de una colección secuencial a través de su índice. Digamos que quiero el cuarto elemento del vector v:

(nth v 4)

Si yerro en el índice, pues éste no existe, obtendré una excepción. Afortunadamente a la función nth podemos pasarle un valor por defecto para que nos sea devuelto en caso que el elemento buscado no exista. Pongamos que devolveremos -1 si el elemento no existe.

(nth nums 19 -1) 

Pero digamos que quiero saber exactamente cuántos elementos tiene mi colección. Para eso está la función count:

(count v)

En este punto creamos tantas colecciones secuenciales que alguno, con derecho, puede estar confundido. ¿Cuál es un vector? ¿Cuál es una lista? ¡Don't panic! Si queremos saber si nuestra colección es un vector llamamos a la función vector?

(vector? z)

(vector? l)

De forma análoga con lista:

(list? nums)

(list? c)

Ahora pasemos a examinar las colecciones asociativas, a saber, los mapas.

Mapas

En Clojure los mapas son una de las colecciones más versátiles y es muy fácil integrarlas en nuestras funciones, por ejemplo, podemos hacer que los argumentos de nuestra función sean las llaves de un mapa. También podemos usar mapas para modelar nuestros problemas de dominio, cosa que en Java u otros lenguajes orientados a objetos haríamos con una clase. Pero eso para más adelante.

Por ahora, lo básico es saber que un mapa almacena los datos en pares de llave y valor. Si queremos un valor, lo obtenemos a través de su llave. Digamos que quiero almacenar la información de un contacto personal:

(def juan {:nombre "Juan"

           :apellido "Perez"

           :dni 212312

           :direccion {:calle "Valle del Rey 48454"

                       :ciudad "Buenos Aires"

                       :codigo_postal 1978}

           :hijos ["Mario" "Fabiana" "Marina"]})

Para obtener el valor de alguno de los campos podemos sencillamente colocar la llave en la posición de función y pasar como argumento el nombre del mapa en cuestión.

(:dni juan)

Si tenemos un mapa anidado, como en el ejemplo, podemos utilizar el macro de hilado simple (noten que la colección siempre va en primer lugar):

(-> juan

  :direccion

  :calle)

También podemos emplear la función get-in:

(get-in juan [:direccion :codigo_postal])

Pudimos alternativamente haber utilizado get para obtener el valor asociado a una llave:

(get juan :apellido)

Si se confunden con el orden de los argumentos que se le pasan a alguna función de las que hemos visto (y cualquier otra, por supuesto) utilicen la función doc para que los asista.

En un mapa se pueden combinar distintos tipos de colecciones. Por ejemplo, acá vemos cómo una de las llaves está asociada a un vector. Así que podemos usar una combinación de criterios de búsqueda asociativos y secuenciales en la medida en que esto tenga sentido en nuestra estructura de datos. Por ejemplo, digamos que queremos saber el nombre del tercer hijo de Juan:

(get-in juan [:hijos 2])

¿Por qué colocamos el índice número 2 en vez de 3? Porque los índices comienzan a contar desde cero. Esto vale para casi todos los lenguajes ( Julia es una excepción).

¡Genial! Ahora deseo agregar nueva información en el mapa. La mascota no puede faltar. Para eso tenemos la función assoc (del inglés associate):

(assoc juan :mascota "Bobby")

Y ¿si deseo agregar nueva información dentro del mapa anidado? Pongamos la comuna y su número. ¡No hay problema!

(assoc-in juan [:direccion :comuna] 11)

¡Juan tuvo un nuevo hijo! Agregémoslo:

(update juan :hijos #(conj % "Ricardo"))

La función update recibe como argumentos el mapa, la llave y una función que nos permitirá actualizar el valor en cuestión. Arriba utilizamos una función anónima. Existen dos sintaxis para las funciones anónimas, una larga y otra corta. La larga es muy similar a la de una función nombrada, a saber, (fn [argumentos] cuerpo_de_la_función). De hecho, defn es una contracción de def y fn. La sintaxis corta es la siguiente: #(cuerpo_de_la_funcion). Los argumentos se pasan a través del literal %. Si hay más de uno se suelen numerar así %1, %2... Así que no hicimos otra cosa que llamar a nuestra conocida función conj y pasarle al vector como parámetro o argumento.

¿Cómo saber cuál sintaxis de función anónima usar? Depende. Hay veces en que resulta más claro usar la sintaxis larga. Lo cierto es que las funciones anónimas son muy útiles cuando necesitamos crear una nueva función ad hoc dentro de una función. En todo caso, no se preocupen si aún no les cae la ficha con este tema, lo profundizaremos más adelante en el curso.

Si deseamos cambiar un valor, en este caso el dni, podemos crear lo que se llama una función constante, esto es, aquellas que independientemente del parámetro devuelven siempre el mismo valor.

(update juan :dni (fn [x] 19324190))

¿Complicado? Usa entonces assoc :

(assoc juan :dni 900002)

Update deberíamos usarlo en realidad cuando la transformación del valor implique alguna clase de cálculo, mientras que para una simple sustitución deberíamos usar assoc.

Por supuesto también tenemos update-in. Digamos que el nuevo valor del código postal es el viejo dividido entre dos:

(update-in juan [:direccion :codigo_postal] #(/ % 2))

No olvidemos que en los lenguajes de la familia Lisp la notación matemática es prefija en vez de infija, esto es, el operador va primero. En una expresión simbólica siempre va la función en primer lugar.

Si deseamos eliminar algo de nuestro mapa, quitamos la llave. Para esto usamos la función dissoc. Juan nos denunció por invasión a su privacidad, así que tendremos que eliminar los datos de su dirección:

(dissoc juan :direccion)

Pero ¡recuerden! En Clojure las estructuras de datos son inmutables, así que sillamamos al mapa juan, toda la información original estará allí. Si deseamos sacar alguna definición de nuestro espacio de nombres (namespace) tendremos que hacer lo siguiente:

(ns-unmap *ns* 'juan)

;arroja excepción si lo des-comentan

;juan

¿Se dieron cuenta que la función se llama un-map? No debe extrañar que el namespace sea una especie de mapa.

Digamos que, como arriba, tengo muchísimas estructuras de datos ¿Cómo sé si la que me interesa es asociativa? Simple:

(associative? juan)

Y ¿los conjuntos? ¿qué son? Preguntémosle a Clojure:

(associative? #{21 3 1223 2312})

¿Serán secuenciales entonces?

(seq? #{989 10 91})

No. Tampoco. ¿Qué son?

Conjuntos

Los conjuntos en Clojure constituyen un tipo de colección particular. Un conjunto es una colección de valores únicos (no repetidos). Se pueden aplicar algunas de las funciones que vimos arriba sobre los conjuntos, pero los conjuntos cuentan con su propia API para soportar operaciones que son típicas para los conjuntos tales como unión, diferencia, intersección, etc. Veamos algunos ejemplos.

(def cartas #{:bastos :espadas :corazones :copas})

Podemos usar algunas operaciones secuenciales como first:

(first cartas)

(last cartas)

Pero si queremos obtener el enésimo (nth) elemento obtendremos una excepción, ya que un conjunto no está indexado.

(nth 3 cartas)

Pero podemos agregar un elemento a un cojunto con conjoin (conj)

(conj cartas :joker)

Para quitar un elemento podemos usar disj (del inglés disjoin)

(disj cartas :bastos)

¡Atención! disj sólo se puede usar con conjuntos.

Podemos contar los elementos de un conjunto:

(count cartas)

Existen dos tipos de conjuntos, los hashsets y los sorted sets. La diferencia radica en que los segundos pueden ordenar sus elementos. Si creamos un mapa con los literales obtendremos un hashset.

(type cartas)

También podemos crearlo con la función hash-set:

(hash-set 2213 213 2131 901)

Pero si deseamos un sorted-set tendremos que crearlo específicamente con la función homónima:

(sorted-set 900 1 23 48 90 67)

Noten que introduje los números sin ningún orden y en la celda del resultado aparecen ordenados.

Con los conjuntos podemos usar la función contains? para consultar su contenido:

(contains? cartas :bastos)

Si deseamos utilizar las funciones propias de los conjuntos de las que hablamos arriba, debemos importar su librería. Podemos hacerlo así:

(use 'clojure.set)

Ahora creemos dos hashsets para hacer los ejemplos:

(def ab #{32423 423 332 3 3442423 34223})

(def cd #{3 423 303 2303934 3201930 240312 3129032 1 343})

Apliquemos la unión de ambos conjuntos:

(union ab cd)

La intersección:

(intersection ab cd)

Y la diferencia

(difference ab cd)

Ejercicios

A continuación plantearemos algunos ejercicios para que practiquen lo aprendido.

Vamos a escribir algunas funciones que nos resolverán un problema determinado. Es importante tener en cuenta que el programador que escribe la función establece el contrato por el que esta se va a regir, es decir, qué tipo de parámetros obtendrá como input y qué arrojará como output.

Ejercicio 1

En un curso de programación se realizó la primera evaluación y el profesor prometió un premio para la calificación más alta. Ayudemos al profesor a saber quién obtendrá el premio. Programe una función que, recibiendo una cantidad n de calificaciones, devuelva la más alta.

TIPS:

• Explore las funciones sort y reverse.

• Puede utilizar el single threaded macro (->)

• Téngase en cuenta que el retorno está definido por la última expresión simbólica en la función y que su tipo será el producto de tal operación;

• Piense en el algoritmo como una secuencia de pequeñas transformaciones que tiene que realizar sobre el input para llegar al output. Como se vio en clases, resulta de mucha ayuda anotar estos pasos primero en un papel y/o escribirlas como comentario en el cuerpo de la función.

(defn calificacion_max

  "Escriba aquí la documentación de su función" 

  [] ;Escriba dentro del vector el nombre del o de los parámetros

     ; Escriba acá el cuerpo de la función

  )

Pruebe su función:

;Cree una estructura de datos de prueba y luego pásela como argumento a su función. Asegúrese que devuelve el resultado correcto.

Ejercicio 2

Un equipo de baloncesto necesita conocer la estatura promedio de sus 12 jugadores. Defínase, a través de la documentación y de la implementación, el input y el output. Establézcase un algoritmo que resuelva el problema (cálculo de un promedio).

TIPS:

• Utilice la función reduce como paso intermedio;

• Recuérdese que en Clojure, como lenguaje dinámico que es, normalmente no se utiliza la declaración de tipos de datos;

• No olviden que se usa notación prefija, es decir, el operador matemático va en primer lugar (e.g. para sumar cuatro números: (+ 1 33 334 32) ).

• Utilice algunos bindings para nombrar el resultado de operaciones parciales y así poder emplear esos valores para realizar cálculos en otras operaciones. Ejemplo, supongamos que quiero devolver un vector con el resultado de la suma, multiplicacion y división de dos números:

(let [a 10.1

      b 89.9

      suma (+ a b)

      mul (* a b)

      div (/ a b)]

  [suma mul div])

Ahora, ¡a resolver el ejercicio!

(defn estatura_promedio

  "Escriba aquí la documentación de su función"

  [] ;Escriba dentro del vector el nombre del parámetro o de los parámetros

  (let [] 

    ;Escriba aquí la expresión simbólicas (s-exp) cuyo resultado será el valor de retorno de la función

    ))

Pruebe su función:

;;Cree un input según el contrato que definió y páselo a su función. Asegúrese que el resultado es el correcto

Ejercicio 3

El Gobierno de la Ciudad nos otorgó un contrato para actualizar el sistema de la SUBE. Nuestra tarea consiste en programar una función que actualice el saldo de la tarjeta (debitar) al realizar un viaje. Abajo, el input que recibirá nuestra función:

(def sube-id-32d21asa {:nombre "Miguel Rodriguez"

                       :dni 18565723

                       :nro_sube 1215415464511

                       :saldo 350})

Cree una función que reciba el mapa anterior como input y devuelva como output el saldo actualizado. No olvide reflexionar sobre cuántos parámetros serán ingresados en nuestra función y cuál es el tipo de dato de cada cual.

(defn debitar-saldo

  "Escriba la documentación de su función"

  []

  )

Pruebe su función:

Ejercicio 4

Una tienda de moda por departamentos aplicará un descuento del 20% sobre todas sus prendas. Se nos pide que actualicemos el programa que marca los precios. Cree una función que recibiendo una lista de precios, devuelva una lista con el descuento correspondiente.

TIPS:

• Investigue sobre las funciones map y mapv.

• Utilice una función anónima, preferiblemente en su versión larga o extendida para mayor claridad (e.g. una función que tome dos parámetros y los multiplique sería así: (fn [a b]

  (* a b)) )

(defn aplicar-descuento

  "Documente su función"

  [] ;;Nombre dentro del vector los parámetros que recibirá la función

  ;; Escriba aquí la expresión de retorno de la función

  )

;; Utilice esta celda para probar su función. La solución de este ejercicio se discutirá en clases.

Soluciones

¿Te trabaste? No hay problema. Aquí puedes mirar las soluciones (téngase en cuenta que una solución correcta no tiene que lucir exactamente como éstas)

Ejercicio 1

(defn calif-max

  [vc]

  (-> vc

    sort

    last))

Prúebenla:

Ejercicio 2

(defn alt_avg

  [altrs]

  (let [suma (reduce + altrs)

        cant (count altrs)]

    (/ suma cant)))

Prueben:

(def alts [1.232 1.89 1.27 1.90 2.05])

(alt_avg alts)

Ejercicio 3

(defn deb-saldo

  [sube costo]

  (:saldo ;; Como update devuelve un mapa, utilizamos la llave que nos interesa para devolver el resultado.

   (update sube :saldo #(- % costo))))

¡A probar!