array関数と!演算子について,もう少し詳しく見ていきましょう。それぞれの型は以下の通りです。

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

 このように,arrayは配列を作成するために,第1引数として添え字の最小値と最大値,第2引数として「添え字となるキー(key)」と「値(value)」を対にした「連想リスト(association list)」を取ります。この連想リストに含まれていないものは配列には含まれません。連想リストに含まれていないキーを使って配列にアクセスした場合,結果の値は未定義(⊥)です。おそらく,値が未定義であることを示すエラーになるでしょう。

*Main> let arr = array (Red, Blue) [(Red, 12), (Green, 23)]
*Main> arr!Blue
*** Exception: (Array.!): undefined array element

 同様に,配列の範囲外へのアクセスは未定義(⊥)です。

*Main> let arr = array (Green, Blue) [(Green, 12), (Blue, 22)]
*Main> arr!Red
*** Exception: Error in array index

 また,連想リストが添え字の範囲外のキーを持つ場合,その配列の動作は未定義(⊥)になります(参考リンク)。

*Main> let arr = array (Green, Blue) [(Red, 12), (Blue, 22)]
*Main> arr!Red
*** Exception: Error in array index
*Main> arr!Blue
*** Exception: Error in array index

 「配列そのものが未定義になる」というのは直感に反しますが,この仕様は添え字の範囲を誤って設定した場合に重要な役割を果たします。

 arrayの第1引数として渡す範囲は,順不同ではありません。必ず下界(lower bound,つまり最小値),上界(upper bound,つまり最大値)の順に渡す必要があります。すべての次元において下界が上界を上回るよう値を与えた場合,そのような範囲は存在しないため配列は空になります。

 こうした配列に対する添え字付け(indexing)はどうあるべきでしょうか?

 この配列は空であるため,添え字を使った配列に対する参照は,常に範囲外に対するものになります。したがって,配列に対する添え字は必ず境界エラーと結びつけられなければなりません。

Prelude Data.Array> let arr = array (2,0) [(0,"Hellow" ), (2,"Array")]
Prelude Data.Array> arr!0
"*** Exception: Error in array index
Prelude Data.Array> arr!2
"*** Exception: Error in array index

 配列そのものを未定義としない場合,素朴な実装では,存在する添え字ごとに参照のための領域を確保することになるでしょう。その結果,実際に作成された配列は空であるのにもかかわらず,配列を作成するのに使用した添え字の分だけ余計に領域を消費することになります(同様に,配列が空でない場合でも,無効な添え字はその分だけ余計な領域を必要とします)。このような余計な領域の確保は,無駄以外の何者でもありません。

 そこで無駄な空間非効率を避けるために,範囲外に対する添え字付けは「配列そのものを未定義とする」ようにしているのでしょう。

Prelude Data.Array> array (2,0) [(0,"Hellow"), (2,"Array")]
array *** Exception: Error in array index
Prelude Data.Array> array (0,2) [(3,"Hellow"), (4,"Array")]
array *** Exception: Error in array index

 このように定義しておけば,複雑な実装を行わなくても比較的効率のよい配列を作成することができます。

 なお,Ixクラスのインスタンスを導出した型の添え字では,最小値は常に最大値の左に存在する値でなければなりません。これはColorのような無引数データ構成子を持つデータ型では,左から右へ順に0からn-1までの番号が割り振られていると仮定してインスタンスの導出を行っているためです(参考リンク)。Colorでは,Redに0,Greenに1,Blueに2が割り振られることになります。

*Main> let arr = array (Blue, Red) [(Red, 12), (Blue, 22)]
*Main> arr!Red
*** Exception: Error in array index
*Main> arr!Blue
*** Exception: Error in array index

 ここまで説明してきたように,Haskellでの配列の作成や参照はあまり安全な操作ではありません。この点がリストとは大きく異なります。リストの作成が失敗することはなく,連想リストへの参照はMaybeを返すためエラーにはなりません。

Prelude> :t lookup
lookup :: (Eq a) => a -> [(a, b)] -> Maybe b
Prelude> lookup "assoc" [("pair", 87), ("assoc", 22)]
Just 22
Prelude> lookup "list" [("pair", 87), ("assoc", 22)]
Nothing

 では,配列は安全性と引き換えに何を得ているのでしょうか? それは性能です。配列というデータ構造を仕様で定義し,様々な振る舞いに対して制限を加えることで,効率がいい実装を行う余地を与えています。

 配列を使うことで,どの程度,効率が上がるのでしょうか? Haskellの言語仕様には,配列の計算量に特化した記述はありません。ただ,仕様からある程度は想像できます。仕様には「配列は制限のある関数である」と記述されているため,配列の参照の計算量はおそらく定数(計算量がO(1)オーダー)に近いことを想定していると考えられます(参考リンク1参考リンク2)。

 一方,配列の更新は,リストの更新と同様にコストの高い操作です。参照透明性を守るために,配列を使った演算もまた常に同じ値を返さなければならないからです。他の部分での操作によって配列の中身が書き換えられてしまうと,参照透明性が破れてしまいます。このため配列に対する更新操作は,元の配列を複製した新しい配列を返すように定義されているのです。結果として,配列を更新する場合の計算量は配列の大きさに対して線形(O(n)オーダー)になります。

 実際には,配列の更新操作をそのまま行っていると効率が悪いので,配列の更新関数は少し工夫されたものになっています。

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

 型を見ればわかるように,//演算子は連想リストを取って配列を更新します。差分を定義した連想リストを取って更新を一度に行うことで,要素の変更ごとに新たな配列を作成する無駄を防いでいます。

 試してみましょう。

Prelude Data.Array> let arr = array (0,2) [(0,"Immutable" ), (2,"Array")]
Prelude Data.Array> arr!0
"Immutable"
Prelude Data.Array> let arr' = arr//[(0,"Diff"), (1, "Result")]
Prelude Data.Array> arr'!0
"Diff"
Prelude Data.Array> arr'!1
"Result"
Prelude Data.Array> arr'!2
"Array"
Prelude Data.Array> arr!0
"Immutable"

 //演算子は,更新されていない要素や変更前の配列には全く影響を与えていないことがわかりますね。