StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This occurs because the rank-2 type of <code>runST</code> is preventing you from giving a meaningful type to <code>randShuffleST</code>. (There's a second problem with your code as written: mutable ST arrays can't meaningfully exist outside of the <code>ST</code> monad, so returning one from inside <code>runST</code> is impossible, and constructing one to pass into a pure function is unlikely at best. This is "uninteresting," but might end up being confusing on its own; see the bottom of this answer for how to address it.)</p> <p>So, let's see why you can't write down a type signature. It's worth saying up-front that <a href="https://stackoverflow.com/a/12848618/237428">I agree with shachaf</a> about the best way to write functions like the one you're writing: stay inside <code>ST</code>, and use <code>runST</code> only once, at the very end. If you do this, then I've included some sample code at the bottom of the answer which shows how to write your code successfully. But I think it's interesting to understand why you get the error you do; errors like the one you're getting are some of the reasons that you don't want to write your code this way!</p> <p>To begin with, let's first look at a simplified version of the function which produces the same error message:</p> <pre><code>bounds arr = runST (getBounds arr) </code></pre> <p>Now, let's try to give a type to <code>bounds</code>. The obvious choice is</p> <pre><code>bounds :: (MArray a e (ST s), Ix i) => a i e -> (i,i) bounds arr = runST (getBounds arr) </code></pre> <p>We know that <code>arr</code> must be an <code>MArray</code> and we don't care what elements or index type it has (as long as its indices are in <code>Ix</code>), but we know that it must live inside the <code>ST</code> monad. So this should work, right? Not so fast!</p> <pre><code>ghci> :set -XFlexibleContexts +m ghci> :module + Control.Monad.ST Data.Array.ST ghci> let bounds :: (MArray a e (ST s), Ix i) => a i e -> (i,i) ghci| bounds arr = runST (getBounds arr) ghci| <interactive>:8:25: Could not deduce (MArray a e (ST s1)) arising from a use of `getBounds' from the context (MArray a e (ST s), Ix i) bound by the type signature for bounds :: (MArray a e (ST s), Ix i) => a i e -> (i, i) at <interactive>:7:5-38 ... </code></pre> <p>Wait a minute: <code>Could not deduce (MArray a e (ST <em>s1</em>))</code>? Where'd that <code>s1</code> come from‽ We don't mention such a type variable anywhere! The answer is that it's coming from the <code>runST</code> in the definition of <code>bounds</code>. In general, <code>runST</code> has the type (renaming some type variables for convenience) <code>runST :: (forall σ. ST σ α) -> α</code>; when we use it here, we've constrained it to the type <code>(forall σ. ST σ (i,i)) -> (i,i)</code>. What's happening here is that the <code>forall</code> is like a lambda (in fact, it <em>is</em> a lambda), binding <code>σ</code> locally inside the parentheses. So when <code>getBounds arr</code> returns something of type <code>ST s (i,i)</code>, we can unify <code>α</code> with the <code>(i,i)</code>---but we <em>can't</em> unify the <code>σ</code> with the <code>s</code>, because the <code>σ</code> isn't in scope. In GHC, the type variables for <code>runST</code> are <code>s</code> and <code>a</code>, not <code>σ</code> and <code>α</code>, so it renames <code>s</code> to <code>s1</code> to remove ambiguity, and it's <em>this</em> type variable that you're seeing.</p> <p>So the error is fair: we've claimed that for some particular <code>s</code>, <code>MArray a e (ST s)</code> holds. But <code>runST</code> needs that to be true for <em>every</em> <code>s</code>. The error is, however, very unclear, since it introduces a new type variable which you can't actually refer to (so the "possible fix" is meaningless, although it's never helpful anyway).</p> <p>Now, the obvious question is, "So can I write a correct type signature?" The answer is "…sort of." (But you probably don't want to.) The desired type would be something like the following:</p> <pre><code>ghci> :set -XConstraintKinds -XRank2Types ghci> let bounds :: (forall s. MArray a e (ST s), Ix i) => a i e -> (i,i) ghci| bounds arr = runST (getBounds arr) ghci| <interactive>:170:25: Could not deduce (MArray a e (ST s)) arising from a use of `getBounds' from the context (forall s. MArray a e (ST s), Ix i) ... </code></pre> <p>This constraint says that <code>MArray a e (ST s)</code> holds for <em>every</em> <code>s</code>, but we still get a type error. It appears that <a href="http://hackage.haskell.org/trac/ghc/ticket/7019#comment:3" rel="nofollow noreferrer">"GHC does not support polymorphic constraints to the left of an arrow"</a>—and in fact, while googling around trying to find that information, I found <a href="http://mainisusuallyafunction.blogspot.com/2010/09/higher-rank-type-constraints.html" rel="nofollow noreferrer">an excellent blog post at "Main Is Usually A Function"</a>, which runs into the same problem as you, explains the error, and provides the following workaround. (They also get the superior error message "malformed class assertion," which makes clear that such a thing is impossible; this is probably due to differing GHC versions.)</p> <p>The idea is, as is common when we want more out of type class constraints that we can get from GHC's built-in system, to provide explicit evidence for the existence of such a type class by (ab)using a GADT:</p> <pre><code>ghci> :set -XNoFlexibleContexts -XNoConstraintKinds ghci> -- We still need -XRank2Types, though ghci> :set -XGADTs ghci> data MArrayE a e m where ghci| MArrayE :: MArray a e m => MArrayE a e m ghci| ghci> </code></pre> <p>Now, whenever we have a value of type <code>MArrayE a e m</code>, we know that the value must have been constructed with the <code>MArrayE</code> constructor; this constructor can only be called when there's an <code>MArray a e m</code> constraint available, and so pattern-matching on <code>MArrayE</code> will make that constraint available again. (The only other possibility is that your value of that type was undefined, which is why a pattern match is in fact necessary.) Now, we can provide that as an explicit argument to the <code>bounds</code> function, so we'd call it as <code>bounds MArrayE arr</code>:</p> <pre><code>ghci> :set -XScopedTypeVariables ghci> let bounds :: forall a e i. ghci| Ix i => (forall s. MArrayE a e (ST s)) -> a i e -> (i,i) ghci| bounds evidence arr = runST (go evidence) ghci| where go :: MArrayE a e (ST s) -> ST s (i,i) ghci| go MArrayE = getBounds arr ghci| ghci> -- Hooray! </code></pre> <p>Note the weirdness where we have to factor out the body into its own function and pattern-match there. What's going on is that if you pattern-match in <code>bounds</code>'s argument list, the <code>s</code> from the <code>evidence</code> gets fixed to a particular value too early, and so we need to put this off; and (I think because inference with higher-rank types is hard) we also need to provide an explicit type for <code>go</code>, which necessitates scoped type variables.</p> <p>And finally, returning to your original code:</p> <pre><code>ghci> let randShuffleST :: forall a e i g. Ix i => (forall s. MArrayE a e (ST s)) ghci| -> a i e ghci| -> g ghci| -> (a i e, g) ghci| randShuffleST evidence arr gen = runST $ go evidence ghci| where go :: MArrayE a e (ST s) -> ST s (a i e,g) ghci| go MArrayE = do _ <- getBounds arr ghci| return (arr, gen) ghci| ghci> -- Hooray again! But... </code></pre> <hr> <p>Now, as I said at the beginning, there's one problem left to address. In the code above, there's never going to be a way to construct a value of type <code>forall s. MArrayE a e (ST s)</code>, because the contraint <code>forall s. MArray a e (ST s)</code> constraint is unsatisfiable. For the same reason, in your original code, you couldn't write <code>randShuffleST</code> even without the type error you're getting, because you can't write a function which returns an <code>STArray</code> outside of <code>ST</code>.</p> <p>The reason for both of these problems is the same: <a href="http://hackage.haskell.org/packages/archive/array/latest/doc/html/Data-Array-ST.html#t:STArray" rel="nofollow noreferrer">an <code>STArray</code>'s first parameter is the state thread it lives on</a>. The <code>MArray</code> instance for <code>STArray</code> is <code>instance MArray (STArray s) e (ST s)</code>, and so you'll always have types of the form <code>ST s (STArray s i e)</code>. Since <code>runST :: (forall s. ST s a) -> a</code>, running <code>runST mySTArrayAction</code> would "leak" the <code>s</code> out in an illegal way. Look into</p> <p><a href="http://hackage.haskell.org/packages/archive/array/latest/doc/html/Data-Array-ST.html#v:runSTArray" rel="nofollow noreferrer"><code>runSTArray :: Ix i => (forall s. ST s (STArray s i e)) -> Array i e</code></a></p> <p>and its unboxed friend</p> <p><a href="http://hackage.haskell.org/packages/archive/array/latest/doc/html/Data-Array-ST.html#v:runSTUArray" rel="nofollow noreferrer"><code>runSTUArray :: Ix i => (forall s. ST s (STUArray s i e)) -> UArray i e</code></a>.</p> <p>You can also use</p> <p><a href="http://hackage.haskell.org/packages/archive/array/latest/doc/html/Data-Array-MArray.html#v:unsafeFreeze" rel="nofollow noreferrer"><code>unsafeFreeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e)</code></a></p> <p>to do the same thing, as long as you promise that that's the last function you'll ever call on your mutable array; the <a href="http://hackage.haskell.org/packages/archive/array/latest/doc/html/Data-Array-MArray.html#v:freeze" rel="nofollow noreferrer"><code>freeze</code></a> function relaxes this restriction, but has to copy the array. By the same token, if you want to pass an array, and not a list, into the pure version of your function, you'll probably also want</p> <p><a href="http://hackage.haskell.org/packages/archive/array/latest/doc/html/Data-Array-MArray.html#v:thaw" rel="nofollow noreferrer"><code>thaw :: (Ix i, IArray a e, MArray b e m) => a i e -> m (b i e)</code></a>;</p> <p>using <a href="http://hackage.haskell.org/packages/archive/array/latest/doc/html/Data-Array-MArray.html#v:unsafeThaw" rel="nofollow noreferrer"><code>unsafeThaw</code></a> would probably be disastrous here, since you're passing in an immutable array that you have no control over! This would all combine to give us something like:</p> <pre><code>ghci> :set -XNoRank2Types -XNoGADTs ghci> -- We still need -XScopedTypeVariables for our use of `thaw` ghci> import Data.Array.IArray ghci> let randShuffleST :: forall ia i e g. (Ix i, IArray ia e) ghci| => ia i e ghci| -> g ghci| -> (Array i e, g) ghci| randShuffleST iarr gen = runST $ do ghci| marr <- thaw iarr :: ST s (STArray s i e) ghci| _ <- getBounds marr ghci| iarr' <- unsafeFreeze marr ghci| return (iarr', gen) ghci| ghci> randShuffleST (listArray (0,2) "abc" :: Array Int Char) "gen" (array (0,2) [(0,'a'),(1,'b'),(2,'c')],"gen") </code></pre> <p>This takes <em>O</em>(<em>n</em>) time to copy the input immutable array, but—with optimizations—takes <em>O</em>(1) time to freeze the mutable array for the output, since <code>STArray</code> and <code>Array</code> are the same under the hood.</p> <p>Applying this to your problem in particular, we have the following:</p> <pre><code>{-# LANGUAGE FlexibleContexts #-} import System.Random import Control.Monad import Control.Applicative import Control.Monad.ST import Data.Array.ST import Data.STRef import Data.Array.IArray updateSTRef :: STRef s a -> (a -> (b,a)) -> ST s b updateSTRef r f = do (b,a) <- f <$> readSTRef r writeSTRef r a return b swapArray :: (MArray a e m, Ix i) => a i e -> i -> i -> m () swapArray arr i j = do temp <- readArray arr i writeArray arr i =<< readArray arr j writeArray arr j temp shuffle :: (MArray a e (ST s), Ix i, Random i, RandomGen g) => a i e -> g -> ST s g shuffle arr gen = do rand <- newSTRef gen bounds@(low,_) <- getBounds arr when (rangeSize bounds > 1) . forM_ (reverse . tail $ range bounds) $ \i -> swapArray arr i =<< updateSTRef rand (randomR (low,i)) readSTRef rand -- Two different pure wrappers -- We need to specify a specific type, so that GHC knows *which* mutable array -- to work with. This replaces our use of ScopedTypeVariables. thawToSTArray :: (Ix i, IArray a e) => a i e -> ST s (STArray s i e) thawToSTArray = thaw shufflePure :: (IArray a e, Ix i, Random i, RandomGen g) => a i e -> g -> (a i e, g) shufflePure iarr g = runST $ do marr <- thawToSTArray iarr g' <- shuffle marr g iarr' <- freeze marr return (iarr',g') shufflePure' :: (IArray a e, Ix i, Random i, RandomGen g) => a i e -> g -> (Array i e, g) shufflePure' iarr g = let (g',g'') = split g iarr' = runSTArray $ do marr <- thaw iarr -- `runSTArray` fixes the type of `thaw` void $ shuffle marr g' return marr in (iarr',g'') </code></pre> <p>Again, you could replace freeze with <code>Data.Array.Unsafe.unsafeFreeze</code> in <code>shufflePure</code>; this would probably produce a speedup, since it wouldn't have to copy the array to return it if it was an <code>Array i e</code>. The <code>runSTArray</code> function wraps <code>unsafeFreeze</code> safely, so that's not an issue in <code>shufflePure'</code>. (The two are equivalent, modulo some details about splitting the PRNG.)</p> <p>What do we see here? Importantly, only the mutable code ever references the mutable arrays, and it stays mutable (<em>i.e.</em>, returns something inside <code>ST s</code>). Since <code>shuffle</code> does an in-place shuffle, it doesn't need to return an array, just the PRNG. To build a pure interface, we <code>thaw</code> an immutable array into a mutable array, shuffle <em>that</em> in-place, and then <code>freeze</code> the resulting array back into an immutable one. This is important: it prevents us from leaking mutable data back into the pure world. You can't directly mutably shuffle the passed-in array, because it's is immutable; contrariwise, you can't directly return the mutably shuffled array as an immutable array, because it's mutable, and what if someone could mutate it?</p> <p>This doesn't run afoul of any of the errors we saw above, because all of those errors come from improper use of <code>runST</code>. If we restrict our use of <code>runST</code>, only running it once we've assembled a pure result, all the inner state-threading can happen automatically. Since <code>runST</code> is the only function with a rank-2 type, it's the only place where severe type-weirdness can be produced; everything else just requires your standard type-based reasoning, albeit perhaps with a little more thought to keep the <code>s</code> state-thread parameter consistent.</p> <p>And lo and behold:</p> <pre><code>*Main> let arr10 = listArray (0,9) [0..9] :: Array Int Int *Main> elems arr10 [0,1,2,3,4,5,6,7,8,9] *Main> elems . fst . shufflePure arr10 <$> newStdGen [3,9,0,5,1,2,8,7,6,4] *Main> elems . fst . shufflePure arr10 <$> newStdGen [3,1,0,5,9,8,4,7,6,2] *Main> elems . fst . shufflePure' arr10 <$> newStdGen [3,9,2,6,8,4,5,0,7,1] *Main> elems . fst . shufflePure' arr10 <$> newStdGen [8,5,2,1,9,4,3,0,7,6] </code></pre> <p>Success, at long last! (Way too long last, really. Sorry about the length of this answer.)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload