哈斯克尔：使用最后一个引用变量有效地创建一个新的变量 [英] Haskell: use last reference to a variable to efficiently create a new variable

问题描述

本C code可在概念上被描述为创建新阵列相同的输入数组，但以1作为第一个元素：

This C code can conceptually be described as creating a new array identical to an input array but with 1 as the first element:

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

这是一个纯函数（眼色微调微调），只要没有进一步的引用来输入数组和元素组成。 C类型系统将不执行，对于我们，但它似乎在原则上执行。

This is a pure function (wink wink nudge nudge) so long as no further references are made to the input array and its elements. The C type system won't enforce that for us but it seems enforceable in principle.

在code的GCC产生是简单而有效的：

The code that gcc generates is simple and efficient:

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

我们的功能，通过建立在固定时间内一个全新的阵列和不使用额外的内存达到了看似不可能的。尼斯。可以用类似数组的输入和输出功能的Haskell编写，可以用类似code被有效执行？有没有一种方法能恩preSS这是最后一个引用这个变量，这样一个纯函数可以蚕食幕后的变量？

Our function achieves the seemingly impossible by creating a whole new array in constant time and using no additional memory. Nice. Can a Haskell function with array-like input and output be written that could be validly implemented with similar code? Is there a way to express "this is the last reference to this variable" so that a pure function can cannibalize the variable behind the scenes?

如果该函数被内联再没有什么有趣的需求，在这里发生，所以让我们假设主叫和功能将被单独编译。

If the function gets inlined then nothing interesting needs to happen here so let's suppose the caller and function will be compiled separately.

推荐答案

ST单子 是的不的正是你的描述，实际上，你可以实现大多数使用的 STUArray 。所以，模拟你的code可能是这样的：

Though ST monad is not exactly what you describe, in practice you may implement most of that using STUArray. So, a mock up of your code may be something like:

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

如果你有哪些变异数组原地，像另一个功能：

and if you have another function which mutates the array in-place, like:

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 ：

you may bind the two impure function together and call them inside a pure function using 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 8
array (0,7) [(0,1),(1,0),(2,1),(3,1),(4,2),(5,3),(6,5),(7,8)]

这篇关于哈斯克尔：使用最后一个引用变量有效地创建一个新的变量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！