¿Cómo hacer que el cálculo ST produzca un flujo de resultados perezoso (u opere como una co-rutina)?

Question

Estoy luchando con el problema general sobre cómo hacer que un cálculo con estado en Haskell genere resultados de forma perezosa. P.ej. el siguiente algoritmo simple se puede expresar con la ayuda de la instalación del generador de Python como un cálculo con estado pero "flojo", realizando solo los pasos necesarios para llegar a la siguiente instrucción yield y luego devolviendo el flujo de control al llamante hasta que se solicite el siguiente elemento :

def solveLP(vmax0, elems): 
    elem_true_ixs = [ [ ei for ei, b in enumerate(row) if b ] for row in elems ] 

    return go(vmax0, elem_true_ixs) 

def go(vmax, mms): 
    if not mms: 
     yield [] 

    else: 
     for ei in mms[0]: 
      maxcnt = vmax[ei] 

      if not maxcnt > 0: 
       continue 

      vmax[ei] = maxcnt-1 # modify vmax vector in-place 
      for es in go(vmax, mms[1:]): 
       # note: inefficient vector-concat operation 
       # but not relevant for this question 
       yield [ei]+es 
      vmax[ei] = maxcnt # restore original vmax state 


for sol in solveLP([1,2,3],[[True,True,False],[True,False,True]]): 
    print sol 

# prints [0,2], [1,0], and [1,2] 

Esto puede ser fácilmente traducido a un cálculo Haskell perezoso (por ejemplo, cuando m está especializada para Logic o []), por ejemplo

import   Control.Monad 
import qualified Data.Vector.Unboxed as VU 

solveLP :: MonadPlus m => VU.Vector Int -> [[Bool]] -> m [Int] 
solveLP vmax0 elems = go vmax0 elemTrueIxs 
    where 
    -- could be fed to 'sequence' 
    elemTrueIxs = [ [ ei | (ei,True) <- zip [0::Int ..] row ] | row <- elems ] 

    go vmax []  = return [] 
    go vmax (m:ms) = do 
     ei <- mlist m 

     let vmax' = vmax VU.// [(ei, maxcnt-1)] -- this operation is expensive 
      maxcnt = vmax VU.! ei 

     guard $ maxcnt > 0 

     es <- go vmax' ms 

     return $ (ei:es) 

    mlist = msum . map return 

... pero me gustaría ser capaz de acercarse a la implementación de Python original, mediante el uso de vectores mutables, y la modificación de un único vector de vmax0 in situ (como acabo necesito para aumentar/disminuir un solo elemento, y copiar todo el vector para reemplazar un solo elemento es bastante sobrecarga cuanto más largo se vuelve el vector); tenga en cuenta que esto es solo un ejemplo de juguete para una clase de algoritmos que he estado tratando de implementar

Así que mi pregunta es - suponiendo que haya una manera de lograr eso - ¿cómo puedo expresar un algoritmo con tanto estado en la mónada de ST mientras se pueden devolver los resultados a la persona que llama tan pronto como se producen durante el cálculo? Intenté combinar la mónada ST con una mónada de lista mediante mónada-transformadores, pero no pude encontrar la manera de hacerlo funcionar ...

Answer 1

Es muy temprano en la mañana para entender el algoritmo . Pero si leo correctamente la pregunta subyacente, puede usar ST perezoso. He aquí un ejemplo trivial:

import Control.Monad.ST.Lazy 
import Data.STRef.Lazy 

generator :: ST s [Integer] 
generator = do 
    r <- newSTRef 0 
    let loop = do 
      x <- readSTRef r 
      writeSTRef r $ x + 1 
      xs <- loop 
      return $ x : xs 
    loop 

main :: IO() 
main = print . take 25 $ runST generator 

Está creando exactamente una corriente perezosa resultado de una acción ST que mantiene su estado.

Answer 2

Hagamos una traducción más directa del código de Python. Estás utilizando coroutines en Python, ¿por qué no utilizar corutinas en Haskell? Luego está la cuestión de los vectores mutables; ver más detalles a continuación.

En primer lugar, las toneladas de importaciones:

-- Import some coroutines 
import Control.Monad.Coroutine -- from package monad-coroutine 

-- We want to support "yield" functionality like in Python, so import it: 
import Control.Monad.Coroutine.SuspensionFunctors (Yield(..), yield) 

-- Use the lazy version of ST for statefulness 
import Control.Monad.ST.Lazy 

-- Monad utilities 
import Control.Monad 
import Control.Monad.Trans.Class (lift) 

-- Immutable and mutable vectors 
import Data.Vector (Vector) 
import qualified Data.Vector as Vector 
import Data.Vector.Mutable (STVector) 
import qualified Data.Vector.Mutable as Vector 

