破壊的な更新を行うMArrayクラス

 Array型に対する参照はコストが低いが,更新はコストが高いことがわかりました。どうすれば配列の更新のコストを下げられるでしょうか?

 Array型が更新ごとに新しい配列を作成するのは,純粋関数において参照透明性を保証するためでした。であるなら,I/Oなどのアクションの元では制約を緩めてもよいでしょう。そうした意図で用意されているのがData.Array.MArrayモジュールで定義されているMArray(可変配列,Mutable Array)クラスです。

Prelude Data.Array.MArray> :i MArray
class (Monad m) => MArray a e m where
  getBounds :: (Ix i) => a i e -> m (i, i)
  Data.Array.Base.getNumElements :: (Ix i) => a i e -> m Int
  newArray :: (Ix i) => (i, i) -> e -> m (a i e)
  newArray_ :: (Ix i) => (i, i) -> m (a i e)
  Data.Array.Base.unsafeNewArray_ :: (Ix i) => (i, i) -> m (a i e)
  Data.Array.Base.unsafeRead :: (Ix i) => a i e -> Int -> m e
  Data.Array.Base.unsafeWrite :: (Ix i) => a i e -> Int -> e -> m ()
        -- Defined in Data.Array.Base

 MArrayクラスでは配列の作成はnewArray*メソッド,参照はreadArray関数,更新はwriteArray関数で行います。

Prelude Data.Array.MArray> :t newArray
newArray :: (Ix i, MArray a e m) => (i, i) -> e -> m (a i e)
Prelude Data.Array.MArray> :t newArray_
newArray_ :: (Ix i, MArray a e m) => (i, i) -> m (a i e)
Prelude Data.Array.MArray> :t readArray
readArray :: (Ix i, MArray a e m) => a i e -> i -> m e
Prelude Data.Array.MArray> :t writeArray
writeArray :: (Ix i, MArray a e m) => a i e -> i -> e -> m ()

 では,実際に使ってみましょう。Data.Array.MArrayモジュールではMArrayクラスや関数のインタフェースのみを定義しています。このため,実際に使用するにはMArrayクラスのインスタンスになる配列を定義しているモジュールを使用する必要があります。

 配列を定義したモジュールは,目的ごとに分けて提供されています。例えば,配列の操作にIOモナドを使うIOArrayはData.Array.IOモジュールに定義されています。STモナドを使うSTArrayはData.Array.STモジュールに,STMモナドを利用するTArrayはstmパッケージのControl.Concurrent.STM.TArrayモジュールに,それぞれ定義されています。

 ここでは説明が簡単なIOArrayを取り上げます。Data.Array.IOはData.Array.MArrayをエクスポートしているため,そのままMArrayを利用できます。

Prelude Data.Array.IO> arr <- newArray (1,22) 2::IO (IOArray Int Int)
Prelude Data.Array.IO> readArray arr 4
2
Prelude Data.Array.IO> arr_ <- newArray_ (0,22) ::IO (IOArray Int Int)
Prelude Data.Array.IO> readArray arr_ 4
*** Exception: MArray: undefined array element
Prelude Data.Array.IO> :t writeArray arr_ 4 0
writeArray arr_ 4 0 :: (MArray IOArray Int m) => m ()
Prelude Data.Array.IO> writeArray arr_ 4 0
Prelude Data.Array.IO> readArray arr_ 4
0

 IO (IOArray Int Int)と型注釈を付けているのは,インスタンスになっている具体的な型を推論しきれないからです。

Prelude Data.Array.IO> arr <- newArray (1,22) 2

