haskell - mónada - Relajarse ordenando restricciones en cómputo monádico

monads

Question

He aquí algunos elementos de reflexión.

Cuando escribo código monádico, la mónada impone el orden en las operaciones realizadas. Por ejemplo, si escribo en la mónada IO:

do a <- doSomething
b <- doSomethingElse
return (a + b)

Sé que doSomething se ejecutará antes de doSomethingElse .

Ahora, considere el código equivalente en un lenguaje como C:

return (doSomething() + doSomethingElse());

La semántica de C no especifica realmente en qué orden se evaluarán estas dos llamadas de función, por lo que el compilador es libre de mover las cosas como le plazca.

Mi pregunta es la siguiente: ¿Cómo escribiría un código monádico en Haskell que también deja este orden de evaluación sin definir? Idealmente, obtendría algunos beneficios cuando el optimizador de mi compilador mira el código y comienza a mover las cosas.

Aquí hay algunas técnicas posibles que no hacen el trabajo, pero están en el "espíritu" correcto:

• Escriba el código en estilo funcional , es decir, escriba plus doSomething doSomethingElse y permita que plus programe las llamadas monádicas. Inconvenientes: Pierdes el intercambio de los resultados de las acciones monádicas y, plus aún toma una decisión sobre cuándo las cosas terminan siendo evaluadas.
• Use la IO perezosa , es decir, unsafeInterleaveIO , que difiere la programación a las demandas perezosas de la evaluación. Pero perezoso es diferente de estricto con un orden indefinido: en particular, quiero que todas mis acciones monádicas sean ejecutadas.
• Lazy IO, combinada con la inmediata búsqueda de todos los argumentos. En particular, seq no impone restricciones de orden.

En este sentido, quiero algo más flexible que el ordenamiento monádico pero menos flexible que la pereza total.

Answer 1

La semántica de C no especifica realmente en qué orden se evaluarán estas dos llamadas de función, por lo que el compilador es libre de mover las cosas como le plazca.

¿Pero qué doSomething() si doSomething() causa un efecto secundario que cambiará el comportamiento de doSomethingElse() ? ¿Realmente quieres que el compilador se meta con el orden? (Pista: no) El hecho de que estés en una mónada sugiere que tal puede ser el caso. Tu nota de que "pierdes la participación en los resultados" también sugiere esto.

Sin embargo, tenga en cuenta que monádico no siempre significa secuenciado. No es exactamente lo que describe, pero puede estar interesado en la mónada Par , que le permite ejecutar sus acciones en paralelo.

Está interesado en dejar el orden indefinido para que el compilador pueda optimizarlo mágicamente para usted. Tal vez, en lugar de eso, deberías usar algo como la mónada Par para indicar las dependencias (algunas cosas inevitablemente tienen que suceder antes que otras) y luego dejar que el resto corra en paralelo.

Nota al margen: no confundas el return de Haskell con el return de C

Answer 2

Este es un truco muy sucio, pero parece que debería hacer el truco para mí.

{-# OPTIONS_GHC -fglasgow-exts #-}
{-# LANGUAGE MagicHash #-}
module Unorder where
import GHC.Types
unorder :: IO a -> IO b -> IO (a, b)
unorder (IO f) (IO g) = IO $ /rw# ->
let (# _, x #) = f rw#
(# _, y #) = g rw#
in (# rw# , (x,y) #)

Dado que esto pone el no determinismo en manos del compilador, debe comportarse "correctamente" (es decir, no determinísticamente) con respecto a los problemas de flujo de control (es decir, excepciones) también.

Por otro lado, no podemos hacer el mismo truco en la mayoría de las mónadas estándar, como State y Either a ya que realmente dependemos de la acción espeluznante a una distancia disponible a través del desorden con la ficha de RealWorld . Para obtener el comportamiento correcto, necesitaríamos algunas anotaciones disponibles para el optimizador que indicaban que estábamos bien con una elección no determinista entre dos alternativas no equivalentes.

Answer 3

Este problema de código de mónada con exceso de secuenciación se conoce como "problema de mónadas conmutativas" .

Las mónadas conmutativas son mónadas para las cuales el orden de las acciones no hace ninguna diferencia (conmutan), es decir, cuando se sigue el código:

do a <- f x
b <- g y
m a b

es lo mismo que:

do b <- g y
a <- f x
m a b

hay muchas mónadas que conmutan (por ejemplo, Maybe , Random ). Si la mónada es conmutativa, las operaciones capturadas en ella se pueden calcular en paralelo, por ejemplo. ¡Son muy útiles!

Sin embargo, no tenemos una buena sintaxis para las mónadas que viajan diariamente , aunque muchas personas han pedido algo así, todavía es un problema de investigación abierto .

Además, los funtores aplicativos nos dan tanta libertad para reordenar los cálculos, sin embargo, debe renunciar a la noción de liftM2 (como lo demuestran las sugerencias para, por ejemplo, liftM2 ).