miércoles, 17 de febrero de 2010

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

En el episodio anterior conseguimos la función que nos convierte un número en la lista de sus dígitos:

> (numList 12345)
(1 2 3 4 5)

Nos faltaría el proceso inverso para tener la cosa completa. En este caso partimos de una lista de elementos y tenemos que "reducirla" a uno solo. La implementación cruda se puede hacer recursivamente, extrayendo cada uno de los dígitos y haciendo la operación inversa a la función anterior, es decir, empezando por el último, multiplicar cada elemento por diez y sumarlo al siguiente:

(defn listNum [l]+
(let [x (last l) xs (butlast l)]
(if (nil? x) 0 (+ x (* 10 (listNum xs))))))

Como en cualquier aproximación recursiva primero establecemos el caso trivial que es cuando ya no haya mas elementos en la lista (o sea cuando sea "nil" o nulo el elemento extraido de la lista). Entonces devolveremos el valor básico 0. Luego construimos la llamada de "dentro a afuera", como si fuera una muñeca rusa. La recursión puede ser un poco confusa al principio hasta que la mente abandona los for, while y compañía. En este caso no podemos usar recur ya que la llamada recursiva no es la ultima expresión evaluada en la funcion.
La ejecución de (listNum '(1 2 3)) se podria rastrear poniendo todas las llamadas recursivas a la vez así:

(+ 3 (* 10 (+ 2 (* 10 (+ 1 (* 10 0))))))
(+ 3 (* 10 (+ 2 (* 10 (1)))))
(+ 3 (* 10 (+ 2 (10))))
(+ 3 (* 10 (12)))
(+ 3 120)
123

La operacion de recorrer una lista e ir creando un valor acumulativo aplicando una funcion a cada elemento de la lista es algo tan habitual que hay una función especializada en ello: reduce, que precisamente "reduce" una lista a un unico valor aplicando una función a cada uno de los elementos de la lista y al valor acumulado anterior. Esta función entra dentro de las llamadas de "orden superior" ya que o bien toman otras funciones como parametro, bien devuelven otra función o ambas cosas. La firma de reduce sería:

(reduce funcionAcumuladora valorInicial listaAProcesar)

Usandola nuestra función quedaría así:

(defn listNum [lst] (reduce #(+ %2 (* 10 %1)) 0 lst))

Aparece aqui algo muy interesante: una función anónima representada por #(...). Dentro de la misma podemos hacer referencia a los parametros en orden con %1,%2,etc.
La traducción de la función anónima a una con nombre sería:

(defn acumulador [p1 p2] (+ p2 (* 10 p1)))
(defn listNum [lst] (reduce acumulador 0 lst))

Bueno con nuestras funciones de conversión ya podemos empezar a pensar en como multiplicaremos dos números como listas de dígitos, pero sera en la siguiente entrada.

No hay comentarios:

Publicar un comentario