如何使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]]来查看它是否确实懒洋洋地返回结果。在

Answer 2

让我们对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中的行为，或多或少：

^{pr2}$

现在我们需要能够以某种方式使用STVectors。您说您希望使用lazyST，并且对STVectors的预定义操作只为strictST定义，因此我们需要制作一些包装函数。我不喜欢为这样的东西做操作符，但是如果你真的想让代码变成python（例如，$=代表writeLazy或其他任何东西；你需要以某种方式处理索引投影，但无论如何，它可能看起来更好）。在

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

遗憾的是，没有人费心为Coroutine定义MonadPlus，因此{}在这里不可用。但这可能不是你想要的，因为在某些/大多数单子中停顿时会产生错误。当然，我们还需要lift将STmonad中完成的所有操作从Coroutinemonad中取出；这是一个小麻烦。在

这就是所有的代码，所以你可以简单地运行它：

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变量是纯变量，是惰性生成的。在

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

Answer 3

我现在还太早，不能及时理解你的算法。但如果我没看错问题，你可以用lazy 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操作创建一个延迟结果流。在