Trouble with the ST monad
Hello, I'm trying to write a function that would take an STArray and and shuffle its elements. I'm having trouble with the ST monad, though, and couldn't find out how fix this issue. The problem happens when I use runST to extract the shuffled array from the ST monad. I'm getting the following error: Inferred type is less polymorphic than expected Quantified type variable `s' is mentioned in the environment: a :: STArray s Int a The full code is at http://hpaste.org/13240#a1 Any help would be appreciated. Thanks, Andre
The problem is that you are trying to return a mutable array out of an ST computation. This lets the "mutability" of the computation escape. That's what the "s" type variable is for; without it, runST is just unsafePerformIO. To solve your problem, you need to eliminate any references to the state from the output of runST. I suggest looking into the function "freezeSTArray":
From http://haskell.org/ghc/docs/latest/html/libraries/base/GHC-Arr.html#v:freeze... freezeSTArray :: Ix i => STArray s i e -> ST s (Array i e)
(See my annotation at http://hpaste.org/13240#a2)
This allows you to remove any reference to the state from the array
computation. Alternatively, if you want this to be part of a larger
mutable computation, you can return the result in ST; this is what the
version of shuffle you have in the paste does.
-- ryan
On Sun, Dec 21, 2008 at 4:14 PM, Andre Nathan
Hello,
I'm trying to write a function that would take an STArray and and shuffle its elements. I'm having trouble with the ST monad, though, and couldn't find out how fix this issue.
The problem happens when I use runST to extract the shuffled array from the ST monad. I'm getting the following error:
Inferred type is less polymorphic than expected Quantified type variable `s' is mentioned in the environment: a :: STArray s Int a
The full code is at
Any help would be appreciated.
Thanks, Andre
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Sun, 2008-12-21 at 16:47 -0800, Ryan Ingram wrote:
The problem is that you are trying to return a mutable array out of an ST computation. This lets the "mutability" of the computation escape. That's what the "s" type variable is for; without it, runST is just unsafePerformIO.
Thanks! If only I knew that was the problem... It wouldn't have costed me the whole afternoon :P Is there any difference between using freeze/thaw from Data.Array.MArray versus freezeSTArray/thawSTArray from GHC.Arr? Best, Andre
Hello Andre, Monday, December 22, 2008, 4:44:34 AM, you wrote:
Is there any difference between using freeze/thaw from Data.Array.MArray versus freezeSTArray/thawSTArray from GHC.Arr?
portability, at least -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
On Sun, 2008-12-21 at 16:47 -0800, Ryan Ingram wrote:
The problem is that you are trying to return a mutable array out of an ST computation. This lets the "mutability" of the computation escape. That's what the "s" type variable is for; without it, runST is just unsafePerformIO.
I'm trying something similar now... I have defined a data type for mutable matrices as data STMatrix s a = STMatrix { elements :: Array Int (STArray s Int a) , nrows :: Int , ncols :: Int } and one for immutable matrices: data Matrix a = Matrix { elements :: Array Int (Array int a) , nrows :: Int , ncols :: Int } What I wanted was a way to freeze an STMatrix into a Matrix so that I could work with it out of the ST monad after doing all of the modifications I need on the elements. I came up with the following: doFreeze :: STMatrix s a -> ST s (Matrix a) doFreeze mat = do let m = nrows mat n = ncols mat rows <- foldM (freezeRow mat) [] [m-1,m-2..0] return $ listMatrix (m, n) rows where freezeRow mat rs i = do r <- unsafeFreeze (elements mat ! i) return (r:rs) where "listMatrix" builds a Matrix from a list of Arrays. However, when I this: freezeMatrix = runST . doFreeze I get the "less polymorphic than expected" error from ghc. I fail to see why though. Since "freezeRow" returns a list of immutable Arrays, where is the mutability of the computation escaping here? Thanks in advance, Andre
(I'm kinda a newbie, take my explanation with a grain of salt:) The problem is that you're trying to take a STMatrix from some other ST computation and freeze it in a new ST computation. The isolation between separate computations is done via the rank-2 type variable "s" in all those ST functions. Instead of this: freezeMatrix :: forall s. STMatrix s a -> Matrix a freezeMatrix = runST . freezeMatrix -- does not unify runST :: (forall s. ST s a) -> a Which is trying to unify the type variable "s" from the STMatrix you pass in with the explicitly polymorphic "s" in runST -- Note the parentheses -- these are different "s"s and cannot be unified Try this: freezeMatrix :: (forall s . STMatrix s a) -> Matrix a freezeMatrix f :: runST (freezeMatrix f) Also, instead of using an array of arrays, maybe an array with (Int, Int) as the Ix might be a bit smoother? -Ross Here is a working version: {-# LANGUAGE Rank2Types #-} import Control.Monad import Control.Monad.ST import Data.Array import Data.Array.ST data STMatrix s a = STMatrix { stm_elements :: Array Int (STArray s Int a) , stm_nrows :: Int , stm_ncols :: Int } data Matrix a = Matrix { m_elements :: Array Int (Array Int a) , m_nrows :: Int , m_ncols :: Int } listMatrix :: (Int, Int) -> [Array Int a] -> Matrix a listMatrix (n,m) rs = Matrix { m_elements = listArray (0, length rs - 1) rs , m_nrows = m , m_ncols = n } doFreeze :: STMatrix s a -> ST s (Matrix a) doFreeze mat = do let m = stm_nrows mat n = stm_ncols mat rows <- foldM (freezeRow mat) [] [m-1,m-2..0] return $ listMatrix (m, n) rows where freezeRow mat rs i = do r <- unsafeFreeze (stm_elements mat ! i) return (r:rs) freezeMatrix :: (forall s. STMatrix s a) -> Matrix a freezeMatrix f = runST (doFreeze f) On Dec 29, 2008, at 1:57 PM, Andre Nathan wrote:
On Sun, 2008-12-21 at 16:47 -0800, Ryan Ingram wrote:
The problem is that you are trying to return a mutable array out of an ST computation. This lets the "mutability" of the computation escape. That's what the "s" type variable is for; without it, runST is just unsafePerformIO.
I'm trying something similar now... I have defined a data type for mutable matrices as
data STMatrix s a = STMatrix { elements :: Array Int (STArray s Int a) , nrows :: Int , ncols :: Int }
and one for immutable matrices:
data Matrix a = Matrix { elements :: Array Int (Array int a) , nrows :: Int , ncols :: Int }
What I wanted was a way to freeze an STMatrix into a Matrix so that I could work with it out of the ST monad after doing all of the modifications I need on the elements.
I came up with the following:
doFreeze :: STMatrix s a -> ST s (Matrix a) doFreeze mat = do let m = nrows mat n = ncols mat rows <- foldM (freezeRow mat) [] [m-1,m-2..0] return $ listMatrix (m, n) rows where freezeRow mat rs i = do r <- unsafeFreeze (elements mat ! i) return (r:rs)
where "listMatrix" builds a Matrix from a list of Arrays.
However, when I this:
freezeMatrix = runST . doFreeze
I get the "less polymorphic than expected" error from ghc. I fail to see why though. Since "freezeRow" returns a list of immutable Arrays, where is the mutability of the computation escaping here?
Thanks in advance, Andre
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Mon, 2008-12-29 at 14:19 -0500, Ross Mellgren wrote:
The problem is that you're trying to take a STMatrix from some other ST computation and freeze it in a new ST computation. The isolation between separate computations is done via the rank-2 type variable "s" in all those ST functions.
I guess I should go and read the rank-n types page on the wiki...
Try this:
freezeMatrix :: (forall s . STMatrix s a) -> Matrix a freezeMatrix f :: runST (freezeMatrix f)
Do you know why point-free style doesn't work here even with the type annotation?
Also, instead of using an array of arrays, maybe an array with (Int, Int) as the Ix might be a bit smoother?
Thanks for the suggestion. It didn't occur to me that there was an Ix instance for that. Best, Andre
On Dec 29, 2008, at 3:43 PM, Andre Nathan wrote:
On Mon, 2008-12-29 at 14:19 -0500, Ross Mellgren wrote:
The problem is that you're trying to take a STMatrix from some other ST computation and freeze it in a new ST computation. The isolation between separate computations is done via the rank-2 type variable "s" in all those ST functions.
I guess I should go and read the rank-n types page on the wiki...
Try this:
freezeMatrix :: (forall s . STMatrix s a) -> Matrix a freezeMatrix f :: runST (freezeMatrix f)
Do you know why point-free style doesn't work here even with the type annotation?
I'm not very good with all the type-theoretic principles involved, but I think it's because higher ranked types cannot unify with lower ranked ones. I'm sure some of the more wizardly types could explain this with an example of how doing it like that would make something that should be illegal possible and the actual principles involved. (That's longhand for "it makes a kind of intuitive sense to me but I can't explain it")
Also, instead of using an array of arrays, maybe an array with (Int, Int) as the Ix might be a bit smoother?
Thanks for the suggestion. It didn't occur to me that there was an Ix instance for that.
Best, Andre
-Ross
participants (4)
-
Andre Nathan -
Bulat Ziganshin -
Ross Mellgren -
Ryan Ingram