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

# IArrayのつかいかたメモ

自分のためにとりあえず変更不能配列の方だけ簡単に見ておく（変更可能配列も似たようなものではあるけれど）。

現在普通に使われる変更不能配列はIArray型クラスに属するデータ型で、特にArrayが基本的なもの。で、Arrayはインデックスと要素の値とで2つの型を取る(Array i e)。`Array Int String`みたいな感じ。

## インデックスに使える型

インデックスに使える型は、他の言語のいわゆる「配列」と少し違っていて、[Ix型クラス](http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/Data-Ix.html)に属しているものであればなんでもいい。Intはもちろん、BoolやCharやWordなんかも使える。もちろん、Integerも使える。変わったところではOrdering(`LT`,`EQ`,`GT`)も使えるし、なんとIOMode(`ReadMode`,`WriteMode`,`AppendMode`,`ReadWriteMode`)なんかも使える。これはまあある意味では当たり前で、自分で定義した列挙型は`deriving Ix`すれば使える。タプルはクイントゥプルまでは既にData.IxでIxインスタンスになっているが、それ以上の項数のタプルは`deriving`で（タプルの要素はもちろんIxクラスのインスタンスでなければいけない）。キーにOrd型クラスのインスタンスを取れるMapとは違って、ArrayではDouble型の値をインデクッスにしたりはできない点は注意が必要かもしれない。

## データ構築函数

データ構築用には幾つかの函数が用意されている。`array`函数の使い方はこう：

```hs:
array (インデックスの最小値, インデックスの最大値) [(インデックス, 要素値)]
array ((0,0),(9,9)) [((x,y), 10*x+y)|x<-[0..9],y<-[0..9]]

```

要は構築したい配列のインデックスの範囲と、インデックスをキーとした連想リストを渡す、ということね。インデックス範囲内で要素値を渡していないものについては`undefined`になる（当然だが勝手に初期化したりはしてくれない）。注意しなければいけないのは、渡した連想リストの中に、範囲外のインデックスを含むものがあると、配列全体が`undefined`になること。あと、連想リストの中でインデックスが重複していると、動作は処理系依存（GHCは後に来たもので上書きするがHaskell 98的にはそのインデックスに対応する要素値は`⊥`らしい）。で、この段階で`undefined`になるかどうかがチェックされる関係上、`array`で構築する(というか構築の際に内部でこのチェックを行っている`safeIndex`函数を使っている関係で他の構築函数でも即値配列型UArrayでもなのだが) **配列のインデックスは正格評価になる** （もちろんボックス値配列なら要素値は遅延評価）。

もうひとつ、注意しておくべき仕様：インデックスに関して、最小境界が最大境界を上回っている次元がひとつでもあると、そういう配列はそれ自体としては合法だが空になる（連想リストの中身は無視される）。空な配列に`(!)`演算子とかでインデックスを介してアクセスすると境界外エラーになるが、`bounds`函数は当の逆転した境界の対を普通にそのまま返してくる。

`listArray`は`array`と似たようなものだが、連想リストではなく普通の要素値リストを受け取って、最小インデックスから昇順に要素値を配列に突っ込んでいく。なので：

```hs
listArray (インデックスの最小値, インデックスの最大値) [昇順で投入されていく要素値]
listArray ((0,0),(9,9)) [0..99]
```

みたいな感じ。要素値リストが余れば残りは無視される。足りないと、足りなかった部分の要素値は`undefined`になる。

場合によっては便利なのかもしれないが、なんでまたこんなものをわざわざライブラリに入れるのか、という感じもするのが`accumArray`で、これは`array`と似ているものの、連想リストのキーが重複してても差し支えない：

```hs
accumArray 畳み込み函数 デフォルト値 (最小インデックス,最大インデックス) [(インデックス,要素値)]
accumArray (+) 3 (0,3) [(0,0),(0,2),(1,1)]
=> array (0,3) [(0,3+0+2),(1,3+1),(2,3),(3,3)]
== array (0,3) [(0,5),(1,4),(2,3),(3,3)]
```

となる。基本的な動作はデフォルト値に対して畳み込み用の函数で連想リスト中の要素値を畳み込んだ値を各インデックスに対して突っ込んでいくというもの。連想リストにないインデックスについては、`undefined`にせず、デフォルト値を突っ込む。

## アクセス函数

配列なので要素にはインデックスを介してアクセスすることになる。いまさらだが、基本的には`(!)`演算子を使って：

```hs
配列 ! インデックス
arr = listArray (0,9) [9,8..0]
arr ! 3
=> 6
```

という感じ。`indeces`は単純に引数にとった配列の最小境界から最大境界までのインデックスのリストを返してくる。もちろん要素値は触らないので要素が`undefined`でもインデックスは有効なものとして返ってくる。空の配列なら空リストを返す。`elems`は同様にしてインデックス順に要素値を返してくる。`assocs`は両者を組み合わせたようなもので、連想リストを返してくる。

## 配列の更新

変更不能配列なので要素の更新は基本的には配列全体を新たに構築して返してくる(IArrayクラスでもDiffArrayは差分を内部で管理して巧くやってくれていることになっているけど)。使うのは配列更新演算子`(//)`で：

```hs
配列 // 連想リスト
listArray (0,2) [100,200,300] // [(1,150),(2,450)]
=> array (0,2) [(0,100), (1,150), (2,450)]
```

という感じ。ま、レコード型の値をフィールドラベルで更新してるのと同じだよな（配列全体はレコード型でインデックスがラベルと思えば）。

## (contravariant)mapみたいなもの

後は要素値にだけ働きかける`map`みたいな`amap`函数と、インデックスに働きかける`ixmap`函数がある。`amap`は直観的に理解できる。`ixmap`は定義を見るのが早い：

```hs
ixmap (新たな最小インデックス,新たな最大インデックス) インデックス間の写像 元の配列
ixmap (l,u) f arr =
    array (l,u) [(i, arr ! f i) | i <- range (l,u)]
```

インデックス値`i`を函数`f`で写した結果`j`を使い元の配列でインデックス`j`に対応する要素を新たな配列のインデックス`i`に対応する要素として突っ込む。うーむ。これは確かに使うときには使いそうな気がする。インデックスに作用するものとしては確かに自然で納得のいく定義なんだが、普通のmapとかとは逆方向というかcontravariantなんだよな：

```hs
出発元のインデックスの集合          出発元の配列
         ↑ f     >-- ixmap -->     ↓ (ixmap f)
到着先のインデックスの集合          到着先の配列
```

という仕組みになってる。`ixmap f`の矢印方向が`f`と逆で、つまりcontravariant。