opciones - reales en haskell

Cuándo usar las mónadas de Haskell

Question

Estoy implementando un algoritmo de optimización combinatoria en Haskell:

Given an initial candidate solution, repeat until stopping criteria are met:

  1. Determine possible moves
  2. Evaluate possible moves
  3. Choose a move
  4. Make move, record new candidate solution, update search state

Podría escribir funciones para los pasos 1-4 y encadenarlas dentro de una función recursiva para manejar el estado de bucle y paso de una iteración a la siguiente, pero tengo una vaga idea de que las mónadas se aplican.

¿Cuál es la mejor manera de expresar este tipo de procedimiento en Haskell?

Answer 1

Aquí hay un esbozo de pseudocoda de cómo podría usar la mónada de State para pasar el estado de búsqueda a través del cálculo:

import Control.Monad.State

type SearchState = ...
type Move = ...
type Fitness = ...

determineMoves :: State SearchState [Move]
determineMoves = do
  -- since determineMoves is in the State monad, we can grab the state here
  st <- get
  ...

evaluateMoves :: [Move] -> [(Move, Fitness)]
evaluateMoves = ...

chooseMove :: [(Move, Fitness)] -> Move
chooseMove = ...

-- makeMove is not itself monadic, but operates on the SearchState
-- type we''re threading through with the State monad
makeMove :: Move -> SearchState -> SearchState
makeMove m st = ...

loop :: State SearchState ()
loop = do
  moves <- determineMoves
  let candidates = evaluateMoves moves
      move = chooseMove candidates
  -- we pass a function (SearchState -> SearchState) to modify in 
  -- order to update the threaded SearchState
  modify (makeMove move)
  loop

Tenga en cuenta que aunque su cálculo principal está en la mónada estatal, no todos los componentes tienen que estar en la mónada. Aquí, chooseMove y chooseMove no son monádicos, y he usado let para mostrarle cómo integrarlos explícitamente en un bloque do . Sin embargo, una vez que se sienta cómodo con este estilo, probablemente querrá sentirse cómodo utilizando <$> (también fmap como fmap ) y la composición de funciones para ser más sucintos:

loop :: State SearchState ()
loop = do
  move <- (chooseMove . evaluateMoves) <$> determineMoves
  modify (makeMove move)
  loop

Answer 2

La mejor manera de expresar este tipo de procedimiento iterativo en Haskell es como una lista infinita de cada resultado sucesivo. Uniendo sus cuatro pasos produce una noción de una función de una solución a una solución diferente (mejor); todo lo que necesitas hacer es aplicar esto infinitas veces. El usuario de tu función puede usar cualquier función de lista para obtener la respuesta: ¡ solve s0 !! numIterations solve s0 !! numIterations , o find stoppingCondition $ solve s0 solve s0 !! numIterations find stoppingCondition $ solve s0 , o lo que quieras.

Para llegar aquí, escribamos los tipos para cada una de estas funciones.

1. moves :: Solution -> [Move]
   Ante una posible solución, averigüe los posibles cambios que puede hacer.
2. value :: Solution -> Move -> Double
   Dada una solución y un movimiento, evalúala y registra ese valor como un número real.
3. choose :: Solution -> [Move] -> Move
   Dada una solución y una lista de movimientos, elige la mejor.
4. apply :: Solution -> Move -> Solution
   Dado un movimiento, aplíquelo a una solución existente para obtener una nueva.

Desea escribir una función con un tipo parecido a solve :: Solution -> (Solution -> Bool) -> Solution que requiere una solución inicial y una condición de parada para ejecutar su algoritmo.

En cambio, hagamos de esto una lista infinita; esto significa que simplemente eliminará el predicado y tendrá la Solution -> [Solution] .

import Data.Ord
import Data.List

-- moves, value, and apply are domain-specific
choose :: Solution -> [Move] -> Move
choose s ms = maximumBy (comparing $ value s) ms

solve :: Solution -> [Solution]
solve = iterate $ /s -> apply s . choose s $ moves s

Aquí, la clave es iterate :: (a -> a) -> a -> [a] , que aplica repetidamente una función a un valor y le da los resultados, exactamente la descripción de su algoritmo.

Sin embargo, la forma en que realmente escribiría esto sería la siguiente:

import Data.Ord
import Data.List

solve :: Ord o => (s -> [m]) -> (s -> m -> o) -> (s -> m -> s) -> s -> [s]
solve moves value apply = iterate step
  where step   s = apply s . choose s $ moves s
        choose s = maximumBy (comparing $ value s)

La ventaja de esto es que puede reutilizar esta misma estructura genérica para cualquier dominio problemático. ¡Todo lo que necesita hacer es proporcionar las funciones de moves , value y apply ! Y dependiendo de mi estado de ánimo, podría reescribirlo así:

import Control.Applicative
import Data.Ord
import Data.List

solve :: Ord o => (s -> [m]) -> (s -> m -> o) -> (s -> m -> s) -> s -> [s]
solve moves value apply = iterate step
  where step   = (.) <$> apply <*> choose <*> moves
        choose = maximumBy . comparing . value

Aquí, usamos la notación aplicativa para decir que efectivamente estamos haciendo (.) apply choose moves (que es solo apply . choose $ moves ) en un contexto en el que cada una de esas funciones pasa implícitamente un parámetro s (el lector aplicativo) . Si realmente quisiéramos tersificar las cosas, podríamos escribir

import Control.Applicative
import Data.Ord
import Data.List

solve :: Ord o => (s -> [m]) -> (s -> m -> o) -> (s -> m -> s) -> s -> [s]
solve moves value apply =
  iterate $ (.) <$> apply <*> maximumBy . comparing . value <*> moves

Cualquiera de estos fragmentos hará exactamente lo que necesita. (Proviso: no hay efectos / mónadas en ninguna de tus funciones, por lo que se elimina la aleatoriedad. Sin embargo, puedes hacer esto monádicamente fácilmente.)

Sin embargo, solo por diversión, pensemos en la mónada State . Esto representa una computación con algún tipo de entorno, por lo que el State sa es isomorfo a s -> (a,s) algo que puede ver el estado y posiblemente actualizarlo. Aquí, todas las Solution -> a la izquierda de las firmas de su función desaparecerían, al igual que las -> Solution a la derecha. Eso te dejaría con

1. moves :: State Solution [Move]
2. value :: Move -> State Solution Double
3. choose :: [Move] -> State Solution Move
4. apply :: Move -> State Solution ()

Esto significa que tendrías algún step acción monádica:

import Control.Applicative
import Control.Monad.State
import Data.Ord
import Data.List

choose :: [Move] -> State Solution Move
choose = let val m = do v <- value m
                        return (m,v)
         in fst . maximumBy (comparing snd) <$> mapM val ms

step :: State Solution ()
step = apply =<< choose =<< moves

Podrías hacer esto más libre de puntos, o hacerlo polimórfico como arriba, pero no lo haré aquí. El punto es que una vez que tienes un step , puedes generar respuestas con runState . last $ replicateM_ numIterations step runState . last $ replicateM_ numIterations step , o dada una función runState $ whileM (stoppingCondition :: State Solution Bool) step , runState $ whileM (stoppingCondition :: State Solution Bool) step Una vez más, el usuario puede decidir cómo detenerlo. Sus moves y funciones de value probablemente consultarán el estado con get :: State ss ; apply probablemente usaría modify :: (s -> s) -> State s () para modificar el estado sin necesidad de retirarlo. Puedes ver la similitud con la estructura desde arriba en estos tipos; y, de hecho, también puede ver esa estructura en la definición de step . Cada uno dice "cadena, apply , choose / value y se moves ", que es la definición de su algoritmo.

El mensaje para llevar a casa de ambos es que desea evitar los bucles / recursiones explícitas, como se dio cuenta correctamente. Si piensa imperativamente acerca de este algoritmo, entonces la mónada State parece una estructura natural, ya que oculta exactamente las características imperativas en las que estaba pensando. Sin embargo, tiene sus inconvenientes: por ejemplo, todo se ha vuelto monádico y, lo que es peor, todas las funciones que no sean apply pueden cambiar la solución guardada. Si en cambio imagina que este algoritmo produce un nuevo resultado cada vez, obtiene la noción de step :: Solution -> Solution , y desde allí puede usar iterate para obtener una lista infinita de buen comportamiento.