¿Con qué frecuencia se usa seq en el código de producción de Haskell?

23

Tengo algo de experiencia escribiendo herramientas pequeñas en Haskell y me parece muy intuitivo de usar, especialmente para escribir filtros (que usan interact) que procesan su entrada estándar y la canalizan a la salida estándar.

Recientemente intenté usar uno de esos filtros en un archivo que era aproximadamente 10 veces más grande de lo habitual y recibí un Stack space overflowerror.

Después de leer un poco (por ejemplo, aquí y aquí ) he identificado dos pautas para ahorrar espacio en la pila (Haskellers experimentados, corríjanme si escribo algo que no es correcto):

  1. Evite las llamadas de función recursivas que no son recursivas de cola (esto es válido para todos los lenguajes funcionales que admiten la optimización de llamada de cola).
  2. Presente seqpara forzar la evaluación temprana de las subexpresiones para que las expresiones no crezcan demasiado antes de que se reduzcan (esto es específico para Haskell, o al menos para los idiomas que usan una evaluación diferida).

Después de introducir cinco o seis seqllamadas en mi código, mi herramienta vuelve a funcionar sin problemas (también en los datos más grandes). Sin embargo, creo que el código original era un poco más legible.

Como no soy un programador experimentado de Haskell, quería preguntar si presentarlo seqde esta manera es una práctica común y con qué frecuencia se verá normalmente seqen el código de producción de Haskell. ¿O hay alguna técnica que permita evitar usarlo con seqdemasiada frecuencia y aún así usar poco espacio en la pila?

Giorgio
fuente
1
Las optimizaciones como la que describiste casi siempre harán que el código sea un poco menos elegante.
Robert Harvey
@Robert Harvey: ¿Existen técnicas alternativas para mantener bajo el uso de la pila? Quiero decir, me imagino que tengo que reescribir mis funciones de manera diferente, pero no tengo idea de si existen técnicas bien establecidas. Mi primer intento fue utilizar funciones recursivas de cola, que me ayudaron pero no me permitieron resolver mi problema por completo.
Giorgio

Respuestas:

17

Desafortunadamente, hay casos en los que uno tiene que usar seqpara obtener un programa eficiente / que funcione bien para datos grandes. Entonces, en muchos casos, no puede prescindir de él en el código de producción. Puede encontrar más información en Real World Haskell, Capítulo 25. Creación de perfiles y optimización .

Sin embargo, hay posibilidades de cómo evitar el uso seqdirecto. Esto puede hacer que el código sea más limpio y robusto. Algunas ideas:

  1. Use conductos , tuberías o iteraciones en lugar de interact. Se sabe que Lazy IO tiene problemas con la administración de recursos (no solo la memoria) y los iteratees están diseñados exactamente para superar esto. (Sugeriría evitar la E / S diferida por completo sin importar cuán grandes sean sus datos; consulte El problema con la E / S diferida ).
  2. En lugar de utilizar seqdirectamente (o diseñar sus propios) combinadores como foldl ' o foldr' o versiones estrictas de bibliotecas (como Data.Map.Strict o Control.Monad.State.Strict ) que están diseñadas para cálculos estrictos.
  3. Use la extensión BangPatterns . Permite reemplazar seqcon estricta coincidencia de patrones. Declarar campos de constructor estrictos también podría ser útil en algunos casos.
  4. También es posible usar Estrategias para forzar la evaluación. La biblioteca de estrategias está dirigida principalmente a cálculos paralelos, pero también tiene métodos para forzar un valor a WHNF ( rseq) o NF completo ( rdeepseq). Existen muchos métodos de utilidad para trabajar con colecciones, combinar estrategias, etc.
Petr Pudlák
fuente
+1: Gracias por los consejos y enlaces útiles. El punto 3 parece bastante interesante (y la solución más fácil de usar en este momento). Con respecto a la sugerencia 1, no veo cómo evitar la IO diferida puede mejorar las cosas: por lo que entiendo, la IO diferida debería ser mejor para un filtro que se supone que procesa un flujo de datos (posiblemente muy largo).
Giorgio
2
@Giorgio Agregué un enlace a Haskell Wiki sobre problemas con Lazy IO. Con IO perezoso puede ser muy difícil administrar recursos. Por ejemplo, si no lee completamente la entrada (debido a una evaluación diferida), el identificador de archivo permanece abierto . Y si va y cierra el controlador de archivo manualmente, a menudo sucede que debido a la lectura de evaluación diferida, se pospone y cierra el controlador antes de leer toda la entrada. Y, a menudo es bastante difícil evitar problemas de memoria con IO diferido.
Petr Pudlák
Recientemente tuve este problema y mi programa se estaba quedando sin descriptores de archivo. Así que reemplacé IO vago por IO estricto usando estricto ByteString.
Giorgio