[Haskell] How to use STArray?

[Benjamin Franksen]

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
> > > the overloading of newArray and readArray, which is surprisingly
> > > 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
> 	http://www.haskell.org/pipermail/haskell-cafe/2004-July/006400.html
> 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
import Control.Monad.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