Haskellでは，リストを基本的なデータ構造として様々な用途に使います。一方，Cなどの命令型の言語では，配列（Array）を基本的なデータ構造として用います。
この違いはどこから生じているのでしょうか？ Haskellでリストを使う場合と配列を使う場合にはどのような違いがあるのでしょうか？
今回はこうした切り口で配列について考えていきたいと思います。
リストと配列の違い
配列には様々な実装方法があり，どのような実装を採用するかによって細かい性質が異なります。ただ，どのような実装であっても，配列には共通した性質があります。先頭からの逐次的なアクセスにもランダムな要素へのアクセスにも同じように適しているという点です。
リストは再帰的な定義になっているため，当然，逐次的なアクセスには適しています。しかし，参照（look-up）や更新（update）などの操作で必要とされる，ランダムなアクセスにはあまり適していません。リストの場合，こうした演算のために発生するコストは，リストの長さに従って線形増加します。計算量がO(n)のオーダーになってしまうのです。そこで，こうした演算へのコストを抑えるために，リストの代わりに配列をよく使います。
配列を使うことで，どの程度のコストを抑えられるのでしょうか？ これは配列の実装によって異なります。実装によっては，特定の演算では配列を使うメリットがないこともあります。「配列は必ずしもリストより効率が良いデータ構造ではない」ということを覚えておいてください。では，Haskellにおける配列を見ていきましょう。
数値型以外の添え字も使えるArray型
今回は主に「arrayパッケージで提供されている配列」について説明します（第10回で説明した並列配列は特殊なものなので，いったん忘れてください）。
まず，標準Haskellで定義されている配列を見てみましょう。標準Haskellの配列は，Data.ArrayモジュールのArray型です。Array型の添え字（index）はIntなどの数値型に固定されていません。baseパッケージのData.Ixモジュールで定義されているIx（index）クラスのインスタンスであれば，どんな型でも添え字に使えます。
Prelude Data.Array> :i Array
data Array i e = GHC.Arr.Array !i !i !Int (GHC.Prim.Array# e)
-- Defined in GHC.Arr
instance (Ix i, Eq e) => Eq (Array i e) -- Defined in GHC.Arr
instance (Ix i) => Functor (Array i) -- Defined in GHC.Arr
instance (Ix i, Ord e) => Ord (Array i e) -- Defined in GHC.Arr
instance (Ix a, Read a, Read b) => Read (Array a b)
-- Defined in GHC.Read
instance (Ix a, Show a, Show b) => Show (Array a b)
-- Defined in GHC.Arr
Prelude Data.Array> :t array
array :: (Ix i) => (i, i) -> [(i, e)] -> Array i eIxクラスは，型の範囲や型から数値を算出するためのメソッドを提供しています。その結果，Ixクラスのインスタンスである型を，あたかも数値型による添え字のように利用できるのです。
Prelude Data.Ix> :i Ix
class (Ord a) => Ix a where
range :: (a, a) -> [a]
index :: (a, a) -> a -> Int
GHC.Arr.unsafeIndex :: (a, a) -> a -> Int
inRange :: (a, a) -> a -> Bool
rangeSize :: (a, a) -> Int
GHC.Arr.unsafeRangeSize :: (a, a) -> Int
-- Defined in GHC.Arr
instance (Ix a, Ix b) => Ix (a, b) -- Defined in GHC.Arr
instance (Ix a1, Ix a2, Ix a3) => Ix (a1, a2, a3)
-- Defined in GHC.Arr
instance (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1, a2, a3, a4)
-- Defined in GHC.Arr
instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) =>
Ix (a1, a2, a3, a4, a5)
-- Defined in GHC.Arr
instance Ix Char -- Defined in GHC.Arr
instance Ix Int -- Defined in GHC.Arr
instance Ix Integer -- Defined in GHC.Arr
instance Ix Bool -- Defined in GHC.Arr
instance Ix Ordering -- Defined in GHC.Arr
instance Ix () -- Defined in GHC.Arrこのように，Ixのクラスのインスタンスにはタプルも含まれます。このため，タプルを渡すことで，複数の値が組になった多次元の配列を表現できます。
Data.Ixモジュールの構成要素は，Data.Array等の配列を利用するためのモジュールからエクスポートされるようになっています。また，Ixクラスは導出インスタンス宣言の対象にもなっています（参考リンク）。なので，普段はこのモジュールの存在を意識しなくても大丈夫です。
import Data.Array data Color = Red | Green | Blue deriving (Eq, Ord, Ix)
IxクラスはOrdクラスのサブクラスであるため，Ordクラスのインスタンスがないと導出できない点に注意してください。
import Data.Array data Color = Red | Green | Blue deriving Ix
$ ghci ArrayTest.hs
GHCi, version 6.8.2: http://www.haskell.org/ghc/ :? for help
Loading package base ... linking ... done.
[1 of 1] Compiling Main ( ArrayTest.hs, interpreted )
ArrayTest.hs:3:0:
No instance for (Ord Color)
arising from the 'deriving' clause of a data type declaration
at ArrayTest.hs:3:0-42
Possible fix: add an instance declaration for (Ord Color)
When deriving the instance for (Ix Color)
Failed, modules loaded: none.
Prelude> 同じことはEqクラスのサブクラスであるOrdクラスにも言えます。
Prelude> :i Ord
class (Eq a) => Ord a where
compare :: a -> a -> Ordering
(<) :: a -> a -> Bool
(>=) :: a -> a -> Bool
(>) :: a -> a -> Bool
(<=) :: a -> a -> Bool
max :: a -> a -> a
min :: a -> a -> a
-- Defined in GHC.Base
～ 略 ～結果として，上のコードではEq，Ord，Ixの三つのクラスに対して導出インスタンス宣言を行っているのです。
実際に試してみましょう。array関数を使って配列を作成し，!演算子を用いて配列の要素を取り出します。
*Main> let arr = array (Red, Blue) [(Red, 12), (Green, 23)] *Main> arr!Red 12 *Main> let arr = array ((Red, Red), (Blue, Blue)) [((Blue, Red), "array"), ((Green, Green), "color")] *Main> arr!(Green, Green) "color"
添え字にColor型を使った参照も，添え字にColor型の組を使った参照も正常に働いているのがわかりますね。
ただ，!演算子を使った添え字による参照は，将来は別の記法に変更されるかもしれません。なぜなら「!演算子」と「!という文字を用いている別の意味を持つ式」を区別するのは困難だからです。例えば，第9回で紹介したバン！パターンを有効にしている場合，!演算子を使用すると，バン！パターンを使用したと誤って認識される可能性があります。このような問題を避けるため，次期標準のHaskell'では，添え字を別の記法に変更することが提案されています（参考リンク）。
