<p>让我们对Python代码进行更直接的翻译。您在Python中使用协同程序,那么为什么不在Haskell中使用协同程序呢?还有可变向量的问题;请参阅下面的详细信息。在</p>
<p>首先,吨进口:</p>
<pre><code> 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
</code></pre>
<p>下面是一些实用程序定义,它们让我们将协同程序视为在Python中的行为,或多或少:</p>
^{pr2}$
<p>现在我们需要能够以某种方式使用<code>STVector</code>s。您说您希望使用<strong>lazy</strong>ST,并且对<code>STVector</code>s的预定义操作只为<strong>strict</strong>ST定义,因此我们需要制作一些包装函数。我不喜欢为这样的东西做操作符,但是如果你真的想让代码变成python(例如,<code>$=</code>代表<code>writeLazy</code>或其他任何东西;你需要以某种方式处理索引投影,但无论如何,它可能看起来更好)。在</p>
<pre><code>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
</code></pre>
<p>所有的工具都在这里,我们来翻译一下算法:</p>
<pre><code>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
</code></pre>
<p>遗憾的是,没有人费心为<code>Coroutine</code>定义<code>MonadPlus</code>,因此{<cd7>}在这里不可用。但这可能不是你想要的,因为在某些/大多数单子中停顿时会产生错误。当然,我们还需要<code>lift</code>将<code>ST</code>monad中完成的所有操作从<code>Coroutine</code>monad中取出;这是一个小麻烦。在</p>
<p>这就是所有的代码,所以你可以简单地运行它:</p>
<pre><code>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]])
</code></pre>
<p><code>list</code>变量是纯变量,是惰性生成的。在</p>
<p>我有点累了,所以如果有什么不明白的话,请不要犹豫地指出。在</p>