Programación en Haskell: Utilizando listas infinitas para simplificar y optimizar el código

Haskell utiliza un sistema de evaluación perezosa que te permite definir tantos términos como desees, sabiendo que el compilador solo asignará los que utilices en una expresión. En este artículo utilizaremos secuencias simples como listas de longitud infinita de diferentes formas para demostrar cómo puedes utilizar este enfoque.

Generando secuencias lineales

La forma más sencilla de generar una secuencia lineal en Haskell es usando el rango de números: [1..]. Este método es similar a la función de rango en otros lenguajes. Puedes usarlo para generar secuencias crecientes o decrecientes de forma concisa:

[1..10]
[1,2,3,4,5,6,7,8,9,10]

[1,3..10]
[1,3,5,7,9]

[10..1]
[]

[10,9..1]
[10,9,8,7,6,5,4,3,2,1]

take 20 [10,9..]
[10,9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9]

Secuencias autorreferenciales

Cuando observas las listas numbers1 y numbers2, lo importante es que cada una se refiere a sí misma para construir la lista. Aunque la lista nunca está completa, podemos construir cada elemento en la lista utilizando el último valor de la secuencia en ese punto del programa. Esto funciona igual de bien con funciones que producen listas, como map, como con comprensiones de listas. Los elementos de la lista se construyen solo cuando son necesarios, generando elementos anteriores si es necesario, por lo que aunque la secuencia es potencialmente infinita, no ocupará una cantidad infinita de memoria.

Ejemplos más complicados

Un ejemplo más complicado es generar la secuencia de números factoriales y números triangulares. El siguiente código de ejemplo demuestra tanto implementaciones basadas en comprensiones de lista autorreferenciales como aquellos basadas en la función scanl incorporada (para los ejemplos de comprensiones de lista, deberás darle a ghci la opción de línea de comandos -fglasgow-exts):

triangle1 = scanl (+) 1 [2..]
triangle2 = 1 : [x+y | x <- [2..] | y <- triangle2]

factorial1 = scanl (*) 1 [2..]
factorial2 = 1 : [x*y | x <- [2..] | y <- factorial2]

Otro ejemplo común al demostrar listas infinitas es la secuencia de Fibonacci. La página de Wikipedia sobre Haskell ofrece dos formas de implementar esta secuencia como una lista infinita. Yo agregaré otra forma utilizando scanl:

fibs1 = 0 : 1 : zipWith (+) fibs1 (tail fibs1)
fibs2 = 0 : 1 : [a+b | a <- fibs2 | b <- tail fibs2]

fibs3 = 0 : scanl (+) 1 fibs3

Usos de listas infinitas

El uso de listas infinitas no se limita a secuencias de enteros. Por ejemplo, la siguiente función utiliza una lista infinita para generar todas las cadenas posibles de menos de un número dado de caracteres:

Cómo generar archivos PDF dinámicamente con PHP utilizando FPDF

strings = [x++[a] | x <- "" : strings, a <- ['a'..'z']]

stringsMenoresA n = takeWhile (\x -> length x < n) strings

No son útiles en todas las situaciones, pero te brindan otra herramienta que puedes usar para simplificar y condensar tu código. Los perfiles básicos indican que, para una tarea básica, un programa iterativo y uno basado en listas tienen un rendimiento equivalente, es decir, no hay penalización por utilizar la pereza en tu código.

Si deseas leer más sobre el uso de listas perezosas en Haskell. Puedes consultar el Haskell Wiki, en particular esta página sobre la construcción de una lista infinita de números primos es un buen ejemplo de dónde se puede utilizar esta técnica.

En Newsmatic nos especializamos en tecnología de vanguardia, contamos con los artículos mas novedosos sobre Desarrollo, allí encontraras muchos artículos similares a Programación en Haskell: Utilizando listas infinitas para simplificar y optimizar el código , tenemos lo ultimo en tecnología 2023.