The code for this article is available on Hackage.

Suppose I have an algorithm which imperatively builds two result arrays, and once I have built the result arrays, they will remain constant while I continue to read from them. I need to use a monad for the imperative part, but once I have finished that part, I will want to use the arrays as pure (immutable) arrays so that I don’t need to carry the monad around. I want my code to be efficient, so I won’t tolerate copying the data of the arrays: a mutable array and its corresponding immutable array must refer to the same data.

I don’t know how to do this with current array/ST libraries without using an “unsafe” function like `unsafeFreeze`

. The difficulty comes from needing more than one result arrays: if we only needed one, we could use `runSTArray`

, which has the following type signature^{1}:

```
runSTArray :: (forall s. ST s (STArray s a)) -> Array a
```

We can see the problem in this type signature: each time we run the `ST`

monad, we can only produce one array. I have found one way to address this problem. The main idea is to split the ST monad into two distinct stages: the “normal” stage, which is followed by the “freezing” stage. Reading and writing are permitted in the normal stage, and reading and freezing are permitted in the the freezing stage. This policy ensures that, once we have access to the immutable array, no further writing is permitted. Note that constructing a new array is safe in either stage, but rather pointless in the freezing stage as the array cannot be written to. I rewrite `ST`

as an indexed monad (from category-extras) to enforce the sequencing of the freezing stage after the normal stage:

>{-# LANGUAGE EmptyDataDecls, Rank2Types #-}> import Control.Monad.Indexed > > data ST s t a-- = ... -- exported abstract> instance IxFunctor ST > instance IxPointed ST > instance IxApplicative ST > instance IxMonad ST

> data STArray s a-- = ...> data Array a-- = ...

I make two empty types to label the stages with:

> data Normal s > data Freezing s

We have construction, read, write, and freeze operations, each of which encode which stages they may be performed in:

> newArray :: Int -> a -> ST (Normal s) (Normal s) (STArray s a) > readArray :: STArray s a -> Int -> ST (stg s) (stg s) a > writeArray :: STArray s a -> Int -> a -> ST (Normal s) (Normal s) () > freezeArray :: STArray s a -> ST (Freezing s) (Freezing s) (Array a)

The `readArray`

is polymorphic in the stage, as it can be performed in either stage.

The following operation transitions from the first to the second phase:

```
> beginFreezeStage :: ST (Normal s) (Freezing s) ()
```

Operationally, this is a no-op.

Finally, we have the new `runST`

, which accepts `ST`

operations starting and ending in either stage:

> runST :: (forall s. ST (stg1 s) (stg2 s) a) -> a

Using this interface, we can freeze both arrays safely in our initial problem, although this library would internally use `unsafeFreezeArray`

:

> runAlgorithm :: ST (Normal s) (Freezing s) (Array Double, Array Double) > runAlgorithm = > newArray 10 (0 :: Double) >>>= \a -> > newArray 20 (0 :: Double) >>>= \b -> > writeArray a 5 3 >>>= \_ -> > readArray b 4 >>>= \_val-> >-- and do some more stuff with the array> beginFreezeStage >>>= \_ -> > freezeArray a >>>= \fa -> > freezeArray b >>>= \fb -> > ireturn (fa,fb)

Edit: I realise now that the `beginFreezeStage`

operator isn’t necessary; by a small modification of the types, we can make the freeze stage start when some form of `freeze`

is first called. This change is implemented in the Hackage package.

- I am using the types in
`Data.Array.ST`

but I’ve dropped the`Ix`

parameters as they have no significance to this discussion. The parameter type also has no significance, but`Array`

standing by itself as a type looks too odd to my eyes, so I keep that. ↩

## Leave a Reply