Haskellの配列周辺についてのメモ


なんかいっぱいあるのでどうしたらいいかについて個人的メモ。

# Data.Arrayは使わない

`Data.Array`は、Haskell 98で規定されていた「変更不能 immutable」で「ボックス化された boxed」配列を提供している。これは現在のライブラリでは`Data.Array.IArray`が提供するものに該当し、[更に後者の方が配列操作に関わるより一般的なインターフェースを提供しているのでそちらを使うこと](http://hackage.haskell.org/package/array-0.5.0.0/docs/Data-Array.html)とされている。

# 様々な配列データ型の見取図

| |変更不能|変更可能（IOモナド）|変更可能（STモナド）|
|:----:|:-------------:|:-------------:|:-----------:|
|ボックス値 Boxed Value|Array & DiffArray| IOArray|STArray|
|即値 Unboxed Value|UArray & DiffUArray| IOUArray & StorableArray|STUArray|



## 変更不能なボックス値配列

上述の通り、左上の変更不能なボックス値配列（中身が普通のHaskellの値と同じサンクで遅延評価な値の配列）がHaskell 98に規定されていたような、変更不能なHaskellらしい配列を提供している。同じインターフェースを持つ変更不能な純粋な配列としては[`DiffArray`](http://hackage.haskell.org/package/diffarray-0.1.1/docs/Data-Array-Diff.html)もある。これは内部実装が`Array`とは違っていて内部では配列差分を`IOArray`を利用して保持するという方法で`(\\\\)`演算子による配列更新が変更不能な配列であるにもかかわらず高速化されている（ことになっている[^1]）。

[^1]: 2012年1月時点では残念ながら理論的に期待されるようには高速でないようである（現状について識者の情報提供があれば附記したい）。

## 変更不能な即値配列

即値配列はC言語の配列と同じように中身が即値なのでサンク分のコストがない配列。なので、当然ながら中身の値が取れる型に制約がある。その一覧は[`Data.Array.Unboxed`](http://www.haskell.org/ghc/docs/latest/html/libraries/array/Data-Array-Unboxed.html)を見ればわかるが、`Bool, Char, Int, Double, Word, Ptr,etc`といったいかにもなものしか入れられない。中身の大きさが可変なもの（つまり任意長である`Integer`だの`String`だの函数だの）は当然のことながら入れられない。またサンクではなく即値が入るので、配列の中身は正格評価になる（ちなみにインデックスの方はボックス値配列でも即値配列でも正格評価）。


## 変更可能な配列 - IOとST

[IO(U)Array](http://www.haskell.org/ghc/docs/latest/html/libraries/array/Data-Array-IO.html)と[ST(U)Array](http://www.haskell.org/ghc/docs/latest/html/libraries/array/Data-Array-ST.html)はそれぞれIOモナドとSTモナド内で使うことができる。要はIORefとSTRefの配列に特化したヴァージョンと考えておおむね差し支えないようだ（IORefがSTRefから定義されているようにIOArrayもSTArrayから定義されている）。[`Data.Array.MArray`](http://www.haskell.org/ghc/docs/latest/html/libraries/array/Data-Array-MArray.html)が定義するMArray型クラスが両者に共通のインターフェースを提供しており、`newSTRef`や`newIORef`にArray用のデータ構築機能をくっつけたようなデータ構築用の函数`newArray`と読み出し書き込み用の函数`readArray/WriteArray`が提供されている（以下の例に見るように`IORef`とかと同じで使い方はわかりやすい）：

```hs:
import Data.Array.IO
main = do 
  arr <- newArray (1,10) 37 :: IO (IOArray Int Int)
  a <- readArray arr 1
  writeArray arr 1 64
  b <- readArray arr 1 
  print (a,b)
```

`newArray (左端,右端) 初期化値`という使い方だが、データ構築時に中身も単一の初期化値でなくきちんと突っ込みたいなら`newListArray (左端,右端) [左端から昇順に投入されていく初期化値のリスト]`を使う：

```hs:
a <- newListArray ((0,0),(9,9)) [x^y|x<-[0..9],y<-[0..9]]

```

みたいな感じ。ほぼ配列に特化したIORefやSTRefみたいなものなので、IOモナドやSTモナドの中でだけ使えるというだけで、後はまあ普通の命令型言語の配列と同じような使い方。わかりやすいけど「Haskellらしい」とは言えないかも（いや別に「らしく」ある必要があるわけではないのかもしれないけど）。即値ヴァージョンも入れられる値の型に制約がある＆中身が正格評価というだけであとはほぼ同じ。

## 変更可能な配列 - Storable
インターフェースを含めてほぼIOUArrayと一緒。ただし、IOUArrayはGHCのヒープの中で位置が変わる可能性があるのに対して、StorableArrayでは位置が固定されていることだけが違う。配列へのポインタをFFIでC側に渡して使う際に利用する。FFIのためのものなので、必要な人には必要なんだろう（私のような情弱初心者には余り縁がない）。

# 行列計算はRepaパッケージで

グラフィック操作みたいな行列計算的な用途には[RE(gular) PA(rallel) Arrays](http://www.haskell.org/haskellwiki/Numeric_Haskell:_A_Repa_Tutorial)を使うのがよいようだ。普通に配列として使うにも支障はないし（インデックス関係が上述のArrayと違って柔軟性がないくらい）、repa-ioで配列データをファイルに記録したり読み込んだりできるので、そのためだけに使ってもいいかもしれない。Repaの使い方を少し見てみたところ、型付けがちょっと面白かったのだが、深入りはしない。

# ArrayRefライブラリとか
[ArrayRefライブラリ](http://www.haskell.org/haskellwiki/Library/ArrayRef)というのもあるようで、これは名前通りArrayとRefのライブラリ。後者については即値のRefを普通のRefと同様のインターフェースでIOURefとかSTURefとかとして提供している。前者についてはサイズ変更可能な配列を提供している（境界を超えてアクセスすると自動的に拡大するような動的配列）。

# 雑感めいたもの
うーん。変更可能配列は要はIORefやSTRefだし（いやそりゃ別に結構なことだとは思うけど）、変更不能配列は更新の問題があるのでData.Mapとかの方が使いやすいことが多いしDiffArrayはまだ残念な状態となるとHaskellの普通の純粋な配列はあんまり使い勝手がいいとは言えなさそうな気がする。FFIのためにStorableArrayを使うとか、行列操作やらでRepaを使うとか、そういう時のためのもの、という感じかな。