data structures - ¿Cuáles son algunos casos de uso convincentes de estructuras de datos infinitas?

data-structures haskell

Question

Algunos lenguajes (Haskell, Clojure, Scheme, etc.) tienen una evaluación perezosa. Uno de los "puntos de venta" de la evaluación perezosa son las estructuras de datos infinitas. ¿Qué tiene de bueno eso? ¿Cuáles son algunos ejemplos de casos en los que ser capaz de manejar estructuras de datos infinitas es claramente ventajoso?

Answer 1

Algunas ventajas que puedo pensar:

• Código más limpio : es interesante observar que el código genera secuencias infinitas si a menudo es más simple y más limpio que el código que opera con datos limitados. Esto se debe a que dicho código a menudo está más cerca de la definición matemática subyacente.
• Flexibilidad : en lugar de decidir por adelantado qué tan grande debe ser su información, si la escribe utilizando una estructura infinita y holgazana, simplemente no tiene que preocuparse. "Solo funcionará"
• Rendimiento : si utiliza la pereza de manera correcta, puede usarla para mejorar el rendimiento calculando solo los valores de los datos cuando sea necesario, y posiblemente no lo haga en absoluto. Por lo tanto, puede evitar una gran cantidad de cálculos innecesarios.
• Abstracción de procesos infinitos : existe un uso interesante de secuencias perezosas infinitas como una abstracción para flujos de eventos, por ejemplo, lectura de entrada de una conexión de red a lo largo del tiempo. Esto puede crear algunas formas muy elegantes e interesantes de crear código para manejar flujos de eventos. por ejemplo, ver la biblioteca stream-utils en Clojure.
• Mejores algoritmos : hay algunos algoritmos que se expresan más fácilmente con estructuras de datos infinitas: la idea es que "extraes" perezosamente las partes de la solución que necesitas sin dejar el resto del algoritmo infinito sin evaluar. Si se usa este enfoque, se habilita Para reducir la complejidad del tiempo de su algoritmo (por ejemplo, de O(n^2) a O(n log n) ), esto puede ser una gran victoria.

Answer 2

Aquí hay dos ejemplos, uno grande y uno pequeño:

Por qué la Programación Funcional Importa por John Hughes tiene un buen ejemplo de un juego de ajedrez. El árbol de movimiento para un juego de ajedrez no es realmente infinito, pero es lo suficientemente grande como para ser infinito (llámalo "casi infinito"). En un lenguaje estricto, no se puede tratar como un árbol, porque no hay espacio suficiente para almacenar todo el árbol. Pero en un lenguaje lento, simplemente define el árbol y luego define una función "nextMove" para recorrerlo tanto como sea necesario. El mecanismo de evaluación perezosa se ocupa de los detalles.

El pequeño ejemplo es simplemente asociar un número de índice con cada elemento de una lista, de modo que ["foo", "bar", "baz"] se convierte en [(1, "foo"), (2, "barra"), ( 3, "baz")]. En un lenguaje estricto necesitas un bucle que rastrea el último índice y verifica si estás al final. En Haskell solo dices:

zip [1..] items

El primer argumento para zip es una lista infinita. No necesita calcular cuánto tiempo necesita estar adelantado.

Answer 3

Bueno, tuve un buen caso de uso para eso el mes pasado. Necesitaba un generador para nombres únicos al copiar objetos. Eso significa que el generador toma el nombre original X y genera un nuevo nombre para la copia. Lo hace añadiendo un texto como

X - copy
X - copy (2)
X - copy (3)
...

siempre que el nombre no se use dentro del conjunto de objetos dentro del mismo grupo. Usar una "estructura de datos infinita" (una matriz infinita de cadenas) para eso en lugar de un bucle simple tiene una ventaja: puede separar la parte que genera el nombre completamente de la prueba si el nombre ya está en uso. Así que podría reutilizar la función del generador para diferentes tipos de objetos donde la prueba en uso es ligeramente diferente para cada tipo de objeto.

Answer 4

Existe la estrategia de memorización pura canónica:

fib = (map fib'' [0..] !!)
where
fib'' 0 = 0
fib'' 1 = 1
fib'' n = fib (n-1) + fib (n-2)

fib'' función fib'' sobre una lista infinita para construir una tabla con todos los valores de fib . Voila! Memorización barata y fácil.

Por supuesto, esto tiene un tiempo de búsqueda lineal en el argumento. Puede reemplazarlo con un trie infinito para obtener el tiempo de búsqueda logarítmica. cf. data-inttrie .

Answer 5

Iba a comentar sobre el esquema de @ knivil. En lugar de eso, voy a arrojar esto como una respuesta más.

Las estructuras de datos perezosas no son la única forma de lograr la mayoría de las tareas. Esto podría irritar a los Pythonistas. Pero creo que es mejor cuando los programadores eligen las técnicas que usan. Las técnicas flojas son poderosas y elegantes.

Knivil mencionó usar el iota de Scheme. Mire qué fácil es escribir el método completo (con los 3 args), confiando en la pereza:

iota count begin step = let xs = begin:map (+step) xs
in take count xs
-- or, alternately
iota count begin step = take count $ map ((+begin).(*step)) [0..]

También podría escribir length para listas no vacías al abusar de la pereza:

len = fst . last . zip [1..]
-- or even handling empty lists
len = fst . last . zip [0..] . (undefined:)

Considere la poderosa y elegante función iterate definida en Preludio.

iterate f x = x : iterate f (f x)

Crea la lista infinita [x, fx, f (fx), f (f (fx)), ...] . Podría haber escrito iota en términos de iterate :

iota count begin step = take count $ iterate (+step) begin

El enfoque perezoso es una forma elegante de programar. No es la única forma, y ​​la gente acostumbrada a C o Java ciertamente gritará "pero no necesito flojera, puedo simplemente _", y están en lo cierto. Si su idioma es Turing-completo, se puede hacer. Pero la pereza puede ser tan elegante.

Answer 6

Las estructuras de datos infinitas proporcionan representaciones elegantes de números reales (computables). Por ejemplo, una lista infinita como

[(0, 4), (1, 3.5), (3.1, 3.2), ...]

puede representar pi . Con pereza incorporada, operar en esta representación se vuelve fácil.