生の値を格納する非ボックス化配列

 では,「MArrayのクラスのインスタンスの型は,使用しているモナドからは推論できない可能性がある理由」を説明しましょう。併せて,IArrayクラスが存在する理由についても説明します。

 MArrayクラスは「配列の複製を防ぐ」という観点で性能の向上を図っています。ところが,Haskellの実装を考えると,配列の性能を向上をさせる方法がもう一つあることがわかります。

 第7回で説明したように,Haskellではマシン表現そのものではなくボックス化された値を扱います。ここまで見てきた配列はすべて,どのような型でも要素として持つことができるよう,ボックス化されたHaskellの値を格納するようになっていました。であれば,ボックス化されていない生のマシン表現を配列に格納することで性能を向上させられるのではないでしょうか?

 これを実現するのが非ボックス化配列です。非ボックス化配列にはArrayの非ボックス化版であるUArray,IOArrayの非ボックス化版であるIOUArray,STArrayの非ボックス化版であるSTUArrayがあります。UArrayを利用するには専用のData.Array.Unboxedモジュールが必要ですが,IOUArrayとSTUArrayはそれぞれIOArrayやSTArrayを提供しているモジュールから利用できます。

 非ボックス化配列について詳しく見ていきましょう。:infoコマンドで非ボックス化配列を調べると,以下のような情報が表示されます。

Prelude Data.Array.Unboxed> :i UArray
data UArray i e
  = Data.Array.Base.UArray !i !i !Int GHC.Prim.ByteArray#
        -- Defined in Data.Array.Base
instance (Ix ix, Eq e, IArray UArray e) => Eq (UArray ix e)
  -- Defined in Data.Array.Base
instance (Ix ix, Ord e, IArray UArray e) => Ord (UArray ix e)
  -- Defined in Data.Array.Base
instance (Ix ix, Show ix, Show e, IArray UArray e) =>
         Show (UArray ix e)
  -- Defined in Data.Array.Base
instance IArray UArray Bool -- Defined in Data.Array.Base
instance IArray UArray Char -- Defined in Data.Array.Base
instance IArray UArray Int -- Defined in Data.Array.Base
instance IArray UArray Float -- Defined in Data.Array.Base
instance IArray UArray Double -- Defined in Data.Array.Base
Prelude Data.Array.Unboxed> :m Data.Array.IO
Prelude Data.Array.IO> :i IOUArray
newtype IOUArray i e
  = array-0.1.0.0:Data.Array.IO.Internals.IOUArray (Data.Array.Base.STUArray
                                                      GHC.Prim.RealWorld i e)
        -- Defined in array-0.1.0.0:Data.Array.IO.Internals
instance Eq (IOUArray i e)
  -- Defined in array-0.1.0.0:Data.Array.IO.Internals
instance MArray IOUArray Bool IO
  -- Defined in array-0.1.0.0:Data.Array.IO.Internals
instance MArray IOUArray Char IO
  -- Defined in array-0.1.0.0:Data.Array.IO.Internals
instance MArray IOUArray Int IO
  -- Defined in array-0.1.0.0:Data.Array.IO.Internals
instance MArray IOUArray Float IO
  -- Defined in array-0.1.0.0:Data.Array.IO.Internals
instance MArray IOUArray Double IO
  -- Defined in array-0.1.0.0:Data.Array.IO.Internals

 このうちIArrayクラスとMArrayクラスのインスタンスに注目すると面白いことがわかります。他のクラスとは異なり,IArrayとMArrayでは,UArray Bool,UArray Charのように格納される型ごとに別々のインスタンスを定義しているのです。つまり,添え字を除いたすべての型が決まらない限り,非ボックス化配列のインスタンスは決定できないのです。

 もちろん,非ボックス化されていない通常の配列ではそのようなことはありません。

