Estructuras de datos infinitas

En el post anterior, hablamos listas infinitas. Podemos definir una lista infinita de enteros consecutivos de la siguiente manera:

[1 ..]

Podemos evaluar esta lista, pero no se imprimirá en su totalidad. 

Debemos utilizar las funciones de take y drop para trabajar con listas infinitas. Esto permite realizar una cantidad finita de procesamiento en una lista infinita, pero no recorrerla infinitamente.

La razón por la que Haskell puede procesar listas infinitas es porque evalúa las listas de manera perezosa, es decir, solo evalúa los elementos de la lista cuando son necesarios.

Ahora echemos un vistazo a dos listas de enteros conocidas. Estudiaremos sus definiciones recursivas.

Números de Fibonacci : El n-ésimo número de Fibonacci es la suma de los dos números de Fibonacci anteriores. Los dos primeros números son ambos 1. Luego el tercero es 2, seguido de 3, 5, etc.

1, 1, 2, 3, 5, 8, 13, 21, ...

Esto se puede expresar en Haskell usando la función zipWith, combinando pares de elementos con el operador de suma.

let fibs = 1: 1: (zipWith (+) fibs (tail fibs))

Podemos evaluar elementos individuales de esta lista usando el !! y el indice. O podríamos tomar los primeros n elementos de la lista de fibs.

Números primos: A continuación se muestra una serie de expresiones de filtro para calcular una lista infinita de números primos.

properfactors :: Int -> [Int]

properfactors x = filter (\y->(x `mod` y == 0)) [2..(x-1)]

numproperfactors :: Int -> Int

numproperfactors x = length (properfactors x)

primes :: [Int]

primes = filter (\x-> (numproperfactors x == 0)) [2..]

La función de factores propios toma un valor entero x y devuelve una lista de factores propios para x. Los factores son números que dividen x y no dejan resto. Los factores adecuados para un número entero x no incluyen 1 ni x.

La función numproperfactors simplemente cuenta cuántos factores propios hay para x, devolviendo la longitud de la lista x de factores propios.

Finalmente, la lista de primos usa la función de filtro para seleccionar enteros x que no tienen factores en el rango de 2 a (x-1) inclusive.