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 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
– luqui, Commented Nov 20, 2015 at 7:27
Clean is a functional language using uniqueness types, also influenced by Haskell. — chi
– chi, Commented Nov 20, 2015 at 8:55
related: 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
– Will Ness, Commented Dec 23, 2019 at 12:56

behzad.nouri · Accepted Answer · 2015-11-20 23:20:58Z

6

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)]

edited Nov 20, 2015 at 23:20

answered Nov 20, 2015 at 13:28

behzad.nouri

78.5k18 gold badges130 silver badges127 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Praxeolitic Over a year ago

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.

behzad.nouri Over a year ago

@Praxeolitic There is no copying; ST monad (in contrast to 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 provide.

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related