haskell - perezosa - programacion funcional pdf

¿Por qué la evaluación perezosa es útil? (22)

Puede aumentar la eficiencia. Este es el aspecto obvio, pero en realidad no es el más importante. (Tenga en cuenta también que la pereza también puede matar la eficiencia, este hecho no es inmediatamente obvio. Sin embargo, al almacenar muchos resultados temporales en lugar de calcularlos de inmediato, puede consumir una gran cantidad de RAM).
Le permite definir construcciones de control de flujo en un código de nivel de usuario normal, en lugar de estar codificado en el lenguaje. (Por ejemplo, Java tiene bucles for , Haskell tiene una función for , Java tiene manejo de excepciones, Haskell tiene varios tipos de mónada de excepción, C # tiene goto , Haskell tiene la mónada de continuación ...)
Te permite desacoplar el algoritmo para generar datos del algoritmo para decidir la cantidad de datos que se generarán. Puede escribir una función que genere una lista de resultados teóricamente infinita, y otra función que procese la mayor cantidad de esta lista que decida que necesita. Más concretamente, puede tener cinco funciones de generador y cinco de consumidor, y puede producir de manera eficiente cualquier combinación, en lugar de codificar manualmente 5 x 5 = 25 funciones que combinan ambas acciones a la vez. (!) Todos sabemos que el desacoplamiento es algo bueno.
Te obliga más o menos a diseñar un lenguaje funcional puro . Siempre es tentador tomar atajos, pero en un lenguaje perezoso, la más mínima impureza hace que tu código sea tremendamente impredecible, lo que te obliga a no tomar atajos.

Me he estado preguntando por qué la evaluación perezosa es útil. Todavía tengo que pedirle a alguien que me explique de una manera que tenga sentido; sobre todo, termina hirviendo para "confiar en mí".

Nota: no me refiero a la memorización.

Aquí hay dos puntos más que no creo han sido mencionados en la discusión todavía.

La pereza es un mecanismo de sincronización en un entorno concurrente. Es una forma ligera y fácil de crear una referencia a algunos cálculos y compartir sus resultados entre muchos hilos. Si varios subprocesos intentan acceder a un valor no evaluado, solo uno de ellos lo ejecutará, y los demás se bloquearán en consecuencia, recibiendo el valor una vez que esté disponible.
La pereza es fundamental para amortizar las estructuras de datos en un entorno puro. Esto es descrito por Okasaki en Estructuras de Datos Puramente Funcionales en detalle, pero la idea básica es que la evaluación perezosa es una forma controlada de mutación crítica para permitirnos implementar ciertos tipos de estructuras de datos de manera eficiente. Si bien a menudo hablamos de la pereza que nos obliga a usar la camisa de pelo de pureza, la otra forma también se aplica: son un par de características de lenguaje sinérgico.

Considera esto:

if (conditionOne && conditionTwo) { doSomething(); }

El método doSomething () se ejecutará solo si conditionOne es verdadero y conditionTwo es verdadero. En el caso donde conditionOne es falso, ¿por qué necesita calcular el resultado de la condición Two? La evaluación de la condición Dos será una pérdida de tiempo en este caso, especialmente si su condición es el resultado de algún proceso de método.

Ese es un ejemplo del interés de la evaluación perezosa ...

Considere un programa de tres en raya. Esto tiene cuatro funciones:

Una función de generación de movimientos que toma una tabla actual y genera una lista de tableros nuevos cada uno con un movimiento aplicado.
Luego hay una función de "mover árbol" que aplica la función de generación de movimiento para derivar todas las posibles posiciones de la tabla que podrían seguir de esta.
Hay una función minimax que recorre el árbol (o posiblemente solo una parte) para encontrar el mejor movimiento siguiente.
Hay una función de evaluación de la junta que determina si uno de los jugadores ha ganado.

Esto crea una clara separación de preocupaciones. En particular, la función de generación de movimiento y las funciones de evaluación de la junta son las únicas que necesitan comprender las reglas del juego: las funciones de árbol de movimiento y minimax son completamente reutilizables.

Ahora intentemos implementar ajedrez en lugar de tic-tac-toe. En un lenguaje "ansioso" (es decir, convencional), esto no funcionará porque el árbol de movimiento no cabe en la memoria. Por lo tanto, ahora las funciones de evaluación de la placa y generación de movimiento deben combinarse con la lógica de árbol de movimiento y minimax porque la lógica de minimax debe usarse para decidir qué movimientos generar. Nuestra bonita estructura modular limpia desaparece.

Sin embargo, en un lenguaje perezoso, los elementos del árbol de movimiento solo se generan en respuesta a las demandas de la función minimax: no es necesario generar todo el árbol de movimiento antes de dejar que el minimax se suelte en el elemento superior. Entonces nuestra estructura modular limpia aún funciona en un juego real.

Cuando enciendes tu computadora y Windows se abstiene de abrir todos los directorios de tu disco duro en el Explorador de Windows y se abstiene de iniciar cada programa instalado en tu computadora, hasta que indiques que se necesita cierto directorio o se necesita un determinado programa, eso es una evaluación "floja"

La evaluación "floja" realiza operaciones cuando y como se necesiten. Es útil cuando se trata de una característica de un lenguaje de programación o una biblioteca, porque generalmente es más difícil implementar una evaluación diferida por su cuenta que simplemente precalcular todo desde el principio.

Encuentro que la evaluación lenta es útil para varias cosas.

En primer lugar, todos los lenguajes perezosos existentes son puros, porque es muy difícil razonar sobre los efectos secundarios en un lenguaje perezoso.

Los lenguajes puros le permiten razonar acerca de las definiciones de funciones usando el razonamiento ecuacional.

foo x = x + 3

Lamentablemente, en una configuración no perezosa, fallan más declaraciones que en una configuración perezosa, por lo que esto es menos útil en idiomas como ML. Pero en un lenguaje perezoso puedes razonar con seguridad sobre la igualdad.

En segundo lugar, muchas cosas como la ''restricción de valor'' en ML no son necesarias en lenguajes perezosos como Haskell. Esto conduce a una gran decluttering de sintaxis. ML como los idiomas necesitan usar palabras clave como var o diversión. En Haskell, estas cosas colapsan en una sola noción.

En tercer lugar, la pereza le permite escribir un código muy funcional que puede entenderse en pedazos. En Haskell es común escribir un cuerpo funcional como:

foo x y = if condition1 then some (complicated set of combinators) (involving bigscaryexpression) else if condition2 then bigscaryexpression else Nothing where some x y = ... bigscaryexpression = ... condition1 = ... condition2 = ...

Esto le permite trabajar ''de arriba hacia abajo'' a través de la comprensión del cuerpo de una función. Los lenguajes tipo ML le obligan a usar un let que se evalúa estrictamente. En consecuencia, no se atreve a ''levantar'' la cláusula let al cuerpo principal de la función, porque si es cara (o tiene efectos secundarios) no quiere que siempre se evalúe. Haskell puede ''empujar'' los detalles a la cláusula where explícitamente porque sabe que el contenido de esa cláusula solo se evaluará cuando sea necesario.

En la práctica, tendemos a usar guardias y colapsamos eso para:

foo x y | condition1 = some (complicated set of combinators) (involving bigscaryexpression) | condition2 = bigscaryexpression | otherwise = Nothing where some x y = ... bigscaryexpression = ... condition1 = ... condition2 = ...

En cuarto lugar, la pereza a veces ofrece una expresión mucho más elegante de ciertos algoritmos. Una ''clasificación rápida'' en Haskell es unidireccional y tiene la ventaja de que si solo observa los primeros artículos, solo pagará los costos proporcionales al costo de seleccionar solo esos artículos. Nada le impide hacer esto estrictamente, pero es probable que tenga que volver a codificar el algoritmo cada vez para lograr el mismo rendimiento asintótico.

En quinto lugar, la pereza le permite definir nuevas estructuras de control en el lenguaje. No se puede escribir un nuevo constructo ''if .. then .. else ..'' en un lenguaje estricto. Si intenta definir una función como:

if'' True x y = x if'' False x y = y

en un lenguaje estricto, ambas ramas se evaluarían independientemente del valor de la condición. Se pone peor cuando se consideran los bucles. Todas las soluciones estrictas requieren el lenguaje para proporcionarle algún tipo de presupuesto o construcción explícita de lambda.

Finalmente, en la misma línea, algunos de los mejores mecanismos para tratar los efectos secundarios en el sistema de tipos, como las mónadas, en realidad solo pueden expresarse de manera efectiva en un entorno perezoso. Esto se puede ver al comparar la complejidad de los flujos de trabajo de F # con Haskell Monads. (Puede definir una mónada en un lenguaje estricto, pero desafortunadamente a menudo fallará una ley de mónada o dos debido a la falta de pereza y los flujos de trabajo, en comparación, recogen una tonelada de equipaje estricto).

Entre otras cosas, los lenguajes perezosos permiten estructuras de datos infinitas y multidimensionales.

Si bien el esquema, python, etc. permiten estructuras de datos infinitas unidimensionales con flujos, solo puede atravesar una dimensión.

La pereza es útil para el mismo problema marginal , pero vale la pena señalar la conexión corutinas mencionado en ese enlace.

Este fragmento muestra la diferencia entre una evaluación floja y no perezosa. Por supuesto, esta función de fibonacci podría ser optimizada y usar evaluación diferida en lugar de recursión, pero eso estropearía el ejemplo.

Supongamos que TENEMOS que usar los 20 primeros números para algo, con una evaluación no vaga, todos los 20 números tienen que generarse por adelantado, pero, con evaluación diferida, se generarán solo cuando sea necesario. Por lo tanto, pagará solo el precio de cálculo cuando sea necesario.

Muestra de salida

Not lazy generation: 0.023373 Lazy generation: 0.000009 Not lazy output: 0.000921 Lazy output: 0.024205

import time def now(): return time.time() def fibonacci(n): #Recursion for fibonacci (not-lazy) if n < 2: return n else: return fibonacci(n-1)+fibonacci(n-2) before1 = now() notlazy = [fibonacci(x) for x in range(20)] after1 = now() before2 = now() lazy = (fibonacci(x) for x in range(20)) after2 = now() before3 = now() for i in notlazy: print i after3 = now() before4 = now() for i in lazy: print i after4 = now() print "Not lazy generation: %f" % (after1-before1) print "Lazy generation: %f" % (after2-before2) print "Not lazy output: %f" % (after3-before3) print "Lazy output: %f" % (after4-before4)

Extracto de funciones de orden superior

Busquemos el número más grande por debajo de 100,000 que sea divisible por 3829. Para hacer eso, simplemente filtraremos un conjunto de posibilidades en las cuales sabemos que la solución radica.

largestDivisible :: (Integral a) => a largestDivisible = head (filter p [100000,99999..]) where p x = x `mod` 3829 == 0

Primero hacemos una lista de todos los números inferiores a 100,000, descendiendo. Luego lo filtramos por nuestro predicado y como los números se ordenan de forma descendente, el número más grande que satisface nuestro predicado es el primer elemento de la lista filtrada. Ni siquiera necesitábamos usar una lista finita para nuestro set inicial. Eso es pereza en la acción otra vez. Debido a que solo terminamos usando el encabezado de la lista filtrada, no importa si la lista filtrada es finita o infinita. La evaluación se detiene cuando se encuentra la primera solución adecuada.

Hay una diferencia entre la evaluación de orden normal y una evaluación perezosa (como en Haskell).

square x = x * x

Evaluando la siguiente expresión ...

square (square (square 2))

... con una evaluación entusiasta:

> square (square (2 * 2)) > square (square 4) > square (4 * 4) > square 16 > 16 * 16 > 256

... con una evaluación de orden normal:

> (square (square 2)) * (square (square 2)) > ((square 2) * (square 2)) * (square (square 2)) > ((2 * 2) * (square 2)) * (square (square 2)) > (4 * (square 2)) * (square (square 2)) > (4 * (2 * 2)) * (square (square 2)) > (4 * 4) * (square (square 2)) > 16 * (square (square 2)) > ... > 256

... con evaluación perezosa:

> (square (square 2)) * (square (square 2)) > ((square 2) * (square 2)) * ((square 2) * (square 2)) > ((2 * 2) * (2 * 2)) * ((2 * 2) * (2 * 2)) > (4 * 4) * (4 * 4) > 16 * 16 > 256

Eso es porque la evaluación perezosa examina el árbol de sintaxis y realiza transformaciones de árbol ...

square (square (square 2)) || // * / / / / square (square 2) || // * / / / / * / / / / square 2 || // * / / / / * / / / / * / / / / 2

... mientras que la evaluación de orden normal solo hace expansiones textuales.

Es por eso que, cuando usamos la evaluación diferida, nos volvemos más poderosos (la evaluación termina más seguido que otras estrategias) mientras que el rendimiento es equivalente a una evaluación entusiasta (al menos en notación O).

La evaluación diferida es más útil con las estructuras de datos. Puede definir una matriz o vector inductivamente especificando solo ciertos puntos en la estructura y expresando todos los demás en términos de toda la matriz. Esto le permite generar estructuras de datos de forma muy concisa y con un alto rendimiento en tiempo de ejecución.

Para ver esto en acción, puedes echar un vistazo a mi biblioteca de redes neuronales llamada instinct . Hace un uso intensivo de evaluación perezosa por elegancia y alto rendimiento. Por ejemplo, me deshago totalmente del cálculo de activación tradicionalmente imperativo. Una simple expresión perezosa hace todo por mí.

Esto se usa, por ejemplo, en la función de activación y también en el algoritmo de aprendizaje de retropropagación (solo puedo publicar dos enlaces, por lo que deberá buscar la función learnPat en el módulo AI.Instinct.Train.Delta ). Tradicionalmente, ambos requieren algoritmos iterativos mucho más complicados.

La evaluación diferida se relacionó con la CPU de la misma manera que la recolección de basura relacionada con la RAM. GC le permite pretender que tiene una cantidad ilimitada de memoria y, por lo tanto, solicitar tantos objetos en la memoria como necesite. Runtime recuperará automáticamente objetos inutilizables. LE le permite pretender que tiene recursos computacionales ilimitados; puede hacer todos los cálculos que necesite. Runtime simplemente no ejecutará cómputos innecesarios (para casos determinados).

¿Cuál es la ventaja práctica de estos modelos de "pretender"? Libera al desarrollador (en cierta medida) de la administración de recursos y elimina algunos códigos repetitivos de tus fuentes. Pero lo más importante es que puede reutilizar eficientemente su solución en un conjunto más amplio de contextos.

Imagine que tiene una lista de números S y N. Es necesario encontrar el número N más cercano al número M de la lista S. Puede tener dos contextos: un solo N y una lista L de Ns (ei para cada N en L) busca el M más cercano en S). Si usa evaluación diferida, puede ordenar S y aplicar búsqueda binaria para encontrar la M más cercana a la N. Para una buena clasificación perezosa, necesitará O (tamaño (S)) pasos para N y O individuales (ln (tamaño (S)) * (tamaño (S) + tamaño (L))) pasos para L igualmente distribuida. Si no tiene una evaluación diferida para lograr la eficiencia óptima, debe implementar un algoritmo para cada contexto.

