The Haskell 98 Report
top | back | next | contents | function index


16  配列


module  Array ( 
        module Ix,  -- export all of Ix for convenience
        Array, array, listArray, (!), bounds, indices, elems, assocs, 
        accumArray, (//), accum, ixmap ) where

import Ix

infixl 9  !, //

data  (Ix a)    => Array a b = ... -- Abstract

array           :: (Ix a) => (a,a) -> [(a,b)] -> Array a b
listArray       :: (Ix a) => (a,a) -> [b] -> Array a b
(!)             :: (Ix a) => Array a b -> a -> b
bounds          :: (Ix a) => Array a b -> (a,a)
indices         :: (Ix a) => Array a b -> [a]
elems           :: (Ix a) => Array a b -> [b]
assocs          :: (Ix a) => Array a b -> [(a,b)]
accumArray      :: (Ix a) => (b -> c -> b) -> b -> (a,a) -> [(a,c)]
                             -> Array a b
(//)            :: (Ix a) => Array a b -> [(a,b)] -> Array a b
accum           :: (Ix a) => (b -> c -> b) -> Array a b -> [(a,c)]
                             -> Array a b
ixmap           :: (Ix a, Ix b) => (a,a) -> (a -> b) -> Array b c
                             -> Array a c

instance                            Functor (Array a) where ...
instance  (Ix a, Eq b)           => Eq   (Array a b)  where ...
instance  (Ix a, Ord b)          => Ord  (Array a b)  where ...
instance  (Ix a, Show a, Show b) => Show (Array a b)  where ...
instance  (Ix a, Read a, Read b) => Read (Array a b)  where ...

Haskell にはインデックス可能な配列が備わっており、これは 整数の連続した部分集合と同型での領域をもつ関数とみなすことができる。 このような制限のある関数は効率良く実装することが可能である。 特に、プログラマはその構成要素へのアクセスが十分に速いことを 期待することができる。このような実装の可能性を確かなものにするために、 配列は一般の関数としてではなくデータとしてとりあつかう。

ほとんどの配列関数はクラス Ix を含むので、この Ix モジュールは Array からエクスポートされていて、 ArrayIx の両方をインポートする必要はない。

16.1  配列の構築

もし、a があるインデックス型でかつ b が任意の型で あるとすると、a のインデックスを持ち、要素が b である配列の型は Array a b と書く。配列は関数 array によってつくりだすことが可能である。array の第一引数は境界の対である。それぞれがその配列の インデックスの型になっている。これらの境界はこの順でその配列のなかの 最小のインデックスと最大のインデックスである。例えば、1 からはじまる 長さ 10 のベクトルは、境界の対 (1,10) を持つ。また、1 から はじまる 10 × 10 の行列の境界の対は ((1,1),(10,10)) である。

array の第二引数は (インデックス, 値) の形の連想 リストである。典型的には、このリストは内包表記で表現する。連想対 (i, x) は配列のインデックス i における値が x であるという定義になっている。もし、リストのなかの インデックスに境界からはずれているものがあれば、この配列は未定義 (すなわち _|_ )となる。もし、リストのなかの連想対が同じインデックスを 持つなら、そのインデックスにおける値は未定義(すなわち、_|_ )となる。 インデックスはこれらのエラーをチェックしなければならないので、 array は境界対引数と連想リストのインデックスに関して 正格である。しかし、値に関しては非正格である。したがって、 次のような再帰は可能である。

a = array (1,100) ((1,1) : [(i, i * a!(i-1)) | i <- [2..100]])

その配列の境界内のすべてのインデックスが連想リストのなかに出現する 必要はない。しかし、連想リストにあらわれないインデックスに対応する 値は未定義(すなわち、_|_)となる。 図 16.1array 構成子を使用したいくつかの例を示してる。


-- Scaling an array of numbers by a given number:
scale :: (Num a, Ix b) => a -> Array b a -> Array b a
scale x a = array b [(i, a!i * x) | i <- range b]
    where b = bounds a

-- Inverting an array that holds a permutation of its indices
invPerm :: (Ix a) => Array a a -> Array a a
invPerm a = array b [(a!i, i) | i <- range b]
    where b = bounds a

-- The inner product of two vectors
inner :: (Ix a, Num b) => Array a b -> Array a b -> b
inner v w = if b == bounds w
then sum [v!i * w!i | i <- range b]
else error "inconformable arrays for inner product"
    where b = bounds v

配列の例

(!) 演算子は配列の添字のところの内容を表わす。 bounds 関数は、ひとつの配列に適用すると、その境界対を返す。 関数 indiceselems および assocs は ひとつの配列に適用されると、それぞれ、インデックス、要素、あるいは インデックスと要素連想対のインデックス順にならべたリストを返す。 配列は関数 listArray を使って境界対とインデックス順に ならべた値のリストから構築することもできる。

もし、下界が上界よりも大きいような次元がひとつでもあれば、その配列 自身は正当だが空である。空の配列へのインデックスよるアクセスは、常 に配列境界エラーになる。bounds はその場合でも配列が構築さ れたときの境界対となる。

16.1.1  蓄積配列

もう一つの配列作成関数は accumArray である。この関数は 与えられたインデックスが連想リスト中にあっても一つだけという制限を 緩和し、蓄積関数を使って同じインデックスをもつ連想対中の 値を蓄積する。accumArray の第一引数は蓄積関数で、第二引数は 初期値である。のこりの二つの引数は array 関数の場合と同様に 境界対と連想リストである。たとえば、いくつかのインデックス型の値の リストをあたえると、hist は指定された範囲内にある 各インデックスの出現数のヒストグラムを生成する。

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

もし蓄積関数が正格である場合、accumArray は連想リスト中の インデックスに対してだけではなく値に対しても正格になる。したがって、 一般の配列とはちがって、蓄積配列は一般には再帰にしてはならない。

16.2  配列の漸進更新

演算子 (//) は配列をひとつと対のリストとをとり、右側の 連想リストによって更新された部分以外は左側の配列と同じ配列を返す。 ( array 関数のときと同様、連想リスト中のインデックスは 更新される要素が定義されるためには、唯一でなければならない。) たとえば、もし m がインデックスが 1 から始まる n × n の行列であるとすると、 m//[((i,i), 0) | i <- [1..n]] は対角要素が 0 であるという以外は元の行列と同じものである。

accum f は一つの配列と一つの連想リストをとり、 リストからの対を蓄積関数 f を用いて配列に蓄積する。 したがって、accumArrayaccum を使って 以下のように定義することができる。

accumArray f z b = accum f (array b [(i, z) | i <- range b])

16.3  導出配列

二つの関数 fmapixmap は既存の配列から新しい 配列を導出する。これらの関数は元の配列が内蔵している写像について、 それぞれ右の関数と左の関数を合成する関数と考えられる。 fmap 関数は配列の要素の値を変換し、ixmap は 配列のインデックスの変換を可能にする。図 16.2 にその例を示す。


-- A rectangular subarray
subArray :: (Ix a) => (a,a) -> Array a b -> Array a b
subArray bnds = ixmap bnds (\i->i)

-- A row of a matrix
row :: (Ix a, Ix b) => a -> Array (a,b) c -> Array b c
row i x = ixmap (l',u') (\j->(i,j)) x where ((_,l'),(_,u')) = bounds x

-- Diagonal of a matrix (assumed to be square)
diag :: (Ix a) => Array (a,a) b -> Array a b
diag x = ixmap (l,u) (\i->(i,i)) x
       where 
         ((l,_),(u,_)) = bounds x

-- Projection of first components of an array of pairs
firstArray :: (Ix a) => Array a (b,c) -> Array a b
firstArray = fmap (\(x,y)->x)

導出配列の例

16.4  Array ライブラリ


module  Array ( 
    module Ix,  -- export all of Ix 
    Array, array, listArray, (!), bounds, indices, elems, assocs, 
    accumArray, (//), accum, ixmap ) where

import Ix
import List( (\\) )

infixl 9  !, //

data (Ix a) => Array a b = MkArray (a,a) (a -> b) deriving ()

array       :: (Ix a) => (a,a) -> [(a,b)] -> Array a b
array b ivs =
    if and [inRange b i | (i,_) <- ivs]
        then MkArray b
                     (\j -> case [v | (i,v) <- ivs, i == j] of
                            [v]   -> v
                            []    -> error "Array.!: \
                                           \undefined array element"
                            _     -> error "Array.!: \
                                           \multiply defined array element")
        else error "Array.array: out-of-range array association"

listArray             :: (Ix a) => (a,a) -> [b] -> Array a b
listArray b vs        =  array b (zipWith (\ a b -> (a,b)) (range b) vs)

(!)                   :: (Ix a) => Array a b -> a -> b
(!) (MkArray _ f)     =  f

bounds                :: (Ix a) => Array a b -> (a,a)
bounds (MkArray b _)  =  b

indices               :: (Ix a) => Array a b -> [a]
indices               =  range . bounds

elems                 :: (Ix a) => Array a b -> [b]
elems a               =  [a!i | i <- indices a]

assocs                :: (Ix a) => Array a b -> [(a,b)]
assocs a              =  [(i, a!i) | i <- indices a]

(//)                  :: (Ix a) => Array a b -> [(a,b)] -> Array a b
a // new_ivs          = array (bounds a) (old_ivs ++ new_ivs)
                      where
                   old_ivs = [(i,a!i) | i <- indices a,
                                             i `notElem` new_is]
                   new_is  = [i | (i,_) <- new_ivs]

accum                 :: (Ix a) => (b -> c -> b) -> Array a b -> [(a,c)]
                                   -> Array a b
accum f               =  foldl (\a (i,v) -> a // [(i,f (a!i) v)])

accumArray            :: (Ix a) => (b -> c -> b) -> b -> (a,a) -> [(a,c)]
                                   -> Array a b
accumArray f z b      =  accum f (array b [(i,z) | i <- range b])

ixmap                 :: (Ix a, Ix b) => (a,a) -> (a -> b) -> Array b c
                                         -> Array a c
ixmap b f a           = array b [(i, a ! f i) | i <- range b]

instance  (Ix a)          => Functor (Array a) where
    fmap fn (MkArray b f) =  MkArray b (fn . f) 

instance  (Ix a, Eq b)  => Eq (Array a b)  where
    a == a' =  assocs a == assocs a'

instance  (Ix a, Ord b) => Ord (Array a b)  where
    a <= a' =  assocs a <= assocs a'

instance  (Ix a, Show a, Show b) => Show (Array a b)  where
    showsPrec p a = showParen (p > arrPrec) (
                    showString "array " .
                    showsPrec (arrPrec+1) (bounds a) . showChar ' ' .
                    showsPrec (arrPrec+1) (assocs a)                  )

instance  (Ix a, Read a, Read b) => Read (Array a b)  where
    readsPrec p = readParen (p > arrPrec)
           (\r -> [ (array b as, u) 
                  | ("array",s) <- lex r,
                    (b,t)       <- readsPrec (arrPrec+1) s,
                    (as,u)      <- readsPrec (arrPrec+1) t ])

-- Precedence of the 'array' function is that of application itself
arrPrec = 10


The Haskell 98 Report
top | back | next | contents | function index
December 2002