Haskell：使用对变量的最后引用来有效地创建新变量

Question

此C代码在概念上可以描述为创建一个与输入数组相同，但第一个元素为1的新数组：

int* retire_and_update(int* arr) {
    arr[0] = 1;
    return arr;
}

这是一个纯函数（眨眼眨眼轻推微调），只要不对输入数组及其元素做进一步引用即可。 C类型系统不会为我们强制执行此操作，但原则上似乎可以执行。

gcc生成的代码简单而有效：

retire_and_update:
    movq    %rdi, %rax
    movl    $1, (%rdi)
    ret

我们的函数通过在恒定时间内创建一个全新的数组并且不使用额外的内存来实现看似不可能的事情。真好是否可以编写具有类似数组的输入和输出的Haskell函数，并且可以使用类似的代码有效地实现该函数？有没有一种表达“这是对该变量的最后引用”的方法，以便纯函数可以在后台蚕食该变量？

如果函数内联，那么这里不需要发生任何有趣的事情，因此，假设调用者和函数将分别编译。

Answer 1

尽管ST monad与您描述的完全相同，但实际上，您可以使用ST monad来实现大多数功能。因此，模拟您的代码可能类似于：STUArray

并且如果您还有另一个函数可以就地改变数组，例如：

STUArray

您可以
bind

两个不纯函数在一起，并且在纯函数中调用它们使用

import Control.Monad (forM_)
import Control.Monad.ST (ST)
import Data.Array.Unboxed (UArray)
import Data.Array.ST (STUArray, newArray, readArray, writeArray, runSTUArray)

retire_and_update :: STUArray s Int Int -> ST s (STUArray s Int Int)
retire_and_update arr = do
    writeArray arr 0 1
    return arr

：

mutate_inplace :: STUArray s Int Int -> Int -> ST s ()
mutate_inplace arr size = do
    forM_ [2..size - 1] $ \i -> do
        a <- readArray arr (i - 2)
        b <- readArray arr (i - 1)
        writeArray arr i (a + b)

请注意，runSTUArray保持纯净，并且
返回的数组的早期版本不会泄漏到任何地方

：

run :: Int -> UArray Int Int
run size = runSTUArray $ do
    arr <- newArray (0, size - 1) 0
    retire_and_update arr
    mutate_inplace arr size
    return arr