haskell - ST Monad== código olor?

state monads

Question

Estoy trabajando en la implementación del algoritmo UCT en Haskell, que requiere una gran cantidad de malabares de datos. Sin entrar en demasiados detalles, es un algoritmo de simulación donde, en cada "paso", se selecciona un nodo hoja en el árbol de búsqueda basado en algunas propiedades estadísticas, se construye un nuevo nodo hijo en esa hoja, y las estadísticas correspondientes a la hoja nueva y todos sus antepasados ​​se actualizan.

Teniendo en cuenta todos los malabarismos, no soy lo suficientemente agudo como para descubrir cómo hacer que todo el árbol de búsqueda sea una buena estructura de datos inmutables a la Okasaki . En cambio, he estado jugando un poco con la mónada ST , creando estructuras compuestas de STRef s mutables. Un ejemplo artificial (no relacionado con UCT):

import Control.Monad
import Control.Monad.ST
import Data.STRef
data STRefPair s a b = STRefPair { left :: STRef s a, right :: STRef s b }
mkStRefPair :: a -> b -> ST s (STRefPair s a b)
mkStRefPair a b = do
a'' <- newSTRef a
b'' <- newSTRef b
return $ STRefPair a'' b''
derp :: (Num a, Num b) => STRefPair s a b -> ST s ()
derp p = do
modifySTRef (left p) (/x -> x + 1)
modifySTRef (right p) (/x -> x - 1)
herp :: (Num a, Num b) => (a, b)
herp = runST $ do
p <- mkStRefPair 0 0
replicateM_ 10 $ derp p
a <- readSTRef $ left p
b <- readSTRef $ right p
return (a, b)
main = print herp -- should print (10, -10)

Obviamente, este ejemplo en particular sería mucho más fácil de escribir sin usar ST , pero espero que quede claro a dónde voy con esto ... si tuviera que aplicar este tipo de estilo a mi caso de uso de UCT, ¿es incorrecto?

Alguien hizo una pregunta similar aquí hace un par de años, pero creo que mi pregunta es un poco diferente ... No tengo problemas para usar mónadas para encapsular el estado mutable cuando sea apropiado, pero es esa cláusula "cuando corresponde" lo que me atrapa. Me preocupa que esté volviendo a una mentalidad orientada a objetos prematuramente, donde tengo un montón de objetos con getters y setters. No exactamente idiomático Haskell ...

Por otro lado, si se trata de un estilo de codificación razonable para un conjunto de problemas, supongo que mi pregunta es: ¿hay formas bien conocidas de mantener este tipo de código legible y mantenible? Estoy algo asqueado por todas las lecturas y escrituras explícitas, y especialmente STRef por tener que traducir desde mis estructuras basadas en STRef dentro de la mónada ST a estructuras isomorfas pero inmutables en el exterior.

Answer 1

Algoritmos que hacen uso de mutaciones y algoritmos que no son algoritmos diferentes. En ocasiones, hay una frontera estricta que preserva la traducción de la primera a la segunda, a veces una difícil, y otras solo una que no conserva los límites de la complejidad.

Una pizca de papel me revela que no creo que haga un uso esencial de la mutación, por lo que creo que podría desarrollarse un algoritmo funcional perezoso potencialmente muy ingenioso. Pero sería un algoritmo diferente pero relacionado al descrito.

A continuación, describo uno de estos enfoques, no necesariamente el mejor o más inteligente, pero bastante sencillo:

Aquí está la configuración, lo entiendo - A) se construye un árbol de bifurcación B) los pagos se envían desde las hojas a la raíz, lo que indica la mejor opción en cualquier paso dado. Pero esto es costoso, por lo que solo se exploran las partes de los árboles de forma no determinista. Además, cada exploración adicional del árbol está determinada por lo que se aprendió en exploraciones previas.

Así que construimos código para describir el árbol "en etapas". Luego, tenemos otra estructura de datos para definir un árbol parcialmente explorado junto con estimaciones de recompensas parciales. Entonces tenemos una función de randseed -> ptree -> ptree que al dar una semilla aleatoria y un árbol parcialmente explorado, se embarca en una exploración adicional del árbol, actualizando la estructura preeree a medida que avanzamos. Entonces, podemos simplemente iterar esta función sobre un campo de semilla vacío para obtener una lista de espacios cada vez más muestreados en el pree. Luego podemos recorrer esta lista hasta que se cumpla alguna condición de corte especificada.

Así que ahora hemos pasado de un algoritmo en el que todo se combina en tres pasos distintos: 1) construir todo el árbol de estado, de forma perezosa, 2) actualizar algunas exploraciones parciales con algunos ejemplos de una estructura y 3) decidir cuándo hemos reunió suficientes muestras

Answer 2

Debo admitir que no puedo leer el código de Haskell. Pero si usas ST para mutar el árbol, entonces probablemente puedas reemplazar esto con un árbol inmutable sin perder mucho porque:

La misma complejidad para el árbol mutable e inmutable

Tienes que mutar cada nodo sobre la nueva hoja. Un árbol inmutable tiene que reemplazar todos los nodos sobre el nodo modificado. Entonces, en ambos casos, los nodos tocados son los mismos, por lo que no se gana nada en complejidad.

Por ejemplo, la creación de objetos Java es más costosa que la mutación, así que tal vez puedas ganar un poco aquí en Haskell usando la mutación. Pero esto no estoy seguro. Pero una pequeña ganancia no te compra mucho por el próximo punto.

La actualización del árbol no es presumiblemente el cuello de botella

La evaluación de la nueva hoja probablemente será mucho más cara que la actualización del árbol. Al menos este es el caso de UCT en la computadora Go.

Answer 3

El uso de la mónada de ST suele ser (pero no siempre) como una optimización. Para cualquier optimización, aplico el mismo procedimiento:

1. Escribe el código sin él,
2. Perfilar e identificar cuellos de botella,
3. Reescriba incrementalmente los cuellos de botella y pruebe las mejoras / regresiones,

El otro caso de uso que conozco es como una alternativa a la mónada estatal. La diferencia clave es que con la mónada de estado, el tipo de todos los datos almacenados se especifica de arriba hacia abajo, mientras que con la mónada ST se especifica de abajo hacia arriba. Hay casos en que esto es útil.

Answer 4

No uso mucho ST, pero a veces es la mejor solución. Esto puede ser en muchos escenarios:

• Ya existen formas bien conocidas y eficientes de resolver un problema. Quicksort es un ejemplo perfecto de esto. Es conocido por su velocidad y comportamiento in situ, que no puede ser imitado por código puro muy bien.
• Necesitas límites de tiempo y espacio rígidos. Especialmente con la evaluación perezosa (y Haskell ni siquiera especifica si hay una evaluación perezosa, solo que no es estricta), el comportamiento de sus programas puede ser muy impredecible. Si hay una pérdida de memoria podría depender de si se habilita una determinada optimización. Esto es muy diferente del código imperativo, que tiene un conjunto fijo de variables (generalmente) y un orden de evaluación definido.
• Tienes una fecha límite. Aunque el estilo puro es casi siempre una mejor práctica y un código más limpio, si está acostumbrado a escribir de manera imperativa y necesita el código pronto, comenzar de manera imperativa y pasar a la funcionalidad más tarde es una elección perfectamente razonable.

Cuando uso ST (y otras mónadas), trato de seguir estas pautas generales:

• Use el estilo Applicative menudo. Esto hace que el código sea más fácil de leer y, si cambia a una versión inmutable, es mucho más fácil de convertir. No solo eso, sino que el estilo Aplicativo es mucho más compacto.
• No solo use ST. Si programa solo en ST, el resultado no será mejor que un gran programa de C, posiblemente peor debido a las lecturas y escrituras explícitas. En cambio, intercala el código Haskell puro donde se aplica. A menudo me encuentro usando cosas como STRef s (Map k [v]) . El mapa en sí está siendo mutado, pero gran parte del trabajo pesado se realiza de forma pura.
• No rehagas las bibliotecas si no tienes que hacerlo. Una gran cantidad de código escrito para IO puede ser limpia y mecánicamente, convertido a ST. Reemplazar todas las IORef con STRef y IO con ST en Data.HashTable fue mucho más fácil que escribir una tabla hash codificada a mano, la implementación hubiera sido, y probablemente también más rápida.

Una última nota: si tiene problemas con las lecturas y escrituras explícitas, existen formas de evitarlo .

Answer 5

Puede ser realmente difícil saber cuándo usar ST es apropiado. Sugeriría que lo hagas con ST y sin ST (no necesariamente en ese orden). Mantenga la versión que no es ST simple; usar ST debería verse como una optimización, y no querrás hacerlo hasta que sepas que lo necesitas.