Haskell: stosować ostatni odnosi się do zmiennej efektywnego tworzenia nowego kodu o zmiennej

Question

ten C koncepcyjnie można opisać jako tworzenie nowej tablicy identyczną tablicy wejść, z 1 jako pierwszy element:

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

tę jest czystą funkcją (mrugnięcie wink nucić) tak długo, jak nie ma dalszych odniesień do tablicy wejściowej i jej elementów. System typu C nie wymusi tego dla nas, ale z zasady wydaje się być wykonalny.

Kod, który generuje gcc jest prosty i skuteczny:

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

Nasza funkcja osiąga pozornie niemożliwe, tworząc zupełnie nową tablicę w stałym czasie i przy użyciu dodatkowej pamięci. Miły. Czy można napisać funkcję Haskella z tablicowymi danymi wejściowymi i wyjściowymi, które mogą być poprawnie implementowane za pomocą podobnego kodu? Czy istnieje sposób na wyrażenie "to jest ostatnie odniesienie do tej zmiennej", aby czysta funkcja mogła kanibalizować zmienną za kulisami?

Jeśli funkcja zostanie wstawiona, wtedy nic ciekawego się nie stanie, więc załóżmy, że wywołujący i funkcja będą kompilowane osobno.

Answer 1

Chociaż ST monad jest nie dokładnie to, co opisują, w praktyce można wdrożyć większość tego przy użyciu STUArray. Tak, makiety z kodem może być coś takiego:

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 

a jeśli masz inną funkcję, która mutuje tablicę w miejscu, jak:

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) 

możesz wiążą dwa funkcja razem nieczyste i nazywają je wewnątrz czystego funkcji użyciu 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 

nuta że run pozostaje czysta, a wcześniejsze wersje zwróconej tablicy nie wyciekła nigdzie:

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