python - ST計算で遅延結果ストリームを生成する(またはコルーチンのように動作させる)方法は?

Question

Haskell でステートフルな計算を行い、結果を遅延生成する方法に関する一般的な問題に取り組んでいます。たとえば、次の単純なアルゴリズムは、Python のジェネレーター機能を利用して、次のyieldステートメントに到達するために必要なステップのみを実行し、次の要素が要求されるまで制御フローを呼び出し元に返すステートフルだが「遅延」計算として表現できます。 :

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 計算に簡単に変換できます (たとえば、がormに特化されている場合)。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(単一の要素をインクリメント/デクリメントし、全体をコピーするだけでよいため)単一の要素を置き換えるだけの vector は、vector が長くなるほどかなりのオーバーヘッドになります); これは、私が実装しようとしているアルゴリズムのクラスのおもちゃの例にすぎないことに注意してください

だから私の質問は、それを達成する方法があると仮定して、計算中に結果が生成されるとすぐに結果を呼び出し元に返すことができる一方で、ST モナドでそのようなステートフルなアルゴリズムを表現するにはどうすればよいですか? モナドトランスフォーマーを介してSTモナドとリストモナドを組み合わせてみましたが、それを機能させる方法がわかりませんでした...

Answer 1

レイジー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]]、実際に結果が遅延して返されることを確認してください。

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を使用したいとおっしゃいましたが、s に対する定義済みの操作は厳密なSTVectorSTに対してのみ定義されているため、いくつかのラッパー関数を作成する必要があります。私はこのようなもののための演算子を作ることには興味がありませんが、本当にコードを 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

残念ながら、誰もわざわざMonadPlusfor Coroutinesを定義してguardいないので、ここでは利用できません。しかし、一部/ほとんどのモナドで停止するとエラーが発生するため、とにかくそれはおそらくあなたが望んでいたことではありません。もちろん、モナド外のモナドliftで行われるすべての操作も必要です。ちょっとした迷惑。STCoroutine

これがすべてのコードなので、簡単に実行できます。

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

あなたのアルゴリズムを理解するのに時間を割くには、朝が早すぎます。しかし、根本的な質問を正しく読めば、lazy 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 アクションから遅延結果ストリームを正確に作成しています。