哈斯克尔表达功能改变其周围环境?

Question

Haskell是一种纯函数式语言，它为命令式表达式提供了语法糖。例如，这个 Python 代码：

def f():
n = 0
for i in range(10):
n += 1
return n

可以使用 monads 逐行翻译成同构 Haskell 代码。

函数改变其周围环境的代码也是如此吗？例如：

def f():
n = 0
def g():
nonlocal n
n += 1
for i in range(10):
g()
return n

有没有办法将上面的逐行翻译成同构哈斯克尔？

我已经完全准备好了答案是否定的，代码需要重新设计以不同的方式做同样的事情。但我认为值得一问的是是否有同构翻译。

Answer 1

您可以使用State来封装State的更改。

在这种情况下，您的g可能如下所示：

import Control.Monad.State.Lazy(State, modify)
g :: State Int ()
g =modify(1+)

那么f也是一个State，它首先将状态设置为0，然后运行g十次：

import Control.Monad(replicateM_)
import Control.Monad.State.Lazy(State, get, put)
f :: State Int Int
f = do
put 0
replicateM_ 10g
get

然后，您可以使用evalState :: State s a -> s -> a运行f，其中我们提供了初始状态，它将返回State s a项的结果，因此此处get返回的内容：

Prelude Control.Monad.State.Lazy> evalState f 0
10

Answer 2

William Van Onsem在评论中提到了Statemonad，这是有效的。 您也可以将其重构为尾递归函数。例如：

module Test (f) where
f :: Int
f = go 0 10 where
go :: Int -> Int -> Int
go n 0 = n
go n i = go (g n) (i-1)
g n = n+1

这通过使其成为函数的参数来捕获状态。 它的优化也相当好。 在 GHC 8.6.2 上，-O3，其相关部分编译为：

.Lc2gN:
testq %rsi,%rsi
jne .Lc2gS
movq %r14,%rbx
jmp *(%rbp)
.Lc2gS:
decq %rsi
incq %r14
jmp .Lc2gN

您可以看到 Haskell 传递了一个延续，终止大小写的分支跳转到该延续，类似于但并不完全相同的传统命令式语言将返回地址推送到堆栈上的方式。 否则，此生成的代码完全等效于命令式语言中的while或for循环：有一个终止条件的测试，一个更新保存总和和计数器的寄存器的主体，以及跳回到代码块的顶部。

此方法适用于命令式程序中的许多循环，尽管不是全部。 如果循环具有明显的副作用或更改了大型数据结构，您将需要不同的解决方案，例如使用StateT将Statemonad 与IO相结合。