8

纯函数式编程语言不允许可变数据，但某些计算以命令式方式更自然/直观地表达 - 或者算法的命令式版本可能更有效。我知道大多数函数式语言都不是纯粹的，并且允许您分配/重新分配变量并执行命令式的事情，但通常不鼓励这样做。

我的问题是，为什么不允许在局部变量中操作局部状态，而是要求函数只能访问它们自己的局部变量和全局常量（或者只是在外部范围中定义的常量）？这样，所有函数都保持引用透明性（它们总是在给定相同参数的情况下给出相同的返回值），但在函数内，计算可以用命令式术语表示（例如，while 循环）。

IO 等仍然可以通过正常的功能方式完成 - 通过单子或传递“世界”或“宇宙”令牌。

4

2 回答 2

3

我的问题是，为什么不允许在局部变量中操作局部状态，而是要求函数只能访问它们自己的局部变量和全局常量（或者只是在外部范围中定义的常量）？

好问题。我认为答案是可变局部变量的实用价值有限，但可变堆分配的数据结构（主要是数组）非常有价值，并且构成了许多重要集合的支柱，包括高效的堆栈、队列、集合和字典。因此，仅将突变限制为本地人不会给其他纯粹的函数式语言带来任何突变的重要好处。

与此相关的是，交换纯功能数据结构的顺序进程通信提供了两个世界的许多好处，因为顺序进程可以在内部使用突变，例如可变消息队列比任何纯功能队列快约 10 倍。例如，这在 F# 中是惯用的，其中 a 中的代码MailboxProcessor使用可变数据结构，但它们之间通信的消息是不可变的。

在这种情况下，排序是一个很好的案例研究。Sedgewick 的 C 语言快速排序简短而简单，比任何语言中最快的纯函数排序快数百倍。原因是快速排序会就地改变数组。可变的本地人不会有帮助。大多数图形算法的情况相同。

于 2012-07-05T08:43:51.267 回答
3

简短的回答是：有一些系统可以满足您的需求。例如，您可以使用STHaskell 中的 monad 来实现（如评论中所引用）。

STmonad 方法来自 Haskell的Control.Monad.ST. 用 monad编写的代码可以在方便的地方ST使用引用 ( )。STRef好的部分是您甚至可以ST在纯代码中使用 monad 的结果，因为它本质上是自包含的（这基本上是您在问题中想要的）。

这种自包含属性的证明是通过类型系统完成的。STmonad 带有一个状态线程参数，通常用 type-variable表示s。当您进行这样的计算时，您将获得单子结果，其类型如下：

foo :: ST s Int

要真正把它变成一个纯粹的结果，你必须使用

runST :: (forall s . ST s a) -> a

你可以像这样阅读这种类型：给我一个s类型参数无关紧要的计算，我可以给你返回计算的结果，没有ST包袱。这基本上可以防止可变ST变量转义，因为它们会随身携带s，这将被类型系统捕获。

这可以用于对使用底层可变结构（如vector 包）实现的纯结构产生良好的效果。人们可以在有限的时间内摆脱不变性来做一些改变底层数组的事情。例如，可以将不可变Vector与不纯算法包结合起来，以保持原地排序算法的大部分性能特征并仍然获得纯度。

在这种情况下，它看起来像：

pureSort :: Ord a => Vector a -> Vector a
pureSort vector = runST $ do
  mutableVector <- thaw vector
  sort mutableVector
  freeze mutableVector

和函数是线性时间复制thaw，freeze但这不会破坏整体 O(n lg n) 运行时间。您甚至可以使用它unsafeFreeze来避免另一个线性遍历，因为不再使用可变向量。

于 2012-07-05T11:43:19.370 回答