Haskell: letzte Referenz auf eine Variable verwenden, um effizient eine neue Variable

Question

Dieser C-Code zu erzeugen kann konzeptionell als die Schaffung eines neuen Array identisch ist mit einer Eingangsanordnung beschrieben, aber mit 1 als dem ersten Element:

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

Diese ist eine reine Funktion (Wink Wink Nudge Nudge), solange keine weiteren Verweise auf das Eingangsarray und seine Elemente gemacht werden. Das C-System wird das für uns nicht durchsetzen, aber es scheint im Prinzip durchsetzbar zu sein.

Der Code, dass gcc erzeugt ist einfach und effizient:

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

Unsere Funktion erreicht, das scheinbar Unmögliche durch eine ganz neue Array in konstanter Zeit und mit keinem zusätzlichen Speicher zu schaffen. Nett. Kann eine Haskell-Funktion mit Array-ähnlichen Ein- und Ausgaben geschrieben werden, die mit ähnlichem Code gültig implementiert werden könnten? Gibt es eine Möglichkeit, "das ist die letzte Referenz auf diese Variable" auszudrücken, so dass eine reine Funktion die Variable hinter den Kulissen kannibalisieren kann?

Wenn die Funktion inline wird, dann muss hier nichts Interessantes passieren. Nehmen wir an, der Aufrufer und die Funktion werden separat kompiliert.

Answer 1

Obwohl ST monad ist nicht genau das, was Sie beschreiben, in der Praxis können Sie die meisten, dass STUArray mit implementieren. So kann ein Mock-up von Ihrem Code so etwas wie:

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 

und wenn Sie eine andere Funktion, die die Anordnung an Ort und Stelle mutiert, wie:

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) 

Sie können binden die beiden unreine Funktion zusammen und nennen sie in einer reinen Funktion mit 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 

beachten Sie, dass run rein bleibt, und die früheren Versionen des zurückgegebenen Arrays sind überall nicht durchgesickert:

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