从概念上讲,此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函数,并可以用类似的代码有效地实现它?有没有一种表达“这是对该变量的最后引用”的方法,以便纯函数可以在后台蚕食该变量?
如果函数被内联,则这里不需要发生任何有趣的事情,因此,假设调用者和函数将分别编译。
尽管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)]
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句