Reiner Pope

September 18, 2009

Making runSTArray more flexible; or, making unsafeFreeze safe.

Filed under: Haskell,ST — Reiner Pope @ 4:57 pm

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 signature1:

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.


  1. 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.
About these ads

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Rubric Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: