# [Haskell] How to use STArray?

Benjamin Franksen benjamin.franksen at bessy.de
Wed Aug 31 19:04:21 EDT 2005

On Tuesday 30 August 2005 06:32, oleg at pobox.com wrote:
> Benjamin Franksen wrote:
> > On Thursday 25 August 2005 19:58, Udo Stenzel wrote:
> > > [...] you'll need a type signature somewhere to help ghc resolve
> > > tricky due to the "s" that must not escape.  This works:
> > >
> > > compute :: Int -> Int
> > > compute n = runST ( do
> > >     arr <- newArray (-1, 1) n :: ST s (STArray s Int Int)
> > >     readArray arr 1
> > >   )
> >
> > I am fighting with a similar problem. I want to use STUArray but
> > without committing to a fixed element type.
>
> That problem has been addressed in a message
> which discussed several solutions. Given below is one of the
> solutions adjusted to fit the question of the original poster. His
> code is almost unchanged.

Gosh, it took me a while before I really understood /why/ your solution
works, but now I think I got it.

The central idea is to use an intermediate data type that has the proper
constraint on its element(s). Existential quantification is not
strictly necessary: if we wrap runSTUArray instead of newArray_ we
merely need a rank-2 type. This also strikes me as the more direct
aproach and has the additional advantage that we don't have to use
unsafeFreeze.

Below is the code of the modified solution. Note that there are no type
signatures in the instances for class UArrayElement.

\begin{code}
{-# OPTIONS -fglasgow-exts #-}
import Data.Array.Unboxed
import Data.Array.ST

copy :: (MArray a e m, IArray b e) =>
a Int e -> Int -> b Int e -> Int -> Int -> m ()
copy dest destix src srcix cnt
| cnt <= 0  = return ()
| otherwise = do
writeArray dest destix (src ! srcix)
copy dest (destix+1) src (srcix+1) (cnt-1)

append :: (IArray a e, UArrayElement e) =>
a Int e -> a Int e -> Int -> UArray Int e
append x y low =
case freezer of
Freezer f -> f (do
z <-  newArray_ (low,low+len x+len y-1)
copy z low x (first x) (len x)
copy z (low+len x) y (first y) (len y)
return z)
where
len = rangeSize . bounds
first = fst . bounds

data Freezer i e = Freezer
((forall s. MArray (STUArray s) e (ST s) => ST s (STUArray s i e))
-> UArray i e)

class UArrayElement e where
freezer :: Ix i => Freezer i e

instance UArrayElement Bool where
freezer = Freezer runSTUArray

instance UArrayElement Char where
freezer = Freezer runSTUArray

-- ...
\end{code}

Ben