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

Question

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

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

这是一个纯函数 (wink wink nudge nudge)，只要不进一步引用输入数组及其元素即可。 C 类型系统不会为我们强制执行，但原则上它似乎是可执行的。

gcc生成的代码简单高效：

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

我们的函数通过在常数时间内创建一个全新的数组并且不使用额外的内存来实现看似不可能的事情。好的。是否可以编写具有类数组输入和输出的 Haskell 函数，并且可以用类似的代码有效地实现？有没有办法表达"this is the last reference to this variable"让一个纯函数在幕后蚕食变量？

如果函数被内联，那么这里不需要发生任何有趣的事情，所以我们假设调用者和函数将被单独编译。

Answer 1

虽然ST monad is not exactly what you describe, in practice you may implement most of that using STUArray。因此，您的代码模型可能类似于：

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

请注意 run 保持纯净，返回数组的早期版本不会泄露到任何地方:

\> run 8 array (0,7) [(0,1),(1,0),(2,1),(3,1),(4,2),(5,3),(6,5),(7,8)]

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

Haskell: use last reference to a variable to efficiently create a new variable

c

haskell

in-place

ghc

purely-functional