La evaluación perezosa es el razonamiento ecuacional del pobre (lo que se podría esperar, idealmente, deducir las propiedades del código de las propiedades de los tipos y las operaciones involucradas).

Ejemplo donde funciona bastante bien: sum . take 10 $ [1..10000000000] sum . take 10 $ [1..10000000000] . Lo cual no nos importa que se reduzca a una suma de 10 números, en lugar de un solo cálculo numérico directo y simple. Sin la evaluación perezosa, por supuesto, esto crearía una lista gigantesca en la memoria solo para usar sus primeros 10 elementos. Sin duda sería muy lento y podría causar un error de falta de memoria.

Ejemplo donde no es tan bueno como nos gustaría: sum . take 1000000 . drop 500 $ cycle [1..20] sum . take 1000000 . drop 500 $ cycle [1..20] sum . take 1000000 . drop 500 $ cycle [1..20] . Lo que realmente sumará los 1 000 000 números, incluso si está en un bucle en lugar de en una lista; aún debería reducirse a solo un cálculo numérico directo, con pocos condicionales y pocas fórmulas. Lo cual sería mucho mejor que resumir los 1 000 000 números. Incluso si está en un bucle, y no en una lista (es decir, después de la optimización de la deforestación).

Otra cosa es que hace posible codificar en estilo recursión módulo de compilación de cola , y simplemente funciona .