<interactive>:1:7:
    No instance for (MArray a t IO)
      arising from a use of `newArray' at <interactive>:1:7-23
    Possible fix: add an instance declaration for (MArray a t IO)
    In a 'do' expression: arr <- newArray (1, 22) 2

 処理系やライブラリの不備で型推論できないのではなく,配列の型を推論できない可能性がある特殊な事情があるのです。詳しくは後で説明します。

 例に戻りましょう。

 newArrayは第2引数の値を使って配列を初期化するのに対し,newArray_は配列を作成するだけで初期化は行いません。そのためnewArray_を使って作成した配列では,writeArrayを使って書き込む前の最初の参照がエラーになっています。また,writeArrayは//演算子とは異なり,渡された配列そのものの要素を書き換えています。

 このように,IOArrayなどのMArrayクラスのインスタンスでは,配列を複製することなく中身を直接書き換えられます。したがって,更新にかかる計算量は,参照と同じようにO(1)オーダーで済むと期待できます。

 ここまではArrayとMArrayを別個のものとして扱ってきましたが,実用性を考えると相互のやり取りができたほうが便利です。こうした目的のために提供されているのが,freeze関数とthaw関数です。

Prelude Data.Array.MArray> :t freeze
freeze :: (Data.Array.Base.IArray b e, MArray a e m, Ix i) => a i e -> m (b i e)
Prelude Data.Array.MArray> :t thaw
thaw :: (MArray b e m, Data.Array.Base.IArray a e, Ix i) => a i e -> m (b i e)

 IArray(不変配列,Immutable Array)クラスは,Arrayなどの「書き換え不可能な配列」を示す型クラスです。とりあえず,IArrayクラス=Array型だと思ってください。そう考えると,freezeとthawの型は以下のようになります。

freeze :: (MArray a e m, Ix i) => a i e -> m (Array i e)
thaw :: (MArray b e m, Ix i) => Array i e -> m (b i e)

 freezeとthawはArrayとの相互変換を行う関数であることがわかります。つまり,freezeは変更可能なMArrayから変更不可能なArrayへと配列の凍結(freeze),thawは変更不可能なArrayから変更可能なMArrayへと配列の解凍(thaw)を行うのです。

 freezeとthawはそれぞれ配列を複製しているので,変換前の配列に対する操作と変換後の配列に対する操作が相互に影響を及ぼすことはありません。

Prelude Data.Array.IO Data.Array> let arr = array (0,2) [(0,"Immutable" ), (2,"Array")]
Prelude Data.Array.IO Data.Array> arr!0
"Immutable"
Prelude Data.Array.IO Data.Array> arr' <- thaw arr::IO (IOArray Integer String)
Prelude Data.Array.IO Data.Array> readArray arr' 0
"Immutable"
Prelude Data.Array.IO Data.Array> writeArray arr' 0 "Mutable"
Prelude Data.Array.IO Data.Array> readArray arr' 0
"Mutable"
Prelude Data.Array.IO Data.Array> arr!0
"Immutable"
Prelude Data.Array.IO Data.Array> do { arr'' <- freeze arr'; return $ arr''!0}
"Mutable"
Prelude Data.Array.IO Data.Array> do { arr'' <- freeze arr'; return $ (!0) $ arr''//[(0, "Immutable")]}
"Immutable"
Prelude Data.Array.IO Data.Array> do { arr'' <- freeze arr'; let {arr''' = arr''//[(0,"Immutable")]}; print $ arr'''!0}
"Immutable"
Prelude Data.Array.IO Data.Array> do { arr'' <- freeze arr'; return $ arr''//[(0, "Immutable")]; readArray arr' 0}
"Mutable"
Prelude Data.Array.IO Data.Array> do { arr'' <- freeze arr'; writeArray arr' 2 "Change Again"; print $ arr''!2}
"Array"

 ここで再び効率について考えましょう。MArrayクラスを必要としたのは,配列の複製を防ぎ,配列に対する更新をより速く行うためでした。同様のことは,配列を変換する場合にも言えます。配列の変換にかかるコストは,配列を複製するために,配列の大きさに従ってO(n)で線形増加します。ところが,配列の複製は,参照透明性が守られることが保証されている状況下では無駄です。その場合,配列を複製せずにそのまま流用したほうが効率が良いのではないでしょうか?

 このような目的のために,安全ではないバージョンの変換関数も用意されています。

Prelude Data.Array.MArray> :t unsafeFreeze
unsafeFreeze :: (Data.Array.Base.IArray b e, MArray a e m, Ix i) =>
                a i e -> m (b i e)
Prelude Data.Array.MArray> :t unsafeThaw
unsafeThaw :: (MArray b e m, Data.Array.Base.IArray a e, Ix i) =>
              a i e -> m (b i e)

 unsafeFreezeとunsafeThawは,O(1)で配列の変換を実行します(ただし,GHCでは最適化オプション「-O」を使用してコンパイルする必要があります)。

 当然ながら,これらの関数を使って変換した配列は元の配列をそのまま利用するため,参照透明性を破る危険性があります。また,unsafeThawとunsafeFreezeの組み合わせはスレッド安全でないため,複数のスレッドが動作する環境では別の問題が発生する可能性もあります。くれぐれも取り扱いには気をつけてください(参考リンク)。

 なお,Data.Array.STモジュールは,STArrayを使用した計算結果にunsafeFreezeを適用するrunSTArray関数を提供しています。

runSTArray :: (Ix i)
	   => (forall s . ST s (STArray s i e))
	   -> Array i e
runSTArray st = runST (st >>= unsafeFreezeSTArray)