« Jornadas FORMA'14 « || Inicio || » Ejercicios de Elm (El… »

Refactorización Funcional

Última modificación: 19 de Septiembre de 2015, y ha tenido 196 vistas

Etiquetas utilizadas: ||

(Extraído parcialmente del tutorial Haskell Fast & Hard)

A continuación vamos a mostrar, por medio de un ejemplo, una de las diferencias fundamentales entre las soluciones que se suelen dar usando al paradigma imperativo y las que se pueden dar por medio del funcional. Lo vamos a hacer siguiendo un proceso de "refactorización", que consiste en partir de la solución imperativa y, poco a poco, ir convirtiéndola en una solución puramente funcional.

Antes de meternos en esa tarea, hemos de marcar las diferencias existentes entre dos conceptos similares y que a veces se confunden. Por una parte nos encontramos la reescritura de código, y por otra la refactorización del mismo.

Se llama reescritura a la acción de re-implementar un código o gran parte de el. En este sentido, el nuevo código no necesita tener similitud con la estructura del código inicial que se reemplazará, pero sí debe cumplir la misma función. La reescritura de código puede buscar la mejora del diseño ya existente así como introducir nuevas funcionalidades o cambios en el comportamiento de nuestro código para el ambiente en que se expone. Cuando la reescritura no hace uso de código existente previo, se suele llamar reescritura desde cero. A veces también se incluye en este término la re-ingeniería de un código que se ha vuelto difícil de manejar o extender.

Por otra parte, se habla de refactorización de código cuando se realizan cambios mínimos, o muy específicos, en el código sin alterar la estructura que lo expone. La refactorización busca principalmente mejorar el diseño del código dando más legibilidad y brindar mejoras en el rendimiento, pero no se hace refactorización a un código con el fin de resolver problemas de funcionamiento (bugs) o para crear nuevas funcionalidades, sino que debe ser hecha sobre un código completamente funcional. Muchas veces se busca, entre otras cosas, eliminar responsabilidades innecesarias al código sobre el que se hace refactorización, focalizando su uso y distribuyendo funcionalidades entre otros métodos y clases.

En esta entrada nosotros vamos a dar un salto más en el proceso de refactorización, y mostraremos cómo, tras cambiar el código original para simplificar el proceso en el lenguaje de origen, conseguimos más mejoras todavía al rerescribirlo en un lenguaje funcional puro sin cambiar la estructura subyacente al código.

Para ello, vamos a hacer uso de un problema estándar que tiene una solución muy clara en cualquier lenguaje imperativo:

Dada una lista de enteros, devolver la suma de los números pares que aparezcan en la lista.
Ejemplo: sumPar [1,2,3,4,5] = 2 + 4 = 6

Para mostrar una solución imperativa que puede ser comprendida por todo el mundo, daremos una posible solución escrita en Javascript, que tiene una estructura similar a muchos otros lenguajes imperativos:


function SumPar(lista) {
var resultado = 0;
for (var i=0; i< lista.length ; i++) {
if (lista[i] % 2 ==0) {
resultado += lista[i];
}
}
return resultado;
}

La primera diferencia que hemos de considerar es que Haskell ni tiene variables mutables ni bucles. Por lo que hemos de conseguir el mismo resultado usando alguna estructura de programación alternativa. En nuestro caso, haremos uso de la recursión. Aunque la recursión puede ser implementada en todos los lenguajes de programación, en los imperativos generalmente da resultados muy pobres (debido a ineficientes optimizaciones de los compiladores o intérpretes), pero no sucede lo mismo en los lenguajes funcionales. En particular, Haskell maneja las funciones recursivas de una forma especialmente eficiente.

Una implementación de la versión recursiva en un lenguaje imperativo podría tener la forma:


int SumPar(int *lista) {
return acumSum(0,lista);
}
int acumSum(int n, int *lista) {
int x;
int *xs;
if (empty(*lista)) {
return n;
} else {
x = lista[0]; // x es el primer elemento de la lista
xs = lista+1; // xs es el resto de la lista
if ( (x%2) == 0 ) { // Si x es par
return acumSum(n+x, xs);
} else {
return acumSum(n, xs);
}
}
}

Trabajaremos sobre esta versión para convertirla a Haskell. Con el fin de ceñirnos a la parte importante del programa, haremos uso de las siguientes funciones auxiliares (que vienen predefinidas en Haskell):


even :: Integral a => a -> Bool
head :: [a] -> a
tail :: [a] -> [a]

La función `even` se verifica si el dato de entrada es par. La función `head` devuelve el primer elemento de una lista, mientras que la función `tail` devuelve el resto de elementos de la lista (menos el primero). En general, nótese que para cualquier lista no vacía:


lista = (head lista):(tail lista)

Nuestra primera aproximación en Haskell sería:


-- Version 1
sumPar :: [Integer] -> Integer
sumPar l = acumSum 0 l
acumSum n l = if l == []
then n
else let x = head l
xs = tail l
in if even x
then acumSum (n+x) xs
else acumSum n xs

Podemos mejorar algunas cosas de esta implementación, comenzando por su declaración, que debería ser:


sumpPar :: Integral a => [a] -> a

A continuación, podemos hacer uso de las funciones `where` o `let`, con el fin de no hacer uso del espacio de nombres global:


sumPar :: Integral a => [a] -> a
sumPar l = acumSum 0 l
where acumSum n l =
if l == []
then n
else let x = head l
xs = tail l
in if even x
then acumSum (n+x) xs
else acumSum n xs

Si, además, hacemos uso de patrones, podemos conseguir una simplificación mayor:


-- Version 3
sumPar l = acumSum 0 l
where
acumSum n [] = n
acumSum n (x:xs) =
if even x
then acumSum (n+x) xs
else acumSum n xs

Vamos a dar un paso más, que se relaciona con el adjetivo "funcional" que tiene el paradigma que estamos analizando. Vamos a realizar lo que se llama una nu-reducción. Por ejemplo, en vez de escribir:


f x = (expresión) x

podemos escribir:


f = expresión

De esta forma:


-- Version 4
sumPar :: Integral a => [a] -> a
sumPar = acumSum 0
where
acumSum n [] = n
acumSum n (x:xs) =
if even x
then acumSum (n+x) xs
else acumSum n xs

Funciones de Orden Superior

Una función de orden superior es una función que puede tomar a otras funciones como parámetros. Algunos ejemplos son:


filter :: (a -> Bool) -> [a] -> [a]
map :: (a -> b) -> [a] -> [b]
foldl :: (a -> b -> a) -> a -> [b] -> a

Para nuestro objetivo, la función `filter` cubre una primera necesidad, ya que toma una función de tipo (`a -> Bool`) y una lista de tipo `[a]` y devuelve una lista conteniendo únicamente los elemento de la lista original para los que la función devuelve `true`. Por ejemplo:


filter even [1..10] <=> [2,4,6,8,10]

Por tanto:


-- Version 5
sumPar l = misuma 0 (filter even l)
where
misuma n [] = n
misuma n (x:xs) = misuma (n+x) xs

El siguiente paso es intentar abstraer el proceso recursivo. Para ello haremos uso de la función `foldl`, que captura el patrón de comportamiento que hemos usado en la recursión con acumulador. En general, si tenemos:


miFuncion lista = auxiliar valorInicial lista
auxiliar acumulador [] = acumulador
auxiliar valorTemporal (x:xs) = auxiliar (opBinaria valorTemporal x) xs

Podemos reemplazarlo haciendo uso de foldl como sigue:


miFuncion lista = foldl opBinaria valorInicial lista

La forma en que se define `foldl` es:


foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

En consecuencia, la nueva versión de nuestra función quedaría:

-- Version 6
sumPar l = foldl miSuma 0 (filter even l)
where miSuma ac value = acc + value

Podemos simplificarlo aún más haciendo uso de la notación lambda, que nos permite no tener que crear el nombre temporal `miSuma`:


-- Version 7
sumPar l = foldl (\x y -> x+y) 0 (filter even l)

y como


(\x y -> x+y) <=> (+)

Podemos reescribir:


-- Version 8
sumPar :: Integral a => [a] -> a
sumPar l = foldl (+) 0 (filter even l)

Yendo un poco más allá, podemos hacer uso de la composición, `(.)`, otra función de orden superior:


(f . g) x <=> f ( g x )
(f . g . h) x <=> f ( g ( h x ))

Y tras volver a aplicar la nu-recucción, obtenemos:


-- Version 9
sumPar :: Integral a => [a] -> a
sumPar = (foldl (+) 0) . (filter even)

Es imprescindible destacar la importancia de todo el proceso que hemos ejemplificado. ¿Qué hemos ganado?

Evidentemente, destaca su brevedad, pero hay cosas mucho más importantes que eso. Lo primero a destacar es la facilidad para realizar modificaciones. Supongamos que queremos ahora sumar los cuadrados de los elementos de la lista. Bastaría hacer:


sumCuadrados = (foldl (+) 0) . (map (^2))

Basta cambiar la función de transformación, o añadir los procesos de transformación que queramos ejecutar sucesivamente. La función `map` simplemente aplica la función que se le pasa, `(^2)`, a todos los elementos de la lista.
Además, desde un punto de vista conceptual, la definición funcional permite una aproximación más matemática, que nos permite poner nuestras funciones al mismo nivel que el resto de funciones, por lo que podemos seguir componiéndola, usarla para filtros, recursiones, etc.

« Jornadas FORMA'14 « || Inicio || » Ejercicios de Elm (El… »