94

我正在48 小时内完成为自己编写一个方案（我最多大约 85 小时），并且我已经完成了关于添加变量和分配的部分。本章有一个很大的概念跳跃，我希望它分两步完成，中间有一个很好的重构，而不是直接跳到最终的解决方案。总之……</p>

我迷失了许多似乎服务于相同目的的不同类：State、ST、IORef和MVar. 前三个在正文中被提及，而最后一个似乎是很多 StackOverflow 关于前三个问题的首选答案。它们似乎都在连续调用之间携带一种状态。

它们各自是什么，它们之间有何不同？

特别是这些句子没有意义：

相反，我们使用一个称为状态线程的特性，让 Haskell 为我们管理聚合状态。这让我们可以像在任何其他编程语言中一样对待可变变量，使用函数来获取或设置变量。

和

IORef 模块允许您在 IO monad中使用有状态变量。

所有这一切都使这条线type ENV = IORef [(String, IORef LispVal)]令人困惑——为什么是第二条IORef？如果我改写会破坏什么type ENV = State [(String, LispVal)]？

4

3 回答 3

121

状态单子：可变状态的模型

State monad 是具有状态的程序的纯函数环境，具有简单的 API：

  • 得到
  • 放

mtl 包中的文档。

当需要单个控制线程中的状态时，通常使用 State monad。它实际上并没有在其实现中使用可变状态。相反，程序由状态值参数化（即状态是所有计算的附加参数）。状态似乎只在单个线程中发生变化（并且不能在线程之间共享）。

ST monad 和 STRefs

ST monad 是 IO monad 的受限表亲。

它允许任意可变状态，在机器上实现为实际的可变内存。该 API 在无副作用的程序中是安全的，因为 rank-2 类型参数可防止依赖于可变状态的值逃离本地范围。

因此，它允许在其他纯程序中控制可变性。

常用于可变数组和其他发生突变，然后冻结的数据结构。它也非常有效，因为可变状态是“硬件加速”的。

主要 API：

  • Control.Monad.ST
  • runST——开始一个新的记忆效应计算。
  • 和STRefs：指向（本地）可变单元格的指针。
  • 基于 ST 的数组（如向量）也很常见。

将其视为 IO monad 中危险性较小的兄弟。或者IO，你只能读写内存。

IORef : IO 中的 STRef

这些是 IO monad 中的 STRef（见上文）。它们没有与 STRef 相同的关于位置的安全保证。

MVars : 带锁的 IORefs

与 STRefs 或 IORefs 类似，但附加了一个锁，用于从多个线程进行安全的并发访问。IORefs 和 STRefs 仅在使用时atomicModifyIORef（比较和交换原子操作）在多线程设置中是安全的。MVar 是一种更通用的安全共享可变状态的机制。

通常，在 Haskell 中，使用 MVar 或 TVar（基于 STM 的可变单元），而不是 STRef 或 IORef。

于 2011-04-04T23:44:52.797 回答
37

好的，我将从IORef. IORef提供一个在 IO monad 中可变的值。它只是对某些数据的引用，并且与任何引用一样，有一些函数允许您更改它所引用的数据。在 Haskell 中，所有这些函数都在IO. 您可以将其视为数据库、文件或其他外部数据存储——您可以在其中获取和设置数据，但这样做需要通过 IO。之所以需要 IO 是因为 Haskell 是纯的；编译器需要一种方法来知道在任何给定时间引用指向哪些数据（阅读sigfpe 的“你本可以发明 monads”博文）。

MVars 与 IORef 基本相同，除了两个非常重要的区别。 MVar是一种并发原语，因此它是为从多个线程访问而设计的。第二个区别是 anMVar是一个可以是满的或空的盒子。因此，如果 anIORef Int总是有 an Int（或底部），anMVar Int可能有 anInt或它可能是空的。如果一个线程试图从一个空的值中读取一个值MVar，它将阻塞直到MVar被填充（被另一个线程）。基本上 anMVar a等价于IORef (Maybe a)具有额外语义的对并发有用。

State是一个提供可变状态的 monad，不一定是 IO。事实上，它对于纯计算特别有用。如果您有一个使用 state 但不使用 的算法IO，那么Statemonad 通常是一个优雅的解决方案。

还有一个单子转换器版本的状态，StateT. 这经常用于保存程序配置数据，或应用程序中的“游戏世界状态”类型的状态。

ST有点不同。中的主要数据结构ST是STRef，它类似于 anIORef但具有不同的 monad。monad 使用类型系统技巧（文档提到的ST“状态线程”）来确保可变数据无法逃脱 monad；也就是说，当您运行 ST 计算时，您会得到纯结果。ST 有趣的原因是它是一个类似于 IO 的原始 monad，允许计算对字节数组和指针执行低级操作。这意味着ST可以在对可变数据使用低级操作时提供纯接口，这意味着它非常快。从程序的角度来看，就好像ST计算在具有线程本地存储的单独线程中运行。

于 2011-04-04T23:55:57.160 回答
17

其他人做了核心的事情，但要回答直接的问题：

所有这些都使线型ENV = IORef [(String, IORef LispVal)] 令人困惑。为什么是第二个 IORef？如果我这样做会破坏什么type ENV = State [(String, LispVal)]？

Lisp 是一种具有可变状态和词法范围的函数式语言。想象一下，您已经关闭了一个可变变量。现在，您已经在其他一些函数中引用了这个变量——比如说（在 haskell 样式的伪代码中）(printIt, setIt) = let x = 5 in (\ () -> print x, \y -> set x y)。你现在有两个函数——一个打印 x，一个设置它的值。当您评估时printIt，您想在定义的初始环境中查找 x的名称printIt，但您想在被调用的环境中查找名称绑定到的值（之后可能已被调用多次）。printItsetIt

There are ways besids the two IORefs to do this, but you certainly need more than the latter type you've proposed, which doesn't allow you to alter the values that names are bound to in a lexically-scoped fashion. Google the "funargs problem" for a whole lot of interesting prehistory.

于 2011-04-05T14:19:49.993 回答