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    $1, (%rdi)
    ret

我们的功能通过在恒定时间内创建一个全新的数组并且不使用额外的内存来实现看似不可能的功能.尼斯.可以使用类似代码有效地实现具有类似数组的输入和输出的Haskell函数吗？有没有办法表达"这是对这个变量的最后一个引用",以便纯函数可以在幕后蚕食变量？

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

Answer 1

虽然ST monad是不正是你的描述,实际上,你可以使用实现多数认为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)]