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.

Main> :t (= (= :: Eq a ⇒ a → a → Bool Main> :t (+) (+) :: Num a ⇒ a → a → a