やさしい Haskell 入門 (バージョン 98)
back next top

13  配列

理想的には、関数型言語での配列は単にインデックスから値への関数とみなしま す。しかし、実際のところは、配列要素への効率的なアクセスを確保するために、 これらのアクセス関数の領域の特別な性質の利点を十分活用できることを確認し ておく必要があります。これは、連続した整数からなる整数の有限部分集合の同 型性という性質です。Haskell では、それゆえに、配列を適用演算をする一般的 な関数としては扱わず、サブスクリプト演算を行う抽象データ型として扱います。

関数的配列へのふたつの主要なアプローチは、インクリメンタルな定義とモノリ シックな定義とに識別することができます。インクリメンタルなアプローチの場 合は、与えられたサイズの空の配列を生成する関数と、もうひとつ、配列と、イ ンデックスと、値を引数としてとり、与えられたインデックスの要素だけが元の 配列と違う新しい配列を生成する関数となります。明かに、このような配列の意 味を素朴に実装するると、インクリメンタルな再定義のたびに配列の新しい複製 が必要になり、がまんできないくらい非効率になります。したがって、このアプ ローチをどうしても使いたい場合には、過度の複製を回避するために、洗練され た静的分析と巧妙な実行時の仕組を採用します。一方、モノリシックなアプロー チの場合には、配列全体は一度に生成されます。途中段階での配列の値を参照す ることはありません。Haskell には、インクリメンタルな配列更新の演算子があ りますが、この配列の機能の主たる推進力はモノリシックなものです。

配列は標準プレリュードには含まれていません。この標準ライブラリには配列演 算が含まれています。配列を使用するモジュールでは Array モジュー ルをインポートしなくてはなりません。

13.1  インデックス型

Ix ライブラリは配列インデックスの型クラスを定義しています。

class  (Ord a) => Ix a  where
    range       :: (a,a) -> [a]
    index       :: (a,a) a -> Int
    inRange     :: (a,a) -> a -> Bool

IntIntegerCharBool および Ix の組型についてインスタンス宣言がなされています。さらに、列挙 型や組型に対してはインスタンスが自動的に導出されます。プリミティブ型を 1 次元インデックスとみなし、組を多次元長方行列のインデックスとみなします。 クラス Ix の各演算の第一引数はインデックスのペアであることに注 目して下さい。これらは典型的には配列の 境界 (最初と最後のインデッ クス)です。たとえば、Int のインデックスをもつ、0-オリジンの要 素数 10 の境界は (0,9) となります。また、1-オリジンの 100 × 100 の行列の境界は ((1,1),(100,100)) となります。(他の多くの言 語ではこのような境界は 1:100, 1:100 のように書きます。しか し、ここに示した形式のほうが型システムにピッタリきます。なぜなら、それぞ れの境界が一般のインデックスと同じ型になるからです。)

range 演算は境界のペアを引数として、その間にあるインデックスの 順序リストを生成します。例を以下にしめします。

range (0,4) => [0,1,2,3,4]

range ((0,0),(1,2)) => [(0,0), (0,1), (0,2), (1,0), (1,1), (1,2)]

inRange 述語はインデックスが与えられ境界のペアの間に入っている かどうかを判定します。最後に index 演算は配列の特定の要素を特定 するのに必要な演算です。境界のペアと範囲内にあるインデックスを与えると、 この演算は、そのインデックスが 0-オリジンで何番目のインデックスかを返し ます。たとえば、次のようになります。

index (1,9) 2 => 1

index ((0,0),(1,2)) (1,1) => 4

13.2  配列生成

Haskell のモノリシックな配列生成関数は境界のペアとインデックスと値のペア (連想リスト)のリストから配列を生成します。

array                   :: (Ix a) => (a,a) -> [(a,b)] -> Array a b

ここで、1 から 100 までの数の自乗の配列の例をあげましょう。

squares                 =  array (1,100) [(i, i*i) | i <- [1..100]]

この配列の式は連想リストに対するリストの内包表記の典型的な使用例です。実 際、この使用例は、Id 言語[6]の配列の内包表記にたいへん よく似ています。

配列のインデックスによる指定には中置演算子 ! を使います。また、 境界は関数 bounds を使ってとりだすことができます。

squares!7 => 49

bounds squares => (1,100)

この例を、各インデックスに対して適用する関数と境界とをパラメータ化するこ とで一般化することができます。

mkArray                 :: (Ix a) => (a -> b) -> (a,a) -> Array a b
mkArray f bnds          =  array bnds [(i, f i) | i <- range bnds]

