これは、のランク2タイプがrunST、に意味のあるタイプを与えることを妨げているために発生しrandShuffleSTます。（記述されたコードには2番目の問題があります。可変ST配列はSTモナドの外側に意味のある形で存在できないため、内側から戻すrunSTことは不可能であり、純粋関数に渡すために配列を作成することはほとんどありません。これは「面白くない」です。 、」しかし、それ自体で混乱する可能性があります。対処方法については、この回答の下部を参照してください。）
それでは、型署名を書き留められない理由を見てみましょう。あなたが書いているような関数を書くための最良の方法について、私がshachafに同意することを前もって言う価値があります：内部STにとどまり、最後に一度だけ使用しますrunST。これを行う場合は、回答の下部に、コードを正常に作成する方法を示すサンプルコードをいくつか含めました。しかし、なぜエラーが発生するのかを理解するのは興味深いことだと思います。あなたが得ているようなエラーはあなたがこのようにあなたのコードを書きたくない理由のいくつかです！
まず、同じエラーメッセージを生成する関数の簡略化されたバージョンを見てみましょう。
bounds arr = runST (getBounds arr)
それでは、に型を付けてみましょうbounds。明らかな選択は
bounds :: (MArray a e (ST s), Ix i) => a i e -> (i,i)
bounds arr = runST (getBounds arr)
それはであるarr必要があり、MArrayどの要素またはインデックスタイプを持っているかは関係ありません（インデックスがにある限り）が、モナドIx内に存在する必要があることはわかっています。STだからこれはうまくいくはずですよね？そんなに早くない！
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
...
ちょっと待って：？それはどこから来たのか‽そのような型変数についてはどこにも言及していません！答えは、の定義から来ているということです。一般に、型があります（便宜上、いくつかの型変数の名前を変更します）。ここで使用するときは、タイプに制限しています。ここで起こっていることは、がラムダのようなものであり（実際にはラムダです）、括弧内でローカルにバインドされているということです。したがって、タイプの何かを返す場合、---と統合できますが、スコープ内にないため、と統合することはできません。GHCでは、Could not deduce (MArray a e (ST s1))s1runSTboundsrunSTrunST :: (forall σ. ST σ α) -> α(forall σ. ST σ (i,i)) -> (i,i)forallσgetBounds arrST s (i,i)α(i,i)σsσrunSTでsありa、ではなくσ、であるため、あいまいさを取り除くαために名前が変更sされます。表示されているのはこの型変数です。s1
sしたがって、エラーは公正です。特定の、MArray a e (ST s)が成り立つと主張しました。しかし、それがすべてrunSTに当てはまる必要があります。ただし、実際には参照できない新しい型変数が導入されるため、エラーは非常に不明確です（したがって、「可能な修正」は意味がありませんが、とにかく役に立ちません）。 s
さて、明らかな質問は、「では、正しい型署名を書くことができるか」ということです。答えは「…ある種」です。（しかし、おそらくあなたはしたくないでしょう。）望ましいタイプは次のようなものです：
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)
...
この制約は、すべてMArray a e (ST s)のに当てはまると言っていますが、それでも型エラーが発生します。「GHCは矢印の左側の多形制約をサポートしていない」ようです。実際、その情報を探し回っているときに、「メインは通常は関数」という優れたブログ投稿を見つけました。あなたと同じ問題で、エラーを説明し、次の回避策を提供します。（また、優れたエラーメッセージ「不正なクラスのアサーション」が表示されます。これは、そのようなことは不可能であることを示しています。これは、GHCのバージョンが異なることが原因である可能性があります。） s
この考え方は、GHCの組み込みシステムから取得できる型クラスの制約をさらに活用したい場合によくあることですが、GADTを（ab）使用することでそのような型クラスの存在の明示的な証拠を提供することです。
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>
これで、タイプの値があるときはいつでも、MArrayE a e mその値はコンストラクターで構築されている必要があることがわかりMArrayEます。このコンストラクターは、使用可能な制約がある場合にのみ呼び出すことができるMArray a e mため、パターンマッチングをオンMArrayEにすると、その制約が再び使用可能になります。（他の唯一の可能性は、その型の値が未定義であったことです。そのため、実際にはパターンマッチが必要です。）これで、bounds関数への明示的な引数としてそれを提供できるので、次のように呼び出しますbounds MArrayE arr。
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!
体をそれ自身の機能に分解し、そこでパターンマッチしなければならないという奇妙さに注意してください。何が起こっているのかというと、boundsの引数リストでパターンマッチングを行うと、sfromevidenceが特定の値に固定されるのが早すぎるため、これを延期する必要があります。そして（上位の型での推論は難しいので）またgo、スコープ付き型変数を必要とする明示的な型を提供する必要があります。
そして最後に、元のコードに戻ります。
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...
さて、冒頭で述べたように、対処しなければならない問題が1つ残っています。上記のコードでは、制約制約が満たされないforall s. MArrayE a e (ST s)ため、タイプの値を作成する方法はありません。forall s. MArray a e (ST s)同じ理由で、元のコードでは、の外部randShuffleSTを返す関数を記述できないため、発生する型エラーがなくても記述できませんでした。STArrayST
これらの問題の両方の理由は同じです。のSTArray最初のパラメータは、それが存在する状態スレッドです。のMArrayインスタンスSTArrayはinstance MArray (STArray s) e (ST s)であるため、常にフォームのタイプがありますST s (STArray s i e)。以来runST :: (forall s. ST s a) -> a、実行すると違法な方法でアウトをrunST mySTArrayAction「リーク」します。s調べて
runSTArray :: Ix i => (forall s. ST s (STArray s i e)) -> Array i e
とその箱から出された友人
runSTUArray :: Ix i => (forall s. ST s (STUArray s i e)) -> UArray i e。
使用することもできます
unsafeFreeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e)
それが可変配列で呼び出す最後の関数であると約束する限り、同じことを行うこと。関数はfreezeこの制限を緩和しますが、配列をコピーする必要があります。同様に、リストではなく配列を関数の純粋なバージョンに渡したい場合は、おそらく次のことも必要になります。
thaw :: (Ix i, IArray a e, MArray b e m) => a i e -> m (b i e);
unsafeThaw制御できない不変の配列を渡すので、ここで使用するのはおそらく悲惨なことです。これはすべて組み合わされて、次のようなものになります。
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")
これは、入力不変配列をコピーするのにO（n ）時間かかりますが、最適化を使用すると、出力の可変配列をフリーズするのにOSTArray （1）時間がかかります。これは、とArrayが内部で同じであるためです。
これを特にあなたの問題に当てはめると、次のようになります。
{-# 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'')
Data.Array.Unsafe.unsafeFreeze繰り返しますが、freezeをinに置き換えることができshufflePureます。配列の場合は配列をコピーして返す必要がないため、これによりおそらく高速化が実現しますArray i e。関数は安全にrunSTArrayラップされるので、それはの問題ではありません。（この2つは同等であり、PRNGの分割に関する詳細を法として示しています。）unsafeFreezeshufflePure'
ここに何が見えますか？重要なのは、可変コードのみが可変配列を参照し、可変のままである（つまり、内部に何かを返すST s）ことです。インプレースシャッフルを実行するためshuffle、配列を返す必要はなく、PRNGのみを返す必要があります。純粋なインターフェイスを構築するにはthaw、不変の配列を可変の配列にシャッフルし、その場でシャッフルしてからfreeze、結果の配列を不変の配列に戻します。これは重要です。これにより、可変データが純粋な世界に漏洩するのを防ぐことができます。渡された配列は不変であるため、直接可変的にシャッフルすることはできません。逆に、可変であるため、可変でシャッフルされた配列を不変の配列として直接返すことはできません。誰かがそれを変更できるとしたらどうでしょうか。
これらのエラーはすべて、の不適切な使用に起因するため、これは上記のエラーのいずれにも反するものではありませんrunST。の使用を制限しrunST、純粋な結果をアセンブルした後でのみ実行すると、すべての内部状態スレッドが自動的に発生する可能性があります。ランク2タイプの唯一の関数であるためrunST、深刻なタイプの奇妙さを生み出すことができる唯一の場所です。s他のすべては、おそらく状態スレッドパラメータの一貫性を維持するためにもう少し考えたとしても、標準の型ベースの推論を必要とします。
そして見よ、見よ：
*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]
ついに成功！（最後は長すぎます。本当に。この回答の長さについては申し訳ありません。）