问题标签 [st-monad]

过去一两个月我一直在学习 Haskell，最近解决了这个编码问题。额外的挑战是在没有额外空间和线性时间的情况下完成任务，我认为这不可能以纯粹的功能方式完成，所以我自然而然地发现了 ST monad，我认为这将是一个很好的机会了解更多信息。无论如何，这是我写的代码：

这个想法是使用 1 ≤ a[i] ≤ n 的前提条件，并且每个元素最多出现 2 次。但是代码给了我以下错误。

我希望有人能指出我正确的方向！

我正在为 Haskell 中的一种简单的命令式编程语言编写一个（小步）解释器。我想在 IO monad 之外进行评估，因此我试图将 ST monad 用于可变变量。但是我意识到这意味着向我的值类型引入一个新的幻像类型变量，但是我的表达式类型也需要它，然后我的语句类型也需要它，等等第四。

我的问题是，有什么好的方法可以避免这个问题。我可以以某种方式隐藏幻像类型吗？我试图通过forall s.在我的 AST 定义中引入 a 来做到这一点，但编译器对此并不满意。

场景如下：Given 是一个 C 库，其核心是一些结构，其上的操作由大量 C 函数提供。

第 1 步：使用 Haskell 的FFI创建一个包装器。它具有myCLibInit :: IO MyCLibObj、myCLibOp1 :: MyCLibObj -> ... -> IO ()等功能。MyCLibObj是一个不透明类型，它携带（并隐藏） aPtr或ForeignPtr实际的 C 结构，例如在本wiki或RWH ch. 17 .

第 2 步：使用unsafeIOToSTfromControl.Monad.ST.Unsafe将所有IO动作转换为ST动作。这是通过引入类似的东西来完成的

然后将所有IO函数包装在ST函数中，例如：

这允许编写反映使用类似 OO 的 C 库的命令式程序，例如：

第 3 步：MyCLibObj通常将多个操作混合在一个 do-block上是没有意义的。例如，当 C 结构是（或应该被认为是）单例实例时。做类似doSomething上面的事情要么是荒谬的，要么是完全禁止的（例如，当 C 结构是 a 时static）。在这种情况下，类似于Statemonad 的语言是必要的：

在哪里

这就引出了一个问题：如何将ST s amonad 重新打扮成更像Statemonad 的东西。由于withMyCLibInstance将使用runST新的 monad 函数，我们称之为Q（对于 'q'uestion），应该是

这对我来说看起来很奇怪。我已经在Functor为此实现实例而苦苦挣扎Q，更不用说Applicative和Monad. ST s实际上已经是一个 monad，但是 states不能逃脱STmonad，因此forall s. ST s a. 这是摆脱的唯一方法，s因为runST :: (forall s. ST s a) -> a，并且withMyCLibInstance只是 amyCLibInit'后跟 a runST。但不知何故，这不合适。

处理第 3 步的正确方法是什么？我应该做第 2 步，还是Q在第 1 步之后滚动我的权利？我的感觉是这应该很简单。ST单子有我需要的一切，只是Q需要以正确的方式设置......

更新 1：步骤 3 中的单例和静态结构示例不是很好。如果两个这样的 do 块并行执行，可能会发生非常糟糕的事情，即两个 do 块将并行处理同一个 C 结构。

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

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

这个单子转换器不应该与可以包含多个答案的单子一起使用，例如列表单子。原因是状态令牌将在不同的答案中重复，这会导致坏事发生（例如失去参考透明度）。安全单子包括单子 State、Reader、Writer、Maybe 以及它们相应的单子转换器的组合。

那么我的选择是什么？

要完全清楚：

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

编辑：（编辑编辑：以下反例无效，ListT不应应用于非交换单子和ST。State）我开始意识到，STT按照 StateT有了它，我们可以构建一个 type STT sloc (ListT (ST sglob)) a。这里，sglob是全局状态sloc的名称，而是局部状态的名称。* 现在我们可以使用全局状态在线程之间交换局部状态引用，从而有可能获得对未初始化变量的引用。

*为了比较，对应的StateT结构是StateT sloc (ListT (State sglob)) a，它同构于sloc -> sglob -> ([(a, sloc)], sglob).

但是，文档STT说：

这个单子转换器不应该与可以包含多个答案的单子一起使用，例如列表单子。原因是状态令牌将在不同的答案中重复，这会导致坏事发生（例如失去参考透明度）。安全单子包括单子 State、Reader、Writer、Maybe 以及它们相应的单子转换器的组合。

我希望能够自己判断对STTmonad 的某种使用是否安全。特别是，我想了解与 List monad 的交互。我知道那STT sloc (ListT (ST sglob)) a是不安全的，但是呢STT sloc []？

我发现（至少在 GHC 中）最终是使用,等STT神奇的构造实现的。是否有任何关于这些对象如何表现的准确文档？MuteVar#State#realWorld#

这与我之前的一个问题密切相关。

