如何使ST计算产生延迟的结果流（或者像协同程序一样操作）？

Question

我正在努力解决如何使Haskell中的有状态计算懒惰地生成结果的一般问题。E、 g.下面的简单算法可以在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或{}）时，例如

^{pr2}$

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

所以我的问题是——假设有一种方法可以实现这一点——我如何在第一个单子中表达这样一个有状态的算法，同时还能在计算过程中一产生结果就把结果返回给调用者呢？我尝试过通过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]]来查看它是否确实懒洋洋地返回结果。在