Estas son algunas definiciones de servicios públicos que nos permiten tratar a corrutinas como si se comportaban como en Python, más o menos:

-- A generator that behaves like a "generator function" in Python 
type Generator m a = Coroutine (Yield a) m() 

-- Run a generator, collecting the results into a list 
generateList :: Monad m => Generator m a -> m [a] 
generateList generator = do 
    s <- resume generator -- Continue where we left off 
    case s of 
    -- The function exited and returned a value; we don't care about the value 
    Right _ -> return [] 
    -- The function has `yield`ed a value, namely `x` 
    Left (Yield x cont) -> do 
     -- Run the rest of the function 
     xs <- generateList cont 
     return (x : xs) 

Ahora necesita poder usar STVector s de alguna manera. Usted indicó que quería usar perezoso ST, y las operaciones predefinidas en STVector s solo están definidas para estricta ST, por lo que debemos realizar algunas funciones de envoltura. No me gusta hacer operadores para cosas como esta, pero podrías si realmente quieres hacer que el código sea pitónico (por ejemplo, $= para writeLazy o lo que sea, necesitas manejar la proyección del índice de alguna manera, pero podría ser posible hacer que se vea más agradable de todos modos).

writeLazy :: STVector s a -> Int -> a -> ST s() 
writeLazy vec idx val = strictToLazyST $ Vector.write vec idx val 

readLazy :: STVector s a -> Int -> ST s a 
readLazy vec idx = strictToLazyST $ Vector.read vec idx 

thawLazy :: Vector a -> ST s (STVector s a) 
thawLazy = strictToLazyST . Vector.thaw 

Todas las herramientas están aquí, así que vamos a traducir el algoritmo:

solveLP :: STVector s Int -> [[Bool]] -> Generator (ST s) [Int] 
solveLP vmax0 elems = 
    go vmax0 elemTrueIxs 
    where 
    elemTrueIxs = [[ei | (ei, True) <- zip [0 :: Int ..] row] | row <- elems] 

go :: STVector s Int -> [[Int]] -> Generator (ST s) [Int] 
go _ [] = yield [] 
go vmax (m : ms) = do 
    forM_ m $ \ ei -> do 
    maxcnt <- lift $ readLazy vmax ei 
    when (maxcnt > 0) $ do 
     lift $ writeLazy vmax ei $ maxcnt - 1 
     sublist <- lift . generateList $ go vmax ms 
     forM_ sublist $ \ es -> yield $ ei : es 
     lift $ writeLazy vmax ei maxcnt 

Lamentablemente, nadie se ha preocupado de definir MonadPlus para Coroutine s, por lo guard no está disponible aquí. Pero eso probablemente no sea lo que querías de todos modos, ya que genera un error al detenerse en algunas/más mónadas. También, por supuesto, necesitamos lift todas las operaciones realizadas en la mónada ST fuera de la mónada Coroutine; una pequeña molestia.

Eso es todo el código, por lo que uno puede simplemente ejecutarlo:

main :: IO() 
main = 
    forM_ list print 
    where 
    list = runST $ do 
     vmax <- thawLazy . Vector.fromList $ [1, 2, 3] 
     generateList (solveLP vmax [[True, True, False], [True, False, True]]) 

La variable list es puro y generada con pereza.

Estoy algo cansado, así que si algo no tiene sentido, no dude en señalarlo.

Answer 3

Solo use lazy ST. En Haskell, las listas antiguas simples son básicamente idénticas a los generadores de Python, por lo que devolveremos una lista de resultados (donde el resultado es [Int]). Aquí hay una transcripción de su código de Python:

import Control.Monad.ST.Lazy 
import Data.Array.ST 
import Control.Monad 
import Data.List 

solveLP :: [Int] -> [[Bool]] -> [[Int]] 
solveLP vmax_ elems_ = runST $ do 
    vmax <- newListArray (0, length vmax_) vmax_ 
    let elems = map (findIndices id) elems_ 
    go vmax elems 

go :: STArray s Int Int -> [[Int]] -> ST s [[Int]] 
go vmax [] = return [[]] 
go vmax (mm:mms) = liftM concat . forM mm $ \ei -> do 
    maxcnt <- readArray vmax ei 
    if not (maxcnt > 0) then return [] else do 
     writeArray vmax ei (maxcnt - 1) 
     rest <- go vmax mms 
     writeArray vmax ei maxcnt 
     return (map (ei:) rest) 

Pruebe p. Ej. solveLP [1,undefined,3] [[True,True,False],[True,False,True]] para ver que realmente devuelve resultados de forma perezosa.