こうすれば、squaresmkArray (\i -> i * i) (1,100) と定義することができます。

多くの配列は再帰的に定義します。すなわち、いくつかの要素の値は別の要素の 値に依存しています。たとえば、フィボナッチ数の配列を返す関数をみましょう。

fibs    :: Int -> Array Int Int
fibs n  =  a  where a = array (0,n) ([(0, 1), (1, 1)] ++ 
                                     [(i, a!(i-2) + a!(i-1)) | i <- [2..n]])

こういった再帰のをもうひとつあげると、n × n のウェーブフロント 行列です。これは、その最初の行の要素と最初の列の要素がすべて 1 で、その他の要素はその左側と左上側と上側との和であるような行列です。

wavefront       :: Int -> Array (Int,Int) Int
wavefront n     =  a  where
                   a = array ((1,1),(n,n))
                        ([((1,j), 1) | j <- [1..n]] ++
                         [((i,1), 1) | i <- [2..n]] ++
                         [((i,j), a!(i,j-1) + a!(i-1,j-1) + a!(i-1,j))
                                     | i <- [2..n], j <- [2..n]])

このウェーブフロント行列は並列実装がゆえに、反復命令とよばれ、計算が最初 の行と列から並列に始まり、左上から右下へ楔形に計算がすすみます。しかし、 計算の順序が連想リストによって指定されているわけではないとういことに注目 することが重要です。

いまあげた例にかぎれば、対象の配列の各インデックスに対して、対応する配列 の境界内にあるインデックスに対してのみ、唯一の連想リストを与えました。実 際、一般にいって、配列を完全に定義するにはこのようにしなければなりません。 インデックス境界を越える連想リストはエラーを引き起こします。しかしながら、 もしインデックスがないか、あるいは、2 回以上出現する場合は即座にはエラー にはなりません。しかし、配列の当該のインデックスの値が未定義になりますの で、そのインデックスの場所の値を参照しようとしたときにエラーとなります。

13.3  累積

単一のインデックスに対応する複数の値を合成する方法を指定することで、イン デックスが連想リスト中で 1 度しか出現してはいけないという制限を緩和する ことができます。この結果のことを累積配列( accumulated array )と呼びます。

accumArray :: (Ix a) -> (b -> c -> b) -> b -> (a,a) -> [Assoc a c] -> Array a b

accumArray の第一引数は累積関数( accumulating function )です。第二引数は初期値(配列の各引数に対して同じ値)です。の こりの引数は境界と連想リストで、これは array 関数とおなじもので す。典型的な累積関数は (+) で初期値は 0 です。たとえば、次の関 数は境界のペアと、(インデックス型の)値のリストを引数としてとり、ヒストグ ラム、すなわち、境界内での各値の出現頻度の表を生成します。

hist            :: (Ix a, Integral b) => (a,a) -> [a] -> Array a b
hist bnds is    =  accumArray (+) 0 bnds [(i, 1) | i <- is, inRange bnds i]

区間 [a,b) における計数をし、10を1つにカウントすると、次のように なります。

decades         :: (RealFrac a) => a -> a -> [a] -> Array Int Int
decades a b     =  hist (0,9) . map decade
                   where decade x = floor ((x - a) * s)
                         s        = 10 / (b - a)

13.4  漸進更新

モノリシックな配列の生成関数に加えて、Haskell では漸進的な配列 の更新関数があります。これは中置演算子 // を書くことで実現しま す。最も単純な場合としては、配列 ai 番目の要素を v に更新するのは、a // [(i, v)] のよう に書きます。(//) の左引数に角括弧が使用されている理由は、この引 数が連想リストであるからです。この連想リストは通常、この配列のインデック スの適切な部分集合を含みます。

