miércoles, 24 de febrero de 2010

Ejemplo básico Clojure y IV: multiplicar números como listas.

Como las masas que siguen este blog son muy tímidas vamos a ponernos manos a la obra para conseguir que la ultima versión de nuestra función para multiplicar listas funcione correctamente. El error es muy básico pero vamos a seguir los pasos para detectarlo y arreglarlo. En Clojure no se sigue el proceso cíclico de codificar-compilar-debuguear-probar tan familiar para los que programamos en lenguajes compilados mas torpes como java. En Clojure (como en todos los lenguajes dinámicos y los estáticos mas modernos) tenemos siempre disponible el REPL (Read-Evaluation-Print-Loop) que es un entorno interactivo de programación, una consola donde podemos escribir código, que es evaluado por el interprete presentándose el resultado en la consola. De hecho ya la he expuesto en todos los fragmentos tal que así:

> (codigo a evaluar)
resultado


El REPL permite una programación dinámica e interactiva ya que tenemos una respuesta inmediata a nuestras pruebas e investigaciones. Vamos a usarla para diagnosticar el problema. Recordemos como era la función:

(defn multLists [xs ys]
(let [mults (reduce #(cons (multList %2 xs) %1) '() ys)
despl (apply multDespl mults)]
(listCarry (apply map + despl))))

Primero vamos a cambiar la función para tener los resultado intermedios y los almacenamos en una variable auxiliar:

> (defn multLists [xs ys]
(let [mults (reduce #(cons (multList %2 xs) %1) '() ys)
despl (apply multDespl mults)]
[mults despl (listCarry (apply map + despl))]))
#'mult-listas/multLists

> (def aux (multLists '(5 6 7 8) '(1 2 3))
#'mult-listas/aux

> (aux 0)
((1 7 0 3 4) (1 1 3 5 6) (5 6 7 8))

> (aux 1)
((1 7 0 3 4) (1 1 3 5 6 0) (5 6 7 8 0 0))


Hasta aquí la cosa esta bien, las multiplicaciones parciales son correctas y los desplazamientos a la izquierda también. Vamos a probar el siguiente paso que seria:

> (apply map + (aux 1))
(7 14 10 16 10)


Ooops, aquí esta el error, en lugar de sumar seis elementos ha sumado cinco, si nos fijamos ha sumado los n-esimos elementos de las listas y como la primera solo tiene cinco posiciones ha desechado los últimos elementos de las otras dos. Si comprobamos la documentación de la función map (el énfasis es mio):

> (doc map)
-------------------------
clojure.core/map
([f coll] [f c1 c2] [f c1 c2 c3] [f c1 c2 c3 & colls])
Returns a lazy sequence consisting of the result of applying f to the
set of first items of each coll, followed by applying f to the set
of second items in each coll,
until any one of the colls is
exhausted
. Any remaining items in other colls are ignored. Function
f should accept number-of-colls arguments.
nil


Para solucionarlo lo primero que se me ha ocurrido es igualar todas las listas añadiendo ceros por la izquierda. Para ello tendremos que calcular la longitud de la lista mas grande y añadir ceros a las demás hasta igualarla. Tal vez haya otra forma mas sencilla de hacerlo, no dudéis en comentar vuestras propuestas. Para igualar las listas necesitaremos otras dos funciones pero candidatas totales a ser reutilizadas mas adelante. Una para añadir n elementos a una lista por la izquierda:

(defn lpad [lista num elem] (concat (replicate num elem) lista))

La función es casi auto-descriptiva. Para saber la longitud de la lista mas grande nos haremos otra función (aunque ya esta hecha en la librería auxiliar oficial de Clojure:

(defn maxLength [& lst] (apply max (map count lst)))

En esta función vemos el símbolo & que hace que la función acepte cualquier numero de parámetros que están disponibles metidos en una lista identificada con el símbolo después de & (lst en este caso). Este símbolo puede estar al final de la lista de parámetros normales. La lista de listas se convierte en una lista de las longitudes de las misma con map count y luego usamos max para extraer el máximo entre ellos.

Bueno ya podemos completar la función para que la operación sea correcta:

(defn multLists [xs ys]
(let [mults (reduce #(cons (multList %2 xs) %1) '() ys)
despl (apply multDespl mults)
max (apply maxLength despl)
lpaded (map #(lpad %1 (- max (count %1)) 0) despl)]
(listCarry (apply map + lpaded))))

> (multLists '(5 6 7 8) '(1 2 3))
(6 9 8 3 9 4)
> (numList (multLists '(5 6 7 8) '(1 2 3))
698394


Ya hemos llegado al final del camino, espero que este sencillo ejemplo os haya picado la curiosidad por Clojure y sus posibilidades.

Teneis el codigo del ejemplo en github para que hagais con el lo que querais.

No hay comentarios:

Publicar un comentario