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 专门用于 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

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

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

Answer 1

就用lazy 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]] 看看它确实延迟返回结果。