Haskell: use last reference to a variable to efficiently create a new variable

Question

This C code can conceptually be described as creating a new array identical to an input array but with 1 as the first element:

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

This is a pure function (wink wink nudge nudge) so long as no further references are made to the input array and its elements. The C type system won't enforce that for us but it seems enforceable in principle.

The code that gcc generates is simple and efficient:

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

Our function achieves the seemingly impossible by creating a whole new array in constant time and using no additional memory. Nice. Can a Haskell function with array-like input and output be written that could be validly implemented with similar code? Is there a way to express "this is the last reference to this variable" so that a pure function can cannibalize the variable behind the scenes?

If the function gets inlined then nothing interesting needs to happen here so let's suppose the caller and function will be compiled separately.

IIUC "uniqueness types", or similarly linear types, do this. Unfortunately these are not a feature of the Haskell type system. The conventional way in Haskell is to use [the `ST` monad](https://hackage.haskell.org/package/base-4.8.1.0/docs/Control-Monad-ST.html) to achieve mutation in a conceptually pure setting (which temporarily enters into a monad with mutable state, but the type system guarantees that the computation is deterministic and the state doesn't leak). It's a very different thing than what you're talking about though. — luqui, Nov 20 '15 at 07:27
[Clean](http://clean.cs.ru.nl/Clean) is a functional language using uniqueness types, also influenced by Haskell. — chi, Nov 20 '15 at 08:55
[related](https://stackoverflow.com/a/9605197/849891): a pure `UArray Int Bool` is being updated in a loop, without any references to its previous value. similar to what you express here, it *could* be updated in-place, but it seems that it isn't. — Will Ness, Dec 23 '19 at 12:56

behzad.nouri · Accepted Answer · 2015-11-20T23:20:58.887

Though ST monad is not exactly what you describe, in practice you may implement most of that using STUArray. So, a mock up of your code may be something like:

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

and if you have another function which mutates the array in-place, like:

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)

you may bind the two impure function together and call them inside a pure function using 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

note that run stays pure, and the earlier versions of the returned array are not leaked out anywhere:

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

It's been a year but this answer just crossed my mind and I wanted to check if I understood it so now I have a question. Why exactly do you say `ST monad` doesn't quite fit the question? Do you just mean the extra typing and conceptual matter of keeping state in a monad? Or is the implementation forced to create a copy somewhere? Thanks. — Praxeolitic, Dec 30 '16 at 18:15
@Praxeolitic There is *no* copying; ST monad (in contrast to [`State Monad`](https://wiki.haskell.org/State_Monad)) does in fact mutate in-place. The point of ST Monad is that mutations become _explicit_ in the type system. But it does not provide guarantees which [`uniqueness type`](https://en.wikipedia.org/wiki/Uniqueness_type) provide. — behzad.nouri, Dec 30 '16 at 20:26

Haskell: use last reference to a variable to efficiently create a new variable

1 Answers1

Linked