functional-programming - 功能-命令式混合

Question

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

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

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

Answer 1

简短的回答是:有些系统可以满足您的需求。例如，您可以使用 ST Haskell 中的 monad(如评论中所述)。
ST monad 方法来自 Haskell 的 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避免再次线性遍历，因为不再使用可变向量。