cf. respuesta relacionada .

La explotación más útil de la evaluación perezosa que he usado era una función que llamaba a una serie de subfunciones en un orden particular. Si alguna de estas subfunciones falla (devuelve falso), la función de llamada debe regresar inmediatamente. Así que podría haberlo hecho de esta manera:

bool Function(void) { if (!SubFunction1()) return false; if (!SubFunction2()) return false; if (!SubFunction3()) return false; (etc) return true; }

o, la solución más elegante:

bool Function(void) { if (!SubFunction1() || !SubFunction2() || !SubFunction3() || (etc) ) return false; return true; }

Una vez que empiece a usarlo, verá oportunidades para usarlo cada vez más a menudo.

No sé cómo piensas en las cosas actualmente, pero me parece útil pensar en la evaluación perezosa como un problema de biblioteca en lugar de una función de idioma.

Quiero decir que en los lenguajes estrictos, puedo implementar la evaluación diferida mediante la construcción de algunas estructuras de datos, y en los lenguajes perezosos (al menos Haskell), puedo pedir rigor cuando lo deseo. Por lo tanto, la elección de idioma no hace que sus programas sean perezosos o no, sino que simplemente afecta a los que obtiene de forma predeterminada.

Una vez que lo piense así, piense en todos los lugares donde escribe una estructura de datos que luego puede usar para generar datos (sin mirarlo demasiado antes), y verá muchos usos para la pereza evaluación.

