Как сделать вычисление ST произвести ленивый поток результата (или действовать как совместная процедура)?

Question

Я борюсь с общей проблемой о том, как сделать вычисление с учетом состояния в Haskell ленивым результатом. Например. следующий простой алгоритм может быть выражен с помощью генератора Python в виде расчетного состояния, но «ленивого» вычисления, выполняя только шаги, необходимые для достижения следующего оператора , а затем возвращает поток управления вызывающему абоненту до тех пор, пока не будет запрошен следующий элемент :

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] 

Это может быть легко переведено на ленивое вычисление Haskell (например, когда m специализируется на Logic или []), например,

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 

... но я хотел бы быть в состоянии приблизиться к первоначальной реализации в Python, с помощью изменяемых векторов, и изменения одного vmax0 вектора на месте (как мне просто нужно для увеличения/уменьшения один элемент и копирование всего вектора только для замены одного элемента - это довольно накладные расходы, чем дольше вектор становится); обратите внимание, что это всего лишь игрушечный пример для класса алгоритмов, которые я пытался реализовать.

Так что мой вопрос - если у вас есть способ это сделать - как я могу выразить такой алгоритм с учетом состояния в ST monad, все еще имея возможность возвращать результаты обратно вызывающему абоненту, как только они будут созданы во время вычисления? Я пробовал комбинировать монаду ST с монадом-монадом с монада-трансформаторами, но я не мог понять, как заставить его работать ...

Answer 1

Это слишком рано для меня, чтобы я успел понять ваш алгоритм , Но если я правильно прочитаю основной вопрос, вы можете использовать ленивый ST. Вот простой пример:

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 

Это точно создает ленивый поток результата от действия ST, который поддерживает свое состояние.

Answer 2

Давайте сделаем более прямой перевод кода Python. Вы используете сопрограммы в Python, так почему бы не просто использовать сопрограммы в Haskell? Тогда возникает вопрос об изменчивых векторах; подробнее см. ниже.

Прежде всего, тонны импорта:

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

Вот некоторые определения полезности, которые позволяют нам рассматривать сопрограммы, как если бы они вели себя, как в Python, более или менее:

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

Теперь мы должен иметь возможность использовать STVector s как-то. Вы заявили, что хотите использовать lazy ST, а предопределенные операции на STVector s определены только для строго ST, поэтому нам нужно сделать несколько функций-оберток. Я не делаю операторов для таких вещей, но вы могли бы, если действительно хотите сделать код pythonic (например, $= для writeLazy или что-то еще, вам нужно как-то обработать проекцию индекса, но возможно, лучше в любом случае).

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 

Все инструменты здесь, так что давайте просто перевести алгоритм:

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 

К сожалению, никто не удосужился определить MonadPlus для Coroutine с, так guard не доступен здесь. Но это, вероятно, не то, что вы хотели, так как оно вызывает ошибку, когда останавливается в некоторых/большинстве монадов. Разумеется, нам также необходимо lift все операции, выполненные в монаде ST из монады Coroutine; незначительная неприятность.

Это весь код, так что можно просто запустить его:

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

Переменная list чиста и лениво генерируется.

Я устал, поэтому, если что-то не имеет смысла, пожалуйста, не стесняйтесь указать на это.

Answer 3

Просто используйте ленивый ST. В Haskell простые старые списки в основном идентичны генераторам Python, поэтому мы вернем список результатов (где результат [Int]). Вот транслитерация вашего кода на 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) 

Попробуйте, например. solveLP [1,undefined,3] [[True,True,False],[True,False,True]], чтобы увидеть, что он действительно возвращает результаты лениво.