Haskell: utilizzare ultimo riferimento a una variabile per creare efficacemente un nuovo codice

Question

Questo C variabile può concettualmente essere descritto come la creazione di un nuovo array identico a un array di input ma con 1 come primo elemento:

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

Questo è una funzione pura (wink wink nudge nudge) purché non vengano fatti ulteriori riferimenti all'array di input e ai suoi elementi. Il sistema di tipo C non imporrà questo per noi, ma sembra in linea di principio applicabile.

Il codice che genera gcc è semplice ed efficace:

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

nostra funzione realizza l'apparentemente impossibile creando una nuova matrice in tempo costante e senza usare memoria aggiuntiva. Bello. È possibile scrivere una funzione Haskell con input e output di tipo array che possa essere validamente implementata con un codice simile? C'è un modo per esprimere "questo è l'ultimo riferimento a questa variabile" in modo che una pura funzione possa cannibalizzare la variabile dietro le quinte?

Se la funzione viene evidenziata, non è necessario che avvenga qualcosa di interessante, quindi supponiamo che il chiamante e la funzione vengano compilati separatamente.

Answer 1

Anche se ST monad è non esattamente ciò che si descrive, in pratica, è possibile implementare la maggior parte di che l'utilizzo STUArray. Così, un mock up del codice può essere qualcosa come:

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 

e se si dispone di un'altra funzione, che muta la matrice sul posto, come:

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) 

si può legano i due impura funzione insieme e li chiamano all'interno di una pura funzione utilizzando 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 

nota che run rimane pura, e le versioni precedenti di matrice restituita non sono trapelate da nessuna parte:

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