在Haskell中合并ST和List单子 [英] Combine ST and List monads in Haskell

问题描述

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

Using the StateT monad transformer, I can create the type StateT s [] a, which is isomorphic to s -> [(a, s)]. Now I would prefer to use the STT monad transformer instead, as I would like to have multiple mutable variables of different types, and would like to be able to instantiate them at will, depending on the results of earlier computations.

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

However, the linked documentation for STT mentions explicitly:

此monad转换器不应与可能包含多个答案的monad(例如列表monad)一起使用.原因是状态令牌将在不同的答案之间重复，这会导致发生不良事件(例如，丢失引用透明性).安全的monad包括monad State，Reader，Writer，Maybe以及它们对应的monad转换器的组合.

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.

那我有什么选择?

要完全清楚:

• 我追求的是不确定性.我希望能够分叉计算，为每个分支提供自己的整个状态副本.
• 我不太介意并行性，因为性能并不是我最大的担忧.
• 我不是 是并发的:不同的计算分支不应共享可变变量；相反，它们都应该在自己的原始可变变量的副本上工作.

• What I'm after, is non-determinism. I want to be able to fork my computation, giving each branch its own copy of the entire state.
• I don't mind much for parallelism, as performance is not my greatest concern.
• What I'm not after is concurrency: different branches of computation should not share mutable variables; rather, they should all work on their own copy of the original mutable variable.

我已经认识到，沿StateT线运行的STT monad变压器本质上是不安全的.有了它，我们可以构建类型STT sloc (ListT (ST sglob)) a.在这里，sglob是全局状态的名称，而sloc是本地状态的名称.* 现在，我们可以使用全局状态在线程之间交换局部状态引用，从而潜在地获得对未初始化变量的引用.

I've come to realize that an STT monad transformer that behaves along the lines of StateT is inherently unsafe. With it, we could build a type STT sloc (ListT (ST sglob)) a. Here, sglob is the name of the global state, while sloc is the name of the local state.* Now we can use the global state to exchange local state references between threads, thus potentially obtaining references to uninitialized variables.

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

*For comparison, the corresponding StateT construction is StateT sloc (ListT (State sglob)) a, which is isomorphic to sloc -> sglob -> ([(a, sloc)], sglob).

推荐答案

您不会避开StateT，因为对于这种不确定性的东西，编译器需要始终知道需要分支出哪些变量".当变量可能潜伏在STRef s处时，这是不可能的.

You won't get around StateT, because for this nondeterminism stuff the compiler needs to know always which "variables" need to be branched out. This is not possible when the variables could be anywhere lurking as STRefs.

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

To still get "multiple variables of different types", you'll need to pack them in a suitable record and use that as the single actual state variable. Seems awkward to deal with such a state object? Well, it's not that bad when using lenses to access the "individual variables".

{-# 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具有缩放的概念，使用–将状态对象分成作用域"，并使用仅将某些变量定义为放大到该范围的计算.

"Able to instantiate them at will" is a bit more tricky, because adding variables is only possible through changing the state object, which means you'll not really be in the same monad anymore. Lens has the notion of zooming which could be used – splitting up the state object into "scopes" and using the computations where only some of the variables are defined as zoomed in onto that scope.

要使其真正方便，您需要可以随意扩展的记录.我真的很喜欢Nikita Volkovs record库方法，这似乎没有最近有进一步的发展. 乙烯基也朝着这个方向发展，但我对此并没有进行太多研究.

To make this really convenient you'd need records that can be extended at will. I really liked Nikita Volkovs record library approach, this doesn't seem to have been advanced any further lately. Vinyl also goes in that direction, but I haven't looked into it much.

将来，我们将具有

In the future, we will have the OverloadedRecordFields extension that will help with this kind of stuff.

这篇关于在Haskell中合并ST和List单子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！