Ya tenemos nuestras dos funciones de conversión entre numero y listas y podemos pensar en realizar operaciones. En este caso tenemos que trabajar con dos listas y hacer la multiplicación tal como la haríamos con papel y lápiz. Es decir multiplicar todos los elementos de la lista por cada uno de los elementos de la otra, sumando el acarreo y sumar todos los productos desplazando una posición a la izquierda cada vez.
De la descripción de lo que queremos podemos deducir las funciones que nos harán falta. En primer lugar necesitaremos unas funciones que nos sumen listas de dígitos. Lo que es la simple suma de los elementos es bastante directa:
> (map + '(4 5 6) '(7 8 9))
'(11 13 15)
Map es otra función básica en cualquier lenguaje funcional y aplica una función a cada uno de los elementos de una lista devolviendo la lista resultante. En Clojure si hay varias listas (como en este caso) aplica la función a todos los n-esimos elementos de cada una de las listas. El ejemplo anterior se convertiría en algo así:
((+ 4 7) (+ 5 8) (+6 9))
La cuestión es que no nos vale ya que no queremos (11 13 15) que se nos convertirá en 111315. Hace falta, al igual que cuando sumamos a la antigua usanza dejar el dígito de la unidad y sumar el dígito de la decena al siguiente termino de la suma: (1 2 4 5). Como hemos empezado a describir la resolución "de abajo a arriba", o sea de las funciones mas simples a las complejas que las usan nos ocuparemos de la suma con acarreo. Para construir la nueva lista usaremos de nuevo reduce, para recorrer todos los elementos de la lista e ir construyendo la nueva lista pasando el acarreo y la lista de un elemento a otro.
(defn listCarry [xs]
(let [[x,xs] (reduce carry [0 '()] (reverse xs))]
(if (zero? x) xs (cons x xs))))
Usamos de elemento intermedio un vector de dos posiciones [acarreo '(lista a devolver)]. La función que coge ese dato y nos devuelve el siguiente es:
(defn carry [acc x]
(let [s (+ x (acc 0)) [d r] (div s 10)]
[d (cons r (acc 1))]))
> (carry [0 ()] 15)
[1 (5)]
> (carry [1 '(5)] 13)
[1 (4 5)]
> (carry [1 '(4 5)] 11)
[1 (2 4 5]
La función listCarry si el ultimo acarreo es cero nos devuelve la lista construida y si no se lo añade antes de devolverla.
> (listCarry '(11 13 15))
(1 2 4 5)
Ya podemos atacar la siguiente función que seria multiplicar una lista de dígitos por un solo elemento base de la que queremos. Simplemente aplicaremos una función anónima que multiplica por el elemento en cuestión a todos los elementos de la lista con map, y le pasaremos a la lista resultante la función listCarry:
(defn multList [m lst]
(listCarry (map #(* %1 m) lst)))
> (multList 2 '(5 6 7 8))
(1 1 3 5 6)
Bueno la primera implementación de la multiplicación entre listas esta muy cerca, parecería que solo hay que recorrer los elementos de un lista, multiplicar la otra por cada uno de ellos y sumar las listas resultantes. Sin embargo ya podemos prever que como mínimo tendremos que desplazar cada una de las multiplicaciones parciales una "posición" hacia la izquierda mas que la anterior. Al ser sumas ese desplazamiento podemos traducirlo añadiendo ceros por la derecha. Podríamos o bien añadir los ceros a la vez que vamos haciendo las multiplicaciones o añadir los que toquen en la lista resultante. Una función general independiente que añada ceros por la derecha podría ser utilizada mas adelante así que vamos a elegir esta ultima opción:
(defn multDespl [& lst]
(map concat lst (iterate #(cons 0 %1) '())))
Esta funcion se aprovecha de otra poderosa característica de Clojure (compartida con Haskell): la evaluación "perezosa". Muchas funciones en Clojure nos devuelven una secuencia que no se evalúa en el mismo momento de ser llamada la función. La evaluación de un elemento de la secuencia se hace cuando es necesario y no antes. Eso permite que podamos escribir funciones que representen secuencias infinitas en potencia, con la seguridad de que solo se computara hasta el elemento que necesitemos. La ultima función usa la evaluación perezosa en
La función iterate aplica una función a un valor inicial (una lista vacia en nuestro caso) y vuelve a aplicarla sobre el resultado anterior una y otra vez hasta el infinito. Obviamente un ordenador no puede manejar listas infinitas, así que tendremos que decirle hasta donde queremos usarla, por ejemplo con la función take que "toma" los elementos que queramos de una secuencia.
(iterate #(cons 0 %1) '())
> (take 4 (iterate #(cons 0 %1) ())
((0) (0 0) (0 0 0) (0 0 0 0) (0 0 0 0 0))
Bien ya podemos intuir lo que hace la función de desplazar a la izquierda: une cada una de las listas que representan las multiplicaciones parciales a cada una de las listas con ceros de nuestro iterate:
> (multDespl '(1 2 3) '(1 2) '(1))
((1 2 3 0) (1 2 0 0) (1 0 0 0))
Bien, ya parece que tenemos nuestros ladrillos para construir la función principal:
(defn multLists [xs ys]
(let [mults (reduce #(cons (multList %2 xs) %1) '() ys)
despl (apply multDespl mults)]
(listCarry (apply map + depls))))
La función define en un let dos resultados intermedios, en mults las multiplicaciones parciales resultantes de multiplicar la lista xs por cada uno de los elementos de ys. En despl rehacemos la lista con los desplazamientos hacia la izquierda. Finalmente en el cuerpo de la función sumamos todas las listas intermedias y le pasamos la función listCarry. Sin embargo si probamos la función:
> (multLists '(5 6 7 8) '(1 2 3))
(8 5 1 7 0)
¡Argh! Nuestro gozo en un pozo, la solución ni se acerca a la solución real (si la calculadora de Google no falla tendría que ser (6 9 8 3 9 4). Os doy unos días para averiguar por qué ...
No hay comentarios:
Publicar un comentario