一个`ST`-like monad可以纯粹执行（没有`ST`库）吗？ [英] Can a `ST`-like monad be executed purely (without the `ST` library)?
问题描述
ghci 的文件就可以运行它。 > { - ＃LANGUAGE GADTs，Rank2Types＃ - }
> import Control.Monad
> import Control.Monad.ST
> import Data.STRef
好的，所以我能够计算出如何表示纯代码中的ST monad。首先我们从我们的参考类型开始。它的具体价值并不重要。最重要的是， PT s a 不应该与任何其他类型 forall s 同构。 （特别是，它应该同构于（）和 Void 。）
> newtype PTRef s a = Ref {unref :: s a} - 这个定义喜欢使`toST``工作。它可能会有不同的定义。
s 的种类是 * - > * ，但现在并不重要。它可以是 polykind ，对于我们所有人护理。
>数据PT s a where
> MkRef :: a - > PT s（PTRef s a）
> GetRef :: PTRef s a - > PT s a
> PutRef :: a - > PTRef s a - > PT s（）
>并且：PT s a - > （a→PT s b）→> PT s b
非常简单。 AndThen 允许我们将它用作 Monad 。您可能想知道 return 是如何实现的。这里是它的monad实例（它只考虑关于 runPF 的monad法则，稍后定义）：
>实例Monad（PT s）其中
> （>> =）= And Then
>返回a = AndThen（MkRef a）GetRef --Sorry。我喜欢极简主义。
>实例Functor（PT s）where
> fmap = liftM
>实例应用（PT s）其中
>纯=返回
> （< *>）= ap
现在我们可以定义 fib 作为测试用例。
> fib :: Int - > PT s Integer
> fib n = do
> rold< - MkRef 0
> rnew< - MkRef 1
> replicateM_ n $ do
>旧< - GetRef rold
> new< - GetRef rnew
> PutRef new rold
> PutRef（旧+新）rnew
> GetRef rold
然后输入检查。欢呼！现在，我可以将它转换为 ST （我们现在看到为什么 s 必须是 * - > * ）
> toST :: PT（STRef s）a - > ST s a
> toST（MkRef a）= fmap Ref $ newSTRef a
> toST（GetRef（Ref r））= readSTRef r
> toST（PutRef a（Ref r））= writeSTRef r a
> toST（pa` AndThen` apb）=（toST pa）>> =（toST.apb）
<现在我们可以定义一个函数来运行 PT ，而不需要引用 ST ：
> runPF ::（全部PT a） - > a
> runPF p = runST $ toST p
runPF $ fib 7 给出 13 ，这是正确的。
我的问题是我们可以根据
ST 来定义 runPF 吗？
有没有一种纯粹的方式来定义 runPF ？ PTRef 的定义完全不重要;无论如何，它只是一个占位符类型。
如果不能定义 runPF 纯粹的，给出一个证明它不能。
性能不是问题（如果是的话，我不会让每个 return 有它自己的ref）。
我在想存在类型可能会有用。
注意：如果我们假设 a 是可动态的或者其他的东西，这很简单。我正在寻找一个适用于所有 a 的答案。
注意：事实上，答案并不是甚至必须与 PT 有很大关系。它只需要像 ST 一样强大，而不使用魔法。 （从（forall s。PT s）的转换是测试答案是否有效的一种测试。）
tl; dr：如果不调整 PT 的定义，这是不可能的。以下是核心问题：您将在某种存储介质的上下文中运行有状态计算，但是存储介质必须知道如何存储任意类型。如果没有将某些证据打包到 MkRef 构造函数中，这是不可能的 - 要么是一个存在包装的 Typeable 字典其他人建议，或证明该值属于已知的有限类型集合之一。
第一次尝试时，我们尝试使用列表作为存储介质
newtype Ix a = MkIx Int - 列表中元素的索引
interp :: PT Ix a - >状态[b] a
interp（MkRef x）=修改（++ [x]）>>获取（Ref。MkIx。length）
- ...
在我们的环境中，我们确保将它添加到列表的末尾，以便我们之前给出的 Ref s保持指向正确的元素。
这是不对的。我可以引用任何类型 a ，但是 interp 的类型表示存储介质是 b s的同类列表。当GHC拒绝这种类型的签名时，GHC让我们b然心动，抱怨它不能匹配 b 和 MkRef 。
我们不妨使用 列表作为 PT 。
infixr 4：>
data Tuple as where
E :: Tuple'[]
（：>）:: a - >元组为 - > Tuple（a'：as）
这是我个人最喜欢的Haskell数据类型之一。它是一个可扩展的元组，它由内部事物类型的列表索引。元组是异构链接列表，其中包含有关其内部事物类型的类型级信息。 （它通常被称为 HList 在 Kiselyov's文件，但我更喜欢 Tuple 。）当您将元素添加到元组的前面时，将其类型添加到类型列表的前面。以一种诗意的情绪，我曾经这样说过：The
$ b
元组的示例 s：s元组和它的类型一起生长，就像藤蔓爬上一棵竹子植物一样。 ghci> ：t'x'：> E
'x'：> E :: Tuple'[Char]
ghci> ：thello：>真：> E
hello：>真：> E :: Tuple'[[Char]，Bool]
元组内的值的引用看起来像？我们必须向GHC证明，我们从元组中获得的东西的类型确实是我们期望的类型。
data Elem as a where - 为了方便部分应用而安排的索引顺序
Here :: Elem（a'：as）a
There :: Elem as - > Elem（b'：as）a
Elem 在结构上是自然数（> Elem >）的结构，例如 There（There Here）看起来类似于自然数字如 S（SZ）），但带有额外的类型 - 在这种情况下，证明类型 a 在type-level list as 。我提到这一点是因为它很有启发性： Nat s可以创建好的列表索引，同样 Elem 对索引到一个元组很有用。在这方面，它可以替代我们引用类型中的 Int 。
（！）:: Tuple as - > Elem作为 - >
（x：> xs）！这里= x
（x：> xs）！ （There ix）= xs！ ix
我们需要一些函数来处理元组和索引。 b
输入系列为：++：bs其中
'[]：++：bs = bs
（a'：as） ：++：bs = a'：（as：++：bs）
appendT :: a - >元组为 - > （Tuple（as：++：'[a]），Elem（as：++：'[a]）a）
appendT x E =（x：> E，Here）
appendT x（y：> ys）= let（t，ix）= appendT x ys
in（y：> t，There ix）
让我们尝试为元组中的 PT 编写一个解释器>环境。
interp :: PT（Elem as）a - > State（Tuple as）
interp（MkRef x）= do
t < - get
let（newT，el）= appendTxt
put newT
return el
- ...
不可以，buster。问题是当我们获得一个新的引用时，环境中 Tuple 的类型改变了。正如我之前提到的，向元组添加某些元素会将其类型添加到元组的类型中，类型 State（Tuple as）a 的类型就是事实。 GHC并没有被这种企图诡计欺骗：无法推断（as〜（as：++：'[a1]））。
据我所知，这是车轮脱落的地方。你真正想要做的是在整个 PT 计算中保持元组的大小不变。这将要求你通过你可以获得引用的类型列表来索引 PT 本身，证明每次你允许你允许（通过给出 Elem 值）。然后，环境将看起来像一个列表元组，并且引用将包含一个 Elem （用于选择正确的列表）和一个 Int （查找列表中的特定项目）。
当然，这个计划违反了规则（您需要更改 PT ），但它也有工程问题。当我打电话给 MkRef 时，我有责任为我引用的值给出 Elem ，这非常乏味。 （也就是说，你通常可以通过使用hacky类型的证明搜索来说服GHC找到 Elem 值。）
另一件事：构成 PT s变得困难。您的计算的所有部分都必须由相同的类型列表进行索引。您可以尝试引入组合器或类，它们允许您扩展 PT 的环境，但是当您这样做时，您还必须更新所有引用。使用monad会相当困难。
一个可能更干净的实现将允许 PT 随着数据类型的变化而变化：每次遇到 MkRef 时，类型会变长。由于计算类型随着进展而变化，因此不能使用常规monad - 必须使用 IxMonad 。如果您想知道该程序的外观，请参阅我的其他答案。
最终，关键在于元组的类型由 PT 请求的值决定。环境是给定请求决定存储在其中的内容。 interp 不会选择元组中的元素，它必须来自 PT 上的索引。任何欺骗该要求的企图都会崩溃并燃烧。现在，在一个真正的依赖类型系统中，我们可以检查我们给出的 PT 值并找出
This post is literate Haskell. Just put in a file like "pad.lhs" and ghci will be able to run it.
> {-# LANGUAGE GADTs, Rank2Types #-}
> import Control.Monad
> import Control.Monad.ST
> import Data.STRef
Okay, so I was able to figure how to represent the ST monad in pure code. First we start with our reference type. Its specific value is not really important. The most important thing is that PT s a should not be isomorphic to any other type forall s. (In particular, it should be isomorphic to neither () nor Void.)
> newtype PTRef s a = Ref {unref :: s a} -- This is defined liked this to make `toST'` work. It may be given a different definition.
The kind for s is *->*, but that is not really important right now. It could be polykind, for all we care.
> data PT s a where
> MkRef :: a -> PT s (PTRef s a)
> GetRef :: PTRef s a -> PT s a
> PutRef :: a -> PTRef s a -> PT s ()
> AndThen :: PT s a -> (a -> PT s b) -> PT s b
Pretty straight forward. AndThen allows us to use this as a Monad. You may be wondering how return is implemented. Here is its monad instance (it only respects monad laws with respect to runPF, to be defined later):
> instance Monad (PT s) where
> (>>=) = AndThen
> return a = AndThen (MkRef a) GetRef --Sorry. I like minimalism.
> instance Functor (PT s) where
> fmap = liftM
> instance Applicative (PT s) where
> pure = return
> (<*>) = ap
Now we can define fib as a test case.
> fib :: Int -> PT s Integer
> fib n = do
> rold <- MkRef 0
> rnew <- MkRef 1
> replicateM_ n $ do
> old <- GetRef rold
> new <- GetRef rnew
> PutRef new rold
> PutRef (old+new) rnew
> GetRef rold
And it type checks. Hurray! Now, I was able to convert this to ST (we now see why s had to be * -> *)
> toST :: PT (STRef s) a -> ST s a
> toST (MkRef a ) = fmap Ref $ newSTRef a
> toST (GetRef (Ref r)) = readSTRef r
> toST (PutRef a (Ref r)) = writeSTRef r a
> toST (pa `AndThen` apb) = (toST pa) >>= (toST . apb)
Now we can define a function to run PT without referencing ST at all:
> runPF :: (forall s. PT s a) -> a
> runPF p = runST $ toST p
runPF $ fib 7 gives 13, which is correct.
My question is can we define runPF without reference using ST at all?
Is there a pure way to define runPF? PTRef's definition is completely unimportant; it's only a placeholder type anyway. It can be redefined to whatever makes it work.
If you cannot define runPF purely, give a proof that it cannot.
Performance is not a concern (if it was, I would not have made every return have its own ref).
I'm thinking that existential types may be useful.
Note: It's trivial if we assume is a is dynamicable or something. I'm looking for an answer that works with all a.
Note: In fact, an answer does not even necessarily have much to do with PT. It just needs to be as powerful as ST without using magic. (Conversion from (forall s. PT s) is sort of a test of if an answer is valid or not.)
tl;dr: It's not possible without adjustments to the definition of PT. Here's the core problem: you'll be running your stateful computation in the context of some sort of storage medium, but said storage medium has to know how to store arbitrary types. This isn't possible without packaging up some sort of evidence into the MkRef constructor - either an existentially wrapped Typeable dictionary as others have suggested, or a proof that the value belongs to one of a known finite set of types.
For a first attempt, let's try using a list as the storage medium and integers to refer to elements of the list.
newtype Ix a = MkIx Int -- the index of an element in a list
interp :: PT Ix a -> State [b] a
interp (MkRef x) = modify (++ [x]) >> gets (Ref . MkIx . length)
-- ...
When storing a new item in the environment, we make sure to add it to the end of the list, so that Refs we've previously given out stay pointing at the correct element.
This ain't right. I can make a reference to any type a, but the type of interp says that the storage medium is a homogeneous list of bs. GHC has us bang to rights when it rejects this type signature, complaining that it can't match b with the type of the thing inside MkRef.
Undeterred, let us have a go at using a heterogeneous list as the environment for the State monad in which we'll interpret PT.
infixr 4 :>
data Tuple as where
E :: Tuple '[]
(:>) :: a -> Tuple as -> Tuple (a ': as)
This is one of my personal favourite Haskell data types. It's an extensible tuple indexed by a list of the types of the things inside it. Tuples are heterogeneous linked lists with type-level information about the types of the things inside it. (It's often called HList following Kiselyov's paper but I prefer Tuple.) When you add something to the front of a tuple, you add its type to the front of the list of types. In a poetic mood, I once put it this way: "The tuple and its type grow together, like a vine creeping up a bamboo plant."
Examples of Tuples:
ghci> :t 'x' :> E
'x' :> E :: Tuple '[Char]
ghci> :t "hello" :> True :> E
"hello" :> True :> E :: Tuple '[[Char], Bool]
What do references to values inside tuples look like? We have to prove to GHC that the type of the thing we're getting out of the tuple is indeed the type we expect.
data Elem as a where -- order of indices arranged for convenient partial application
Here :: Elem (a ': as) a
There :: Elem as a -> Elem (b ': as) a
The definition of Elem is structurally that of the natural numbers (Elem values like There (There Here) look similar to natural numbers like S (S Z)) but with extra types - in this case, proving that the type a is in the type-level list as. I mention this because it's suggestive: Nats make good list indices, and likewise Elem is useful for indexing into a tuple. In this respect it'll be useful as a replacement for the Int inside our reference type.
(!) :: Tuple as -> Elem as a -> a
(x :> xs) ! Here = x
(x :> xs) ! (There ix) = xs ! ix
We need a couple of functions to work with tuples and indices.
type family as :++: bs where
'[] :++: bs = bs
(a ': as) :++: bs = a ': (as :++: bs)
appendT :: a -> Tuple as -> (Tuple (as :++: '[a]), Elem (as :++: '[a]) a)
appendT x E = (x :> E, Here)
appendT x (y :> ys) = let (t, ix) = appendT x ys
in (y :> t, There ix)
Let's try and write an interpreter for a PT in a Tuple environment.
interp :: PT (Elem as) a -> State (Tuple as) a
interp (MkRef x) = do
t <- get
let (newT, el) = appendT x t
put newT
return el
-- ...
No can do, buster. The problem is that the type of the Tuple in the environment changes when we obtain a new reference. As I mentioned before, adding something to a tuple adds its type to the tuple's type, a fact belied by the type State (Tuple as) a. GHC's not fooled by this attempted subterfuge: Could not deduce (as ~ (as :++: '[a1])).
This is where the wheels come off, as far as I can tell. What you really want to do is keep the size of the tuple constant throughout a PT computation. This would require you to index PT itself by the list of types to which you can obtain references, proving every time you do so that you're allowed to (by giving an Elem value). The environment would then look like a tuple of lists, and a reference would consist an Elem (to select the right list) and an Int (to find the particular item in the list).
This plan breaks the rules, of course (you need to change the definition of PT), but it also has engineering problems. When I call MkRef, the onus is on me to give an Elem for the value I'm making a reference to, which is pretty tedious. (That said, you can usually convince GHC to find Elem values by proof search using a hacky type class.)
Another thing: composing PTs becomes difficult. All the parts of your computation have to be indexed by the same list of types. You could attempt to introduce combinators or classes which allow you to grow the environment of a PT, but you'd also have to update all the references when you do that. Using the monad would be quite difficult.
A possibly-cleaner implementation would allow the list of types in a PT to vary as you walk around the datatype: every time you encounter a MkRef the type gets one longer. Because the type of the computation changes as it progresses, you can't use a regular monad - you have to resort to IxMonad . If you want to know what that program looks like, see my other answer.
Ultimately, the sticking point is that the type of the tuple is determined by the value of the PT request. The environment is what a given request decides to store in it. interp doesn't get to choose what's in the tuple, it must come from an index on PT. Any attempt to cheat that requirement is going to crash and burn. Now, in a true dependently-typed system we could examine the PT value we were given and figure out what as should be. Alas, Haskell is not a dependently-typed system.
这篇关于一个`ST`-like monad可以纯粹执行（没有`ST`库）吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
