Haskell: sử dụng tài liệu tham khảo cuối cùng cho một biến để tạo ra hiệu quả một biến đang

Question

C này mới khái niệm có thể được mô tả như tạo ra một mảng mới giống với một mảng đầu vào nhưng với 1 là yếu tố đầu tiên:

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

này là một hàm thuần túy (wink wink nudge nudge) miễn là không có tham chiếu thêm nào được thực hiện cho mảng đầu vào và các phần tử của nó. Hệ thống kiểu C sẽ không thực thi điều đó đối với chúng ta nhưng nó có vẻ thực thi theo nguyên tắc.

Mã gcc mà tạo ra rất đơn giản và hiệu quả:

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

chức năng của chúng tôi đạt được dường như bất khả thi bằng cách tạo ra một mảng hoàn toàn mới trong thời gian liên tục và không sử dụng bộ nhớ bổ sung. Tốt đẹp. Có thể hàm Haskell với đầu vào và đầu ra giống như mảng được viết có thể được triển khai hợp lệ với mã tương tự không? Có cách nào để diễn tả "đây là tham chiếu cuối cùng cho biến này" sao cho một hàm thuần túy có thể ăn mòn biến đằng sau hậu trường?

Nếu hàm được gạch chân thì không có gì thú vị cần xảy ra ở đây, vì vậy, giả sử người gọi và chức năng sẽ được biên dịch riêng.

Answer 1

Mặc dù ST monad là không chính xác những gì bạn mô tả, trên thực tế bạn có thể thực hiện hầu hết điều đó bằng cách sử dụng STUArray. Vì vậy, một mô hình thành từ các mã của bạn có thể được giống như:

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 

và nếu bạn có một chức năng mà đột biến mảng tại chỗ, như:

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) 

bạn có thể bind hai chức năng bất tịnh với nhau và gọi cho họ bên trong một hàm thuần túy sử dụng 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 

lưu ý rằng run vẫn tinh khiết, và các phiên bản trước của mảng được trả về không bị rò rỉ ra bất cứ nơi nào:

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