Re: [Haskell] How to use STArray?
On Tuesday 30 August 2005 06:32, [EMAIL PROTECTED] 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
___
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] How to use STArray?
On Tuesday 30 August 2005 06:32, [EMAIL PROTECTED] 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 Ups, I have missed this one. Next time I'll do a list search first. 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. It would havebeen nice if the GHC library supported the second solution, a class Unpackable. Currently there are instances of MArray (STUArray s) e (ST s) and IArray UArray e for exactly the same set of types `e'. Alas, that condition is not stated formally, so we cannot infer that MArray (STUArray s) e (ST s) holds whenever IArray UArray e does. Any chance that the standard libraries will be changed along these lines? [snip complete solution] I almost suspected that I have to introduce some existentially quantified data type, but had no idea where and how. This would make a useful wiki page, BTW. Thanks a lot for the help. Ben ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell] How to use STArray?
Hmmm, no answer on cafe, maybe someone here with a good idea? -- Forwarded Message -- 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 ) Hello, I am fighting with a similar problem. I want to use STUArray but without committing to a fixed element type. For instance (this is not my real problem, but it's similar and easier to motivate), here is a function that appends two UArrays: A little helper first 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) and here is the append function append :: UArray Int e - UArray Int e - Int - UArray Int e append x y low = runSTUArray (do z - newArray_ (low,low+len x+len y) 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 Of course this can't work, because 'copy' needs the MArray and IArray contexts: No instance for (MArray (STUArray s) e (ST s)) arising from use of `copy' at Problem.lhs:31:7-10 [...] No instance for (IArray UArray e) arising from use of `copy' at Problem.lhs:31:7-10 [...] But now, when I add append :: (IArray UArray e, MArray (STUArray s) e (ST s)) = ... I still get the same error message regarding the MArray constraint: No instance for (MArray (STUArray s) e (ST s)) arising from use of `copy' at Problem.lhs:31:7-10 What am I missing? That is, how and where do I have to specify the constraint? Ben ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell] How to use STArray?
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.
It would havebeen nice if the GHC library supported the second
solution, a class Unpackable. Currently there are instances of
MArray (STUArray s) e (ST s)
and
IArray UArray e
for exactly the same set of types `e'. Alas, that condition is not
stated formally, so we cannot infer that MArray (STUArray s) e (ST s)
holds whenever IArray UArray e does.
{-# OPTIONS -fglasgow-exts #-}
module Foo where
import Data.Array.Unboxed
import Data.Array.ST
import Control.Monad.ST
data Allocator m i e = forall a. MArray a e m =
Allocator ((i, i) - m (a i e))
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 UArray e, STUGood e) =
UArray Int e - UArray Int e - Int - UArray Int e
append x y low =
runST (case allcg of Allocator newArray_ -
(do
z - newArray_ (low,low+len x+len y)
copy z low x (first x) (len x)
copy z (low+len x) y (first y) (len y)
unsafeFreeze z))
where
len = rangeSize . bounds
first = fst . bounds
class STUGood e where
allcg::Ix i = Allocator (ST s) i e
instance STUGood Bool where
allcg = Allocator (newArray_:: Ix i = (i,i) - ST s (STUArray s i Bool))
instance STUGood Float where
allcg = Allocator (newArray_:: Ix i = (i,i)- ST s (STUArray s i Float))
-- etc.
test =
append (listArray (1,1) [True]) (listArray (1,1) [False]) 0
___
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell
