在 Haskell 中合并 ST 和 List monad

Question

使用 StateT monad 转换器，我可以创建与 s -> [(a, s)] 同构的类型 StateT s [] a。现在我更愿意使用 STT monad transformer 来代替，因为我希望有多个不同类型的可变变量，并且希望能够根据早期计算的结果随意实例化它们。

但是，STT 的链接文档明确提到：

This monad transformer should not be used with monads that can contain multiple answers, like the list monad. The reason is that the state token will be duplicated across the different answers and this causes Bad Things to happen (such as loss of referential transparency). Safe monads include the monads State, Reader, Writer, Maybe and combinations of their corresponding monad transformers.

那么我有什么选择？

完全清楚：

我追求的是非确定性。我希望能够分叉我的计算，为每个分支提供整个状态的副本。
我不太介意并行性，因为性能不是我最关心的问题。
我不追求的是并发性：不同的计算分支不应该共享可变变量；相反，他们应该都在自己的原始可变变量副本上工作。

编辑：（编辑编辑：以下反例无效，因为 ListT 不应应用于非交换单子 ST 和 State。）我开始意识到，STT monad 转换器的行为与 StateT 一致，本质上是不安全的。有了它，我们可以构建一个类型 STT sloc (ListT (ST sglob)) a。这里，sglob 是全局状态的名称，而 sloc 是局部状态的名称。* 现在我们可以使用全局状态在线程之间交换局部状态引用，从而潜在地获得对未初始化变量的引用。

*为了对比，对应的StateT构造为StateT sloc (ListT (State sglob)) a，与sloc -> sglob -> ([(a, sloc)], sglob).

同构

Answer 1

你不会绕过 StateT，因为对于这种不确定性的东西，编译器需要始终知道哪些“变量”需要分支。当变量可能潜伏在 STRefs.

的任何地方时，这是不可能的

要仍然获得“不同类型的多个变量”，您需要将它们打包到合适的记录中并将其用作单个实际状态变量。处理这样的状态对象似乎很尴尬？好吧，使用镜头访问“个体变量”时还不错。

{-# LANGUAGE TemplateHaskell #-}

import Control.Lens
import Data.Monoid

import Control.Monad.Trans.State
import Control.Monad.ListT
import Control.Monad.Trans.Class
import Control.Monad.IO.Class

data Stobjs = Stobjs {
    _x :: Int
  , _y :: String
  }

makeLenses ''Stobjs

main = runListT . (`runStateT`Stobjs 10 "") $ do
   δx <- lift $ return 1 <> return 2 <> return 3
   xnow <- x <+= δx
   y .= show xnow
   if xnow > 11 then liftIO . putStrLn =<< use y
                else lift mempty

（输出 12）。

“能够随意实例化它们”有点棘手，因为添加变量只能通过改变状态对象来实现，这意味着你将不再真正处于同一个 monad 中。 Lens 具有可以使用的 zooming 概念——将状态对象拆分为“范围”并使用计算，其中只有一些变量被定义为放大到该范围。

为了使这真正方便，您需要可以随意扩展的记录。我真的很喜欢 Nikita Volkovs record library approach, this doesn't seem to have been advanced any further lately. Vinyl 也朝那个方向发展，但我没有深入研究它。

将来，我们将有 OverloadedRecordFields extension 来帮助解决此类问题。

Answer 2

不推荐此答案，参见。

为了扩展您用弱类型变量映射包装 StateT 的想法，这看起来类似于以下内容：

{-# LANGUAGE GADTs #-}

import Unsafe.Coerce
import Data.IntMap

data WeakTyped where
   WeakTyped :: a -> WeakTyped

newtype STT' m a = STT' { weakTypState :: StateT (IntMap WeakTyped) m a }
  deriving (Functor, Applicative, Monad)

newtype STT'Ref a = STT'Ref { mapIndex :: Int }

newSTTRef :: Monad m => a -> STT' m (STT'Ref a)
newSTTRef x = STT' $ do
   i <- (+1) . maximum . keys <$> get
   modify $ insert i x
   return $ STT'Ref i

readSTTRef :: Monad m => STT'Ref a -> STT' m a
readSTTRef (STT'Ref i) = STT' $ do
   unsafeCoerce . (!i) <$> get

我不相信这实际上是明智的。 Haskell 运行时间未正确处理这些 STT'Ref，特别是状态变量不会被垃圾收集。因此，如果你运行一个在循环中使用 newSTTRef 的动作，它实际上会在每次迭代中增加 IntMap 而不会释放已经“超出范围”的变量（即没有任何指向它们的引用）。

或许可以为所有这些添加一个实际的垃圾收集器，但这会使它变得非常复杂。

在 Haskell 中合并 ST 和 List monad

Combine ST and List monads in Haskell

haskell

non-deterministic

state-monad

st-monad