(//)            :: (Ix a) => Array a b -> [(a,b)] -> Array a b

array 関数と同様に、値が定義されるためには、それに対応する連想 リスト中のインデックスは、唯一でなければなりません。たとえば、次の例は、 行列のふたつの行を入れ替える関数です。

swapRows :: (Ix a, Ix b, Enum b) => a -> a -> Array (a,b) c -> Array (a,b) c
swapRows i i' a =  a // ([((i ,j), a!(i',j)) | j <- [jLo..jHi]] ++
                         [((i',j), a!(i ,j)) | j <- [jLo..jHi]])
                   where ((iLo,jLo),(iHi,jHi)) = bounds a

ここでの j インデックスの同じリスト上のふたつの別々のリスト内包 表記の連結は少し効率の悪いものです。命令型言語のループを二つ書くようなも のです。案ずることはありません。Haskell ではループの融合最適化と同じこと が可能なのです。

swapRows i i' a =  a // [assoc | j <- [jLo..jHi],
                                 assoc <- [((i ,j), a!(i',j)),
                                           ((i',j), a!(i, j))] ]
                   where ((iLo,jLo),(iHi,jHi)) = bounds a

13.5  例:行列の積

Haskell の配列の紹介をよく知られた行列の積の例でしめくくりましょう。一般 的な関数をひとつ定義するために多重定義の長所を利用します。行列の要素の乗 法と加法しか必要ではありませんので、あれこれやろうとしなければ、あらゆる 数値型の行列の乗算をする関数を手にいれるだけです。さらに、(!) を適用し、インデックスへ Ix を作用させるときに十分注意すれば、 インデックス型に対しても一般性を得ます。事実、4 つの行と列のインデックス の型は同じである必要がありません。しかしながら、はなしを単純にするために 左側の行列の列のインデックスの型と右側の行列の行のインデックスの型は同じ で、かつ、境界も同じであるとします。

matMult         :: (Ix a, Ix b, Ix c, Num d) =>
                   Array (a,b) d -> Array (b,c) d -> Array (a,c) d
matMult x y     =  array resultBounds
                         [((i,j), sum [x!(i,k) * y!(k,j) | k <- range (lj,uj)])
                                       | i <- range (li,ui),
                                         j <- range (lj',uj') ]
        where ((li,lj),(ui,uj))         =  bounds x
              ((li',lj'),(ui',uj'))     =  bounds y
              resultBounds
                | (lj,uj)==(li',ui')    =  ((li,lj'),(ui,uj'))
                | otherwise             = error "matMult: incompatible bounds"

余談ですが、命令型言語でふつうにつかわれる定式化により近い表現になるよう に accumArray を用いて matMult を定義することも可能で す。

matMult x y     =  accumArray (+) 0 resultBounds
                              [((i,j), x!(i,k) * y!(k,j))
                                      | i <- range (li,ui),
                                        j <- range (lj',uj')
                                        k <- range (lj,uj)  ]
        where ((li,lj),(ui,uj))         =  bounds x
              ((li',lj'),(ui',uj'))     =  bounds y
              resultBounds
                | (lj,uj)==(li',ui')    =  ((li,lj'),(ui,uj'))
                | otherwise             = error "matMult: incompatible bounds"

この関数を sum(*) を関数パラメータにして高階化する ことで、さらに一般化をはかることができます。

genMatMult      :: (Ix a, Ix b, Ix c) =>
                   ([f] -> g) -> (d -> e -> f) ->
                   Array (a,b) d -> Array (b,c) e -> Array (a,c) g
genMatMult sum' star x y  =
      array resultBounds
            [((i,j), sum' [x!(i,k) `star` y!(k,j) | k <- range (lj,uj)])
                                 | i <- range (li,ui),
                                   j <- range (lj',uj') ]
        where ((li,lj),(ui,uj))         =  bounds x
              ((li',lj'),(ui',uj'))     =  bounds y
              resultBounds
                | (lj,uj)==(li',ui')    =  ((li,lj'),(ui,uj'))
                | otherwise             = error "matMult: incompatible bounds"

APL 好きならつぎのような関数がとても便利なことがわかるでしょう。

genMatMult maximum (-)
genMatMult and (==)

これらのうち最初の方は、引数が数値行列です。そして、その結果の行列の (i,j) 番目の要素が、対応する i 番目の行と j 番目の列の要素の間の最大差異となります。ふたつめは、引数は同値類の型で、 結果は真理値行列になります。この行列の (i,j) 要素は第一引数の i 番目の行と第二引数の j 番目の列がベクトルとして同値 であるとき、そのときに限り True になります。

genMatMult の要素の型はすべて同一である必要はなく、単にこの関数 の引数 star として適切な型であればよいだけです。また、ひとつめ の列のインデックスとふたつめの行のインデックスが同一でなければならない、 という要請を落とせば、もっと一般化することができます。あきらかに、ふたつ の行列は、はじめの行列の列数とあとの行列の行数がおなじであるかぎり、適合 可能であると考えることができます。読者のみなさんはもっと一般性のある版を 導出したいと思われることでしょう。(ヒント:長さを決定するのに index 演算を使用すること。)


A Gentle Introduction to Haskell, Version 98
back next top