The Haskell 98 Report
top | back | next | contents | function index
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 からエクスポートされていて、 Array と Ix の両方をインポートする必要はない。
もし、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.1 は array
構成子を使用したいくつかの例を示してる。
(!) 演算子は配列の添字のところの内容を表わす。 bounds 関数は、ひとつの配列に適用すると、その境界対を返す。 関数 indices、elems および assocs は ひとつの配列に適用されると、それぞれ、インデックス、要素、あるいは インデックスと要素連想対のインデックス順にならべたリストを返す。 配列は関数 listArray を使って境界対とインデックス順に ならべた値のリストから構築することもできる。
もし、下界が上界よりも大きいような次元がひとつでもあれば、その配列 自身は正当だが空である。空の配列へのインデックスよるアクセスは、常 に配列境界エラーになる。bounds はその場合でも配列が構築さ れたときの境界対となる。
もう一つの配列作成関数は 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 は連想リスト中の
インデックスに対してだけではなく値に対しても正格になる。したがって、
一般の配列とはちがって、蓄積配列は一般には再帰にしてはならない。
演算子 (//) は配列をひとつと対のリストとをとり、右側の 連想リストによって更新された部分以外は左側の配列と同じ配列を返す。 ( array 関数のときと同様、連想リスト中のインデックスは 更新される要素が定義されるためには、唯一でなければならない。) たとえば、もし m がインデックスが 1 から始まる n × n の行列であるとすると、 m//[((i,i), 0) | i <- [1..n]] は対角要素が 0 であるという以外は元の行列と同じものである。
accum f は一つの配列と一つの連想リストをとり、
リストからの対を蓄積関数 f を用いて配列に蓄積する。
したがって、accumArray は accum を使って
以下のように定義することができる。
accumArray f z b = accum f (array b [(i, z) | i <- range b])
二つの関数 fmap と ixmap は既存の配列から新しい 配列を導出する。これらの関数は元の配列が内蔵している写像について、 それぞれ右の関数と左の関数を合成する関数と考えられる。 fmap 関数は配列の要素の値を変換し、ixmap は 配列のインデックスの変換を可能にする。図 16.2 にその例を示す。
導出配列の例 |
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