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 计算（例如，当m专门用于Logicor时[]），例如

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

...但我希望能够通过使用可变向量并vmax0就地修改单个向量（因为我只需要增加/减少单个元素并复制整个仅替换单个元素的向量是一个相当大的开销，向量变得越长）；请注意，这只是我一直在尝试实现的一类算法的玩具示例

所以我的问题是——假设有一种方法可以实现这一点——我如何在 ST monad 中表达这样一个有状态的算法，同时在计算过程中一旦产生结果，仍然能够将结果返回给调用者？我尝试通过 monad-transformers 将 ST monad 与 list monad 结合起来，但我不知道如何使它工作......

score 3 · Accepted Answer

只需使用懒惰的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]]看看它确实会延迟返回结果。

score 2 · Accepted Answer

让我们对 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。你说要使用惰性ST，而对STVectors的预定义操作只是为严格ST定义的，所以我们需要做一些包装函数。我不打算为这样的东西制作运算符，但如果你真的想让代码变成 Pythonic（例如$=forwriteLazy或其他什么；你需要以某种方式处理索引投影，但无论如何都可以让它看起来更好））。

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为Coroutines 定义，所以guard这里不可用。但这可能不是你想要的，因为它在某些/大多数单子中停止时会引发错误。我们当然也需要将lift所有在 monad 中完成的操作从STmonad 中拿出来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变量是纯粹的且延迟生成的。

我有点累，所以如果有什么不明白的地方，请不要犹豫指出。

score 2 · Accepted Answer

早上太早了，我无法及时理解你的算法。但是，如果我正确阅读了基本问题，您可以使用惰性 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 操作创建一个惰性结果流。

python - 如何使 ST 计算产生惰性结果流（或像协程一样操作）？

3 回答 3

Related

Reference