haskell - Evaluación Lazy no trivial

time-complexity lazy-evaluation

Question

Actualmente estoy digiriendo la bonita presentación ¿Por qué aprender Haskell? por Keegan McAllister. Ahí él usa el fragmento

minimum = head . sort

como una ilustración de la evaluación perezosa de Haskell al afirmar que el minimum tiene O (n) de complejidad de tiempo en Haskell. Sin embargo, creo que el ejemplo es de naturaleza académica. Por lo tanto, estoy pidiendo un ejemplo más práctico donde no sea trivialmente aparente que la mayoría de los cálculos intermedios se descartan.

Answer 1

Considere generar y consumir los primeros n elementos de una secuencia infinita . Sin una evaluación perezosa, la codificación ingenua se ejecutaría para siempre en el paso de generación, y nunca consumiría nada. Con la evaluación diferida, solo se generan tantos elementos como el código intente consumir.

Answer 2

Este es un ejemplo conocido que publiqué en otro hilo ayer. Los números Hamming son números que no tienen ningún factor primo mayor que 5. Es decir, tienen la forma 2 ^ i * 3 ^ j * 5 ^ k. Los primeros 20 de ellos son:

[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]

El 500000 es uno:

1962938367679548095642112423564462631020433036610484123229980468750

El programa que imprimió 500000a (después de un breve momento de cálculo) es:

merge xxs@(x:xs) yys@(y:ys) =
  case (x`compare`y) of
    LT -> x:merge xs yys
    EQ -> x:merge xs ys
    GT -> y:merge xxs ys

hamming = 1 : m 2 `merge` m 3 `merge` m 5
  where
    m k = map (k *) hamming

main = print (hamming !! 499999)

Computar ese número con una velocidad razonable en un lenguaje no perezoso requiere un poco más de código y arañazos en la cabeza. Hay muchos ejemplos aquí

Answer 3

• ¿Alguna vez has escrito una IA? ¿No es molesto que tenga que pasar información de poda (por ejemplo, profundidad máxima, el costo mínimo de una rama adyacente u otra información similar) a través de la función de cruce de árbol? Esto significa que debe escribir un nuevo cruce de árbol cada vez que desee mejorar su IA. Eso es tonto. Con la evaluación perezosa, esto ya no es un problema: escriba la función transversal de árbol una vez, para producir un enorme árbol de juego (¡incluso infinito!) Y permita que su consumidor decida cuánto consumir.

• ¿Escribir una GUI que muestra mucha información? ¿Quieres que corra rápido de todos modos? En otros idiomas, puede que tenga que escribir código que represente solo las escenas visibles. En Haskell, puede escribir código que represente toda la escena y luego elegir qué píxeles observar. Del mismo modo, la representación de una escena complicada? ¿Por qué no calcular una secuencia infinita de escenas en varios niveles de detalle y elegir la más adecuada a medida que se ejecuta el programa?

• Usted escribe una función costosa y decide memorizarla para mayor velocidad. En otros idiomas, esto requiere construir una estructura de datos que rastree qué entradas para la función conoce la respuesta, y actualizar la estructura cuando vea nuevas entradas. Recuerde hacer que sea seguro para el hilo: si realmente necesitamos velocidad, también necesitamos paralelismo. En Haskell, usted construye una estructura de datos infinita, con una entrada para cada entrada posible, y evalúa las partes de la estructura de datos que corresponden a las entradas que le interesan. La seguridad del hilo viene gratis con pureza.

• Aquí hay uno que quizás sea un poco más prosaico que los anteriores. ¿Alguna vez has encontrado un momento cuando && y || ¿No eran las únicas cosas que querías estar en cortocircuito? ¡Claro que sí! Por ejemplo, me encanta la función <|> para combinar los valores Maybe : toma el primero de sus argumentos que realmente tiene un valor. Entonces Just 3 <|> Nothing = Just 3 ; Nothing <|> Just 7 = Just 7 ; y Nothing <|> Nothing = Nothing . Además, está en cortocircuito: si resulta que su primer argumento es un Just , no se molestará en hacer el cálculo requerido para descubrir cuál es su segundo argumento.

  Y <|> no está incorporado al lenguaje; está adherido a una biblioteca. Es decir: la pereza le permite escribir nuevas formas de cortocircuito. (De hecho, en Haskell, incluso el comportamiento de cortocircuito de (&&) y (||) no es una magia de compilación incorporada: surgen naturalmente de la semántica del lenguaje más sus definiciones en las bibliotecas estándar.)

En general, el tema común aquí es que puede separar la producción de valores de la determinación de qué valores son interesantes de observar . Esto hace que las cosas sean más compostables, porque la elección de lo que es interesante observar no necesita ser conocida por el productor.