Prelude Data.Array.IArray> :i Array
data Array i e = GHC.Arr.Array !i !i !Int (GHC.Prim.Array# e)
        -- Defined in GHC.Arr
~ 略 ~
instance IArray Array e -- Defined in Data.Array.Base
Prelude Data.Array.IArray> :m Data.Array.IO
Prelude Data.Array.IO> :i IOArray
newtype IOArray i e
  = GHC.IOBase.IOArray (GHC.Arr.STArray GHC.Prim.RealWorld i e)
        -- Defined in GHC.IOBase
instance Eq (IOArray i e) -- Defined in GHC.IOBase
instance MArray IOArray e IO
  -- Defined in array-0.1.0.0:Data.Array.IO.Internals)

 ただ,非ボックス化配列が存在するために,IArrayクラスとMArrayクラスのインスタンスに対する型推論はうまくいかない可能性があるのです。

 次に非ボックス化配列の使い方を考えましょう。IOUArrayとSTUArrayはMArrayクラスのインスタンスなので,これまで説明したような方法で利用できます。問題はUArrayです。UArrayはどのようにして利用すればよいでしょうか?

 実はData.Arrayモジュールの関数はすべて,Data.Array.IArrayモジュールの中でIArrayクラスに対する関数として再定義されています。

Prelude Data.Array.IArray> :t array
array :: (Ix i, IArray a e) => (i, i) -> [(i, e)] -> a i e
Prelude Data.Array.IArray> :t (!)
(!) :: (Ix i, IArray a e) => a i e -> i -> e
Prelude Data.Array.IArray> :t (//)
(//) :: (Ix i, IArray a e) => a i e -> [(i, e)] -> a i e

 そのため,UArrayはIArrayとほぼ同じように使用できます。

import Data.Array.Unboxed

data Color = Red | Green | Blue deriving Ix

*Main> let arr = array (Red, Blue) [(Red, 12), (Green, 23)]::UArray Color Int
*Main> arr!Red
12
*Main> let arr' = arr//[(Blue, 22)]
*Main> arr'!Blue
22

 ただし,非ボックス化配列に格納可能なのは,あくまでインスタンスが定義されている非ボックス化可能な型に限られます。

*Main> let arr = array ((Red, Red), (Blue, Blue)) [((Blue, Red), "array"), ((Green, Green), "color")]

<interactive>:1:10:
    No instance for (IArray a [Char])
      arising from a use of `array' at <interactive>:1:10-93
    Possible fix: add an instance declaration for (IArray a [Char])
    In the expression:
        array
          ((Red, Red), (Blue, Blue))
          [((Blue, Red), "array"), ((Green, Green), "color")]
    In the definition of `arr':
        arr = array
                ((Red, Red), (Blue, Blue))
                [((Blue, Red), "array"), ((Green, Green), "color")]

 また,非ボックス化の性質上,遅延評価が行われなくなるので注意してください。

*Main> let arr = array (Red, Blue) [(Red, 12), (Green, undefined)]::Array Color Int
*Main> arr!Red
12
*Main> let arr = array (Red, Blue) [(Red, 12), (Green, undefined)]::UArray Color Int
*Main> arr!Red
*** Exception: Prelude.undefined

 配列と非ボックス化配列の間には,このように実装や機能面での違いが多く表れるため,「配列を非ボックス化配列として流用」したり「非ボックス化配列を配列として流用」することはできません。結果として,当然,unsafeFreezeやunsafeThawを使った変換は,配列同士または非ボックス化配列同士に限られます。それ以外では結果が保証されません。

 なお,Data.Array.STモジュールでは,runSTArrayの非ボックス化配列版を提供しています。

Prelude Data.Array.ST> :t runSTUArray
runSTUArray :: (Ix i) =>
               (forall s. GHC.ST.ST s (STUArray s i e)) -> Data.Array.Base.UArray i e

著者紹介 shelarcy

 2008年4月13日に開催されたContinuation Fest(継続祭)に少しかかわっていました。当日使用されたスライドが公開されているので,興味のある方はご覧ください。当日の写真もそのうち公開されると思います。

 これを機に継続について書いてみようとも思いましたが,その前にいくつかもう少し詳しい説明が必要なものが残っていることを思い出しました。なので,もう少し足場を固めてからにしたいと思います。説明できる日ができるだけ早く来るとよいですね。