如何使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原位修改单个向量来接近原始Python实现(因为我只需要增加/减少单个元素,并复制整个向量只是替换单个元素是一个很大的开销,矢量变得越长; 请注意,这只是我尝试实现的一类算法的玩具示例

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

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 操作创建惰性结果流。