Otras personas ya dieron todas las grandes razones, pero creo que un ejercicio útil para ayudar a entender por qué la pereza es importante es intentar escribir una función de fixed-point en un lenguaje estricto.

En Haskell, una función de punto fijo es súper fácil:

fix f = f (fix f)

esto se expande a

f (f (f ....

pero como Haskell es flojo, esa cadena infinita de cálculos no es problema; la evaluación se hace "de afuera hacia adentro", y todo funciona maravillosamente:

fact = fix $ /f n -> if n == 0 then 1 else n * f (n-1)

Es importante que no importa que la fix sea floja, pero que sea flojo. Una vez que ya le han dado una f estricta, puede arrojar las manos al aire y darse por vencido, o eta expandirlo y desordenar las cosas. (Esto se parece mucho a lo que dijo Noah sobre que es la biblioteca estricta / floja, no el lenguaje).

Ahora imagina escribir la misma función en Scala estricta:

def fix[A](f: A => A): A = f(fix(f)) val fact = fix[Int=>Int] { f => n => if (n == 0) 1 else n*f(n-1) }

Por supuesto, obtienes un desbordamiento de pila. Si quiere que funcione, debe hacer el argumento f llamado por necesidad:

def fix[A](f: (=>A) => A): A = f(fix(f)) def fact1(f: =>Int=>Int) = (n: Int) => if (n == 0) 1 else n*f(n-1) val fact = fix(fact1)

Si crees en Simon Peyton Jones, la evaluación perezosa no es importante per se, sino solo como una "camisa de pelo" que obligó a los diseñadores a mantener el lenguaje puro. Me siento comprensivo con este punto de vista.

Richard Bird, John Hughes y, en menor medida, Ralf Hinze son capaces de hacer cosas increíbles con la evaluación perezosa. Leer su trabajo te ayudará a apreciarlo. Un buen punto de partida es el magnífico solucionador de sudoku de Bird y el artículo de Hughes sobre por qué la programación funcional importa .

Si por "evaluación diferida" te refieres a los booleanos combinados, como en

if (ConditionA && ConditionB) ...

entonces la respuesta es simplemente que cuantos menos ciclos de CPU consuma el programa, más rápido se ejecutará ... y si una porción de las instrucciones de procesamiento no tendrá impacto en el resultado del programa, entonces es innecesario (y por lo tanto un desperdicio) de tiempo) para realizarlos de todos modos ...

si otoh, te refieres a lo que he conocido como "inicializadores perezosos", como en:

class Employee { private int supervisorId; private Employee supervisor; public Employee(int employeeId) { // code to call database and fetch employee record, and // populate all private data fields, EXCEPT supervisor } public Employee Supervisor { get { return supervisor?? (supervisor = new Employee(supervisorId)); } } }

Bueno, esta técnica permite que el código del cliente use la clase para evitar la necesidad de llamar a la base de datos para el registro de datos del Supervisor, excepto cuando el cliente que utiliza el objeto Employee necesita acceso a los datos del supervisor ... esto hace que el proceso de crear instancias de un empleado sea más rápido. y sin embargo, cuando necesite el supervisor, la primera llamada a la propiedad del supervisor activará la llamada a la base de datos y los datos se obtendrán y estarán disponibles ...

Sin una evaluación perezosa, no podrás escribir algo como esto:

if( obj != null && obj.Value == correctValue ) { // do smth }

Sobre todo porque puede ser más eficiente: no es necesario calcular los valores si no se van a usar. Por ejemplo, puedo pasar tres valores en una función, pero dependiendo de la secuencia de expresiones condicionales, solo se puede usar realmente un subconjunto. En un lenguaje como C, los tres valores se calcularían de todos modos; pero en Haskell, solo se computan los valores necesarios.

También permite cosas geniales como listas infinitas. No puedo tener una lista infinita en un lenguaje como C, pero en Haskell, eso no es problema. Las listas infinitas se utilizan con bastante frecuencia en ciertas áreas de las matemáticas, por lo que puede ser útil tener la capacidad de manipularlas.

Un gran beneficio de la pereza es la capacidad de escribir estructuras de datos inmutables con límites amortizados razonables. Un ejemplo simple es una pila inmutable (usando F #):

type ''a stack = | EmptyStack | StackNode of ''a * ''a stack let rec append x y = match x with | EmptyStack -> y | StackNode(hd, tl) -> StackNode(hd, append tl y)

El código es razonable, pero al agregar dos pilas xey toma el tiempo O (longitud de x) en los casos mejor, peor y promedio. Agregar dos pilas es una operación monolítica, toca todos los nodos en la pila x.

Podemos volver a escribir la estructura de datos como una pila perezosa:

type ''a lazyStack = | StackNode of Lazy<''a * ''a lazyStack> | EmptyStack let rec append x y = match x with | StackNode(item) -> Node(lazy(let hd, tl = item.Force(); hd, append tl y)) | Empty -> y

lazy funciona suspendiendo la evaluación de código en su constructor. Una vez evaluado con .Force() , el valor de retorno se .Force() en caché y se reutiliza en cada .Force() posterior .Force() .

Con la versión perezosa, los anexos son una operación O (1): devuelve 1 nodo y suspende la reconstrucción real de la lista. Cuando obtenga el encabezado de esta lista, evaluará el contenido del nodo, forzándolo a devolver el encabezado y creando una suspensión con los elementos restantes, por lo que tomar el encabezado de la lista es una operación O (1).

Por lo tanto, nuestra lista de tareas pendientes se encuentra en un estado constante de reconstrucción, no paga el costo de reconstruir esta lista hasta que atraviese todos sus elementos. Usando la pereza, esta lista admite O (1) consing y anexar. Curiosamente, dado que no evaluamos los nodos hasta que se accede a ellos, es totalmente posible construir una lista con elementos potencialmente infinitos.

La estructura de datos anterior no requiere que los nodos se vuelvan a calcular en cada recorrido, por lo que son claramente diferentes de IEnumerables de vanilla en .NET.

Un ejemplo útil de evaluación perezosa es el uso de quickSort :

quickSort [] = [] quickSort (x:xs) = quickSort (filter (< x) xs) ++ [x] ++ quickSort (filter (>= x) xs)

Si ahora queremos encontrar el mínimo de la lista, podemos definir

minimum ls = head (quickSort ls)

Primero ordena la lista y luego toma el primer elemento de la lista. Sin embargo, debido a la evaluación perezosa, solo la cabeza se calcula. Por ejemplo, si tomamos el mínimo de la lista [2, 1, 3,] quickSort filtrará primero todos los elementos que son más pequeños que dos. Luego hace quickSort en eso (devolviendo la lista singleton [1]) que ya es suficiente. Debido a la evaluación perezosa, el resto nunca se ordena, ahorrando una gran cantidad de tiempo computacional.

Este es, por supuesto, un ejemplo muy simple, pero la pereza funciona de la misma manera para los programas que son muy grandes.

Sin embargo, hay una desventaja en todo esto: es más difícil predecir la velocidad del tiempo de ejecución y el uso de memoria de su programa. Esto no significa que los programas perezosos son más lentos o requieren más memoria, pero es bueno saberlo.