的文档Data.Vector.unsafeFreeze说：

Unsafe[ly] 在不复制的情况下将可变向量转换为不可变向量。在此操作之后可能无法使用可变向量。

我想准确描述“不安全”在这里的含义。从实验上看，它似乎“仅”暗示对原始可变向量的进一步修改将导致由返回的不可变向量unsafeFreeze不再是纯的：

我可以想象修改在“不安全”冻结中使用的源代码会做各种会导致更糟糕的行为的粗糙的事情，例如段错误。不幸的是，我很快就试图阅读有关不安全操作的源代码。

我可以依靠上述杂质作为这些操作“不安全”的唯一方式吗？

对于上下文：我需要在典型的不可变数据结构上实现各种修改算法，并且在内部可变性范围内不重用其面向公众的 API 将非常不方便（因为 AFAICT 无法通用访问这两个可变数据和不可变向量）。（Ab）unsafeFreeze当我需要使用该 API 时使用将是完美的逃生舱口，只要我不让自己在路上遇到更多不愉快的副作用。

这个问题是这个线程的续集：https ://stackoverflow.com/a/54317095/4400060

我在那里询问有关携带STRef的ReaderT环境并在其下执行 ST-actions 的问题。我的设置现在看起来像：

总的来说它很酷——我可以dataspace自由地访问或修改。但是，当我添加不可变时，namespace我开始挣扎。我需要的功能是以不会影响进一步计算的命名空间的方式运行Comp更新的操作namespace——正是这样local做的。

首先，我想为 编写MonadReader实例Comp，但是我遇到了ST的幻像类型并得到了illegal instance错误：

完整的错误信息：

我理解这个错误，但我认为没有办法绕过它。老实说，我并不需要完整local的功能。我只需要能够以Comp不同namespace但相同的方式运行dataspace。

最好的解决方案是提供完整的MonadReader实例。我知道这可能是不可能的，所以作为一种解决方法，我想要一个函数

总结：我希望能够在Comp修改后运行，namespace同时保持dataspace不变作为参考，保留所有更改。

怎么做？如果需要，我可以接受修改我的初始设置。

我有一个计算，我将值插入到 a 中Map，然后再次查找它们。我知道在插入之前我从来没有使用过钥匙，但(!)随意使用会让我感到紧张。我正在寻找一种方法来获得一个不返回 a 的总查找函数，Maybe并且类型系统可以防止我意外滥用。

我的第一个想法是制作一个类似于 的 monad 转换器StateT，其中状态为 aMap并且在 monad 中有用于插入和查找的特殊功能。insert 函数返回一个Receipt s knewtype，其中s是STmonad风格的幻象索引类型，k是 key 的类型，lookup 函数采用 aReceipt而不是裸 key。通过隐藏Receipt构造函数并使用类似于 的量化运行函数runST，这应该确保仅在插入同一映射后发生查找。（完整代码如下。）

但我担心我重新发明了一个轮子，或者担心有另一种方法可以安全地进行全地图查找，并且已经在使用中。在某处的公共包中是否有针对此问题的现有技术？

编辑：一些评论者问我为什么要保留 aReceipt而不是实际值。我希望能够使用Receiptin Sets 和Maps （我没有在我的 MVCE 中添加EqandOrd实例Receipt，但我的项目中有它们），但我的值Map是不相等的。如果我Receipt用键值对 newtype 替换，我将不得不Eq为该对实现一个不诚实的实例，而忽略该值，然后我会对此感到紧张。这Map是为了确保在任何给定时间我的任何等效“代理”键都只考虑一个值。

我想一个对我来说很好的替代解决方案是一个 monad 转换器，它提供Refs 的供应，其中data Ref v = Ref Int vmonad 确保Refs 以唯一的IntID 给出，Eq Ref等等。只看Int（现在诚实由Ints) 的唯一性保证。我也会接受指向野外这种变压器的指针。

我正在尝试在 Haskell 上实现插入排序Data.Array.ST，并使用一元比较函数。即，sortByM :: (Monad m, Ix i, Enum i, Eq i) => (e -> e -> Ordering) -> STArray s i e -> m (ST s ())。这是我的代码，用于上下文：

据我了解，我遇到的问题是loopM' 的第一个参数应该有 type ST s i -> m (Either i (ST s ()))，但由于runST' 隐藏ST内部状态的方法，fmap (mapLeft runST) . bubbleBackOnce ary有 type (forall s'. ST s' i) -> Either i (ST s i)。这是我第一次使用 ST，所以我不知道如何解决这个问题。此外，这是一个宠物项目，所以我试图避免依赖现有的可以简化事情的库，例如STMonadTrans。

我ST使用随机数运行以下代码：

我想重构generate，以便计算的整个尾部不是在 a 下case，而是(assassins2, others2)在子计算中计算，即我想这样重写它：

我相信这应该是一个等效的转换。但是，第二个版本无法通过以下方式进行类型检查：