STArraysのリストにrunSTArrayをマップしますか？

Question

私は、ツリーからマトリクスのフラット化されたリストを再帰的に作成する関数を持っています。私は直接[UArray (Int,Int) Int]を返さない理由はdoAllが再帰的に呼び出されるため、あるリスト内の行列の要素を変更し、新しい行列を追加し

doAll :: .. -> [ST s (STArray s (Int, Int) Int)] 

：これまでのところ私は署名を持っている再帰的な解決策が出ています。私は行列を不必要に凍結し解凍したくない。

これまでのところとても良いです。私はghci

runSTArray (matrices !! 0) 
runSTArray (matrices !! 1) 

に（タイプArray (Int, Int) Intの）n番目の行列を検査することができますし、実際に私は私のアルゴリズムのための正しい結果を得ます。私は、リストの上に再帰的に評価するかに包まれた単一の要素を評価しようとしようとした場合

map (runSTArray) matrices 

Couldn't match expected type `forall s. ST s (STArray s i0 e0)' 
      with actual type `ST s0 (STArray s0 (Int, Int) Int)' 

同じ問題が起こる：しかし、私はdoAllによって返されたリスト上runSTUArrayをマッピングする方法を見つけることができませんでした関数

何か起こっていることを説明してもらえますか（私はforallキーワードの意味を本当に理解できませんでした）、リストの配列をどのように評価することができましたか？

Answer 1

のように、他のSTアクションで値を処理することはできません。まず、STの仕組みを理解する必要があります。 STのモナドから純粋なコードへの唯一の方法は、runST関数、またはrunSTArrayのような関数を使ってそれを基にしたものです。これらはすべてforall s.の形式です。これは、STArrayからArrayを構築するためには、sタイプの変数runSTの代わりにコンパイラが好きな型に置き換えることができることをコンパイラが判断できることを意味します。

今、関数map :: (a -> b) -> [a] -> [b]を考えてみましょう。これは、リスト内のすべての要素がまったく同じ型（a）でなければならないことを示しているため、同じsも同じです。しかし、この特別な制約はrunSTArrayの型に違反し、コンパイラはsの他の値を自由に代入できる必要があると宣言します。

あなたが最初のSTモナドの内部配列を凍結する新しい関数を定義することによってこの問題を回避することができ、その結果のSTのアクションを実行します。

は

runSTArrays :: Ix ix => (forall s. [ST s (STArray s ix a)]) -> [Array ix a] 
runSTArrays arrayList = runST $ (sequence arrayList >>= mapM freeze) 

注forallはRankNTypes拡張子が必要です。

Answer 2

タイプシステムの制限に反しただけです。

runSTArrayのランクが高い型です。状態変数が一意のSTアクションを渡す必要があります。しかし、Haskellでは通常、リストにそのような値を持たせることはできません。

STアクションで生成した値がそこから逃れることができないことを、賢明な方法で表しています。つまり、あなたのデザインは何とか壊れているように見えます。

1つの提案：あなたはこれがST安全を作るタイプのトリックの不幸な結果である

sequence [ ... your ST s (STArray s x) ...] >>= processing 
    where 
    processing :: [STArray s x] -> ST s (your results)