Vimos que hay diferentes formas de definir una misma función. Estas distintas definiciones pueden resultar muy distintas en eficiencia. Vamos a ver algunas estrategias para mejorar la eficiencia de las funciones.
En la clase anterior vimos la función encuentraEstafador, que sirve para encontrar números que se encuentran en dos listas. En nuestro ejemplo, tenemos dos listas de DNIs, una con los DNIs de personas que estén cobrando subsidio por desempleo y otra con personas que están trabajando en la municipalidad. Para encontrar a todas las personas que estén en las dos listas, podemos hacerlo de una forma muy poco eficiente:
encuentraEstafador :: [Int] -> [Int] -> [Int]
encuentraEstafador [] _ = []
encuentraEstafador (x:xs) ys | existe x ys = x : encuentraEstafador xs ys
| otherwise = encuentraEstafador xs ys
Esta función es poco eficiente porque, para cada elemento de la primera lista, recorre la segunda lista entera. Para este problema, no es necesario recorrer tantas veces las listas, sino que podemos recorrer ambas listas una única vez, si las dos listas estan ordenadas con el mismo orden. Si eso es así, podemos escribir la siguiente función:
encuentraEstafador' :: [Int] -> [Int] -> [Int]
encuentraEstafador' [] _ = []
encuentraEstafador' _ [] = []
encuentraEstafador' (x:xs) (y:ys) | x < y = encuentraEstafador' xs (y:ys)
| x > y = encuentraEstafador' (x:xs) ys
| x == y = x : encuentraEstafador' xs ys
En esta versión, como la función es verdaderamente recursiva, tenemos dos casos base y hacemos inducción en los dos argumentos. De esta forma, vamos recorriendo las dos listas a la vez, consumiendo solamente una de las dos cabezas de lista: la menor. En el caso en que ambas sean iguales, habremos encontrado un estafador y lo concatenamos al resultado. Así nos evitamos recorrer toda la segunda lista para cada uno de los elementos de la primera.
Para garantizar que las listas estén ordenadas, podemos hacerlo de dos formas: con una función que compruebe si las listas están ordenadas o con una función que las ordene.
Podemos comprobar que la segunda versión de la función es más eficiente que la primera usando el comando :set +s en Hugs:
Main> :set +s
Este comando nos permite ver cuántos pasos de reducción y celdas de memoria se han usado en la ejecución de cada función. Para desactivarlo, basta con introducir el comando :set -s en Hugs.
Vemos que las funciones encuentraEstafador y encuentraEstafador' no se comportan exactamente como esperábamos: en el caso de listas con muy pocos elementos, encuentraEstafador llega a ser incluso más eficiente que encuentraEstafador'. Sin embargo, encuentraEstafador' es más eficiente cuanto más largas son las listas con las que trabajamos.
Otra forma de optimizar el cómputo es cortando la recursión en el momento en que el resultado queda determinado y no puede ser cambiado en ninguna iteración posterior de la función, independientemente de los valores que la función encuentre. Eso pasa típicamente cuando se encuentra el valor absorbente del operador que estemos usando.
Recordemos que el absorbente es el contrario exacto del neutro: para una determinada operación binaria, aplicar la operación a cualquier valor y el absorbente devuelve siempre el absorbente.
Veamos un ejemplo con la función existe. Cuando la habíamos definido con recursión clásica, la definimos así:
existe :: Eq a => a -> [a] -> Bool existe a [] = False existe a (x:xs) = x == a || existe a xs
o bien, usando foldr:
existe' :: Eq a => a -> [a] -> Bool
existe' a xs = foldr (||) False (map (igual a) xs)
where
igual :: Eq a => a -> a -> Bool
igual x y = x == y
Sin embargo, hay una forma más eficiente de definirla:
existe'' :: Eq a => a -> [a] -> Bool
existe'' a [] = False
existe'' a (x:xs) | (x == a) == True = True
| (x == a) == False = existe'' a xs
De esta forma, la recursión se corta en dos casos: cuando llegamos al final, en que se devuelve el neutro (False) o cuando encontramos al absorbente (True). En el caso recursivo no se acumula ningún resultado, aunque esta función es un acumulador, ya que sabemos de antemano que sólo puede haber dos resultados: el neutro o el absorbente, y tenemos definidos los casos en que nos va a devolver el uno o el otro.
Podemos aplicar esta estrategia de optimización para los casos de acumuladores con un absorbente: la multiplicación, el paratodo (que es un && generalizado).
En el caso concreto de Haskell, este tipo de optimización no es especialmente eficiente, por la forma como funciona Haskell, sin embargo, esta estrategia dá muy buena optimización para otros lenguajes.
Para este apartado vamos a usar las filminas de Paco Gutiérrez sobre definiciones de tipo y el sistema de clases de Haskell.
* Definir la función segmentoInicial :: Int → [a] → [a], que dado un natural n y una lista [a], devuelve los n primeros elementos de la lista.
* Definir la función subsegmento :: Int → Int → [a] → [a], que dados dos naturales i y j, devuelve el segmento de la lista que se encuentra entre las posiciones i y j de la lista, ambos inclusive. Para ello, usar la función segmentoInicial y una modificación de la función nesimo.
* Definir la función combina :: Ord a ⇒ [a] → [a] → [a], que dadas dos listas nos devuelve una lista que combina las dos anteriores con sus elementos ordenados de menor a mayor. Implementen diferentes estrategias para obtener los elementos ordenados: ordenar las listas de antemano y después combinarlas (en una estrategia similar a encuentraEstafador''), ordenar la lista resultante, o comprobar si están ordenadas.
* Definir la función eliminaDuplicados :: [a] → [a], que elimina los elementos duplicados de una lista.
* Definir la función fusiona :: Ord a ⇒ [a] → [a] → [a], que dadas dos listas nos devuelve una lista que combina las dos anteriores con sus elementos ordenados de menor a mayor, sin duplicados.
* Definir la función esPalindromo :: [a] → Bool, que dada una lista nos dice si es un palíndromo, es decir, si es igual leída de izquierda a derecha que de derecha a izquierda.
* Definir la función divideEnDos :: Int → [a] → ([a],[a]), que divide una lista en dos, donde la longitud de la primera viene dada por el primer argumento de la función.