函数式-命令式混合

Question

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

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

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

Answer 1

简短的答案是:有系统允许你想要的东西。例如，您可以使用Haskell中的ST monad来完成此操作(如注释中所述)。

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

这个自包含属性的证明是通过类型系统完成的。ST monad带有一个状态线程参数，通常用类型变量s表示。当你有这样的计算时，你会得到一元的结果，类型如下：

foo :: ST s Int

要真正将其转换为纯结果，您必须使用

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

您可以这样理解此类型:给我一个计算，其中s类型参数无关紧要，我可以在没有ST负担的情况下返回计算结果。这基本上防止了可变的ST变量转义，因为它们会携带s，这将被类型系统捕获。

这可以用来在使用底层可变结构(如vector package)实现的纯结构上产生良好的效果。人们可以在有限的时间内摆脱不变性，在适当的地方做一些改变底层数组的事情。例如，可以将不可变的Vector与impure algorithms package相结合，以保持就地排序算法的大部分性能特征，同时仍然获得纯度。

在本例中，它看起来类似于：

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来避免另一次线性遍历，因为可变向量不会再次使用。

Answer 2

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

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

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

在这种情况下，排序是一个很好的案例研究。Sedgewick在C中的快速排序是简短和简单的，并且比任何语言中最快的纯函数式排序快数百倍。原因是快速排序就地改变了数组。可变的局部变量不会有帮助。大多数图形算法的情况也是如此。