Come far sì che il calcolo ST produca flusso di risultati lazy (o funzioni come un co-routine)?

Question

Sono alle prese con il problema generale su come effettuare un calcolo statico in Haskell generare risultati pigramente. Per esempio. il seguente semplice algoritmo può essere espresso con l'aiuto della funzione di generatore di Python come un calcolo statico ma "pigro", eseguendo solo i passi necessari per raggiungere la successiva dichiarazione yield e quindi restituire il flusso di controllo al chiamante fino a quando viene richiesto l'elemento successivo :

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] 

Questo può essere facilmente tradotto in un pigro computazione Haskell (ad esempio quando m è specializzato per Logic o []), ad esempio

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 

... ma mi piacerebbe essere in grado di avvicinarsi alla realizzazione di Python originale, utilizzando vettori mutevoli, e la modifica di un singolo vettore vmax0 sul posto (come ho solo bisogno di aumentare/diminuire un singolo elemento, e copiare l'intero vettore solo per sostituire un singolo elemento è piuttosto un overhead più lungo diventa il vettore); per favore nota che questo è solo un esempio di giocattolo per una classe di algoritmi che ho cercato di implementare

Quindi la mia domanda è - supponendo che ci sia un modo per farlo - come posso esprimere un algoritmo così statico in la monade ST mentre è ancora in grado di restituire i risultati al chiamante non appena vengono prodotti durante il calcolo? Ho provato a combinare la monade ST con una lista monad tramite trasformatori monad ma non riuscivo a capire come farlo funzionare ...

Answer 1

È troppo presto per me per mettere in tempo a capire il tuo algoritmo . Ma se ho letto bene la domanda di fondo, puoi usare il pigro ST. Ecco un esempio banale:

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 

E 'esattamente la creazione di un flusso di risultato pigro da un'azione ST che mantiene il suo stato.

Answer 2

Facciamo una traduzione più diretta del codice Python. Stai usando le coroutine in Python, quindi perché non usare solo le coroutine in Haskell? Poi c'è il problema dei vettori mutabili; vedere più dettagli di seguito.

Prima di tutto, le tonnellate di importazioni:

-- 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 

Qui ci sono alcune definizioni di utilità che ci permettono di trattare coroutine come se si comportavano come in Python, più o meno:

-- 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) 

Ora noi Devo essere in grado di usare in qualche modo lo STVector s. Hai dichiarato che volevi usare pigro ST, e le operazioni predefinite su STVector s sono definite solo per rigoroso ST, quindi abbiamo bisogno di fare alcune funzioni wrapper. Non sto facendo operatori per cose come questa, ma potresti farlo se vuoi veramente rendere il codice pythonic (ad esempio $= per writeLazy o altro, devi gestire la proiezione dell'indice in qualche modo, ma potrebbe essere possibile farlo sembrare comunque più bello).

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 

Tutti gli strumenti sono qui, quindi diciamo solo tradurre l'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 

Purtroppo, nessuno si è preoccupato di definire MonadPlus per Coroutine s, quindi guard non è disponibile qui. Ma probabilmente non è quello che volevi comunque, dal momento che genera un errore quando si blocca in alcune/più monadi. Ovviamente abbiamo anche bisogno di lift tutte le operazioni eseguite nella monade ST fuori dalla monade Coroutine; un piccolo inconveniente.

Questo è tutto il codice, quindi si può semplicemente eseguirlo:

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 variabile list è pura e pigramente generato.

Sono un po 'stanco, quindi se qualcosa non ha senso, per favore non esitare a farlo notare.

Answer 3

Basta usare Pigro ST. In Haskell, le semplici liste vecchie sono fondamentalmente identiche ai generatori Python, quindi restituiremo un elenco di risultati (dove un risultato è un [Int]). Ecco una traslitterazione del tuo codice 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) 

Prova ad es. solveLP [1,undefined,3] [[True,True,False],[True,False,True]] per vedere che restituisce risultati pigramente.