今回は Haskell の「配列 (Array)」について説明します。Haskell は純粋な関数型言語なので、変数の値を書き換えることはできません。また、同じ引数で関数を呼び出せば、計算結果はいつも同じ値になります。これを「参照透明性」と呼びます。Haskell の配列は大きく分けると二種類 [*1] あって、ひとつは参照透明性を守る Array (immutable-array) 型、もう一つは参照透明性を守らない MArray (mutable-array) 型です。
どちらのデータ型も、データの参照は O(1) で行うことができます。Array の場合、データの更新は要素数を N とすると O(N) に比例する時間がかかります。つまり、元の配列を書き換えるのではなく、データを更新した新しい配列を作るわけです。これに対し、MArray は配列を直接書き換えるので、データの更新も O(1) で行うことができます。ただし、副作用を伴うので純粋な関数の世界で使うことはできません。
具体的には、IO モナドの中で専用の配列 (IOArray) を使うことになります。また、IO モナドのほかに ST モナドの中でも MArray を使用することができますが、本稿では取り上げません。関数型言語としては不純な機能なのですが、問題によっては配列を使った方が簡単にプログラムできる場合もあります。
最初に Array (immutable-array) 型の配列について説明します。Array 型を操作する関数はモジュール Data.Array に定義されています。配列の生成は関数 array を使います。array の型を示します。
array :: Ix i => (i, i) -> [(i, e)] -> Array i e
配列のデータ型は Array i e で、i が添字を表すデータ型、e が配列に格納されるデータ型です。Ix は添字を表す型クラスです。Ix のインスタンスであれば、整数値以外のデータでも添字として使用することができます。:info コマンドで Ix を調べると次のように表示されます。
ghci> :m Data.Array
ghci> :i Ix
type Ix :: * -> Constraint
class Ord a => Ix a where
range :: (a, a) -> [a]
index :: (a, a) -> a -> Int
GHC.Ix.unsafeIndex :: (a, a) -> a -> Int
inRange :: (a, a) -> a -> Bool
rangeSize :: (a, a) -> Int
GHC.Ix.unsafeRangeSize :: (a, a) -> Int
{-# MINIMAL range, (index | unsafeIndex), inRange #-}
-- Defined in ‘GHC.Ix’
instance Ix () -- Defined in ‘GHC.Ix’
instance (Ix a, Ix b) => Ix (a, b) -- Defined in ‘GHC.Ix’
instance (Ix a1, Ix a2, Ix a3) => Ix (a1, a2, a3)
-- Defined in ‘GHC.Ix’
instance (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1, a2, a3, a4)
-- Defined in ‘GHC.Ix’
instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) =>
Ix (a1, a2, a3, a4, a5)
-- Defined in ‘GHC.Ix’
instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6) =>
Ix (a1, a2, a3, a4, a5, a6)
-- Defined in ‘GHC.Ix’
instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6, Ix a7) =>
Ix (a1, a2, a3, a4, a5, a6, a7)
-- Defined in ‘GHC.Ix’
instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6, Ix a7,
Ix a8) =>
Ix (a1, a2, a3, a4, a5, a6, a7, a8)
-- Defined in ‘GHC.Ix’
instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6, Ix a7, Ix a8,
Ix a9) =>
Ix (a1, a2, a3, a4, a5, a6, a7, a8, a9)
-- Defined in ‘GHC.Ix’
instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6, Ix a7, Ix a8,
Ix a9, Ix aA) =>
Ix (a1, a2, a3, a4, a5, a6, a7, a8, a9, aA)
-- Defined in ‘GHC.Ix’
instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6, Ix a7, Ix a8,
Ix a9, Ix aA, Ix aB) =>
Ix (a1, a2, a3, a4, a5, a6, a7, a8, a9, aA, aB)
-- Defined in ‘GHC.Ix’
instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6, Ix a7, Ix a8,
Ix a9, Ix aA, Ix aB, Ix aC) =>
Ix (a1, a2, a3, a4, a5, a6, a7, a8, a9, aA, aB, aC)
-- Defined in ‘GHC.Ix’
instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6, Ix a7, Ix a8,
Ix a9, Ix aA, Ix aB, Ix aC, Ix aD) =>
Ix (a1, a2, a3, a4, a5, a6, a7, a8, a9, aA, aB, aC, aD)
-- Defined in ‘GHC.Ix’
instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6, Ix a7, Ix a8,
Ix a9, Ix aA, Ix aB, Ix aC, Ix aD, Ix aE) =>
Ix (a1, a2, a3, a4, a5, a6, a7, a8, a9, aA, aB, aC, aD, aE)
-- Defined in ‘GHC.Ix’
instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6, Ix a7, Ix a8,
Ix a9, Ix aA, Ix aB, Ix aC, Ix aD, Ix aE, Ix aF) =>
Ix (a1, a2, a3, a4, a5, a6, a7, a8, a9, aA, aB, aC, aD, aE, aF)
-- Defined in ‘GHC.Ix’
instance Ix Bool -- Defined in ‘GHC.Ix’
instance Ix Char -- Defined in ‘GHC.Ix’
instance Ix Int -- Defined in ‘GHC.Ix’
instance Ix Integer -- Defined in ‘GHC.Ix’
instance Ix Ordering -- Defined in ‘GHC.Ix’
instance Ix a => Ix (Solo a) -- Defined in ‘GHC.Ix’
instance Ix Word -- Defined in ‘GHC.Ix’
整数値以外でも Char, Bool, タプルが Ix のインスタンスです。Array の場合、タプルを使って多次元配列を表すことができます。array の第 1 引数は添字の下限値と上限値を格納したタプルで、第 2 引数は添字とデータ (初期値) を格納した連想リストです。
簡単な使用例を示します。
ghci> a = array (0, 3) [(0, 0), (1, 10), (2, 20), (3, 30)] ghci> a array (0,3) [(0,0),(1,10),(2,20),(3,30)]
配列のデータは演算子 ! を使って参照することができます。型を示します。
(!) :: Ix i => Array i e -> i -> e
簡単な実行例を示します。
ghci> a
array (0,3) [(0,0),(1,10),(2,20),(3,30)]
ghci> a ! 0
0
ghci> a ! 1
10
ghci> a ! 2
20
ghci> a ! 3
30
ghci> a ! 4
*** Exception: Ix{Integer}.index: Index (4) out of range ((0,3))
範囲外の添字を与えるとエラーになります。また、要素の初期値を省略しても配列は生成されますが、その要素にアクセスするとエラーになります。
ghci> b = array (0, 3) [(0, 0), (1, 10), (3, 30)] ghci> b ! 0 0 ghci> b ! 1 10 ghci> b ! 2 *** Exception: (Array.!): undefined array element
添字は関数 range で生成することができます。簡単な使用例を示します。
ghci> range (1, 10) [1,2,3,4,5,6,7,8,9,10] ghci> range ((1, 1), (5, 5)) [(1,1),(1,2),(1,3),(1,4),(1,5),(2,1),(2,2),(2,3),(2,4),(2,5),(3,1),(3,2),(3,3), (3,4),(3,5),(4,1),(4,2),(4,3),(4,4),(4,5),(5,1),(5,2),(5,3),(5,4),(5,5)]
配列の更新は演算子 // を使います。型を示します。
(//) :: Ix i => Array i e -> [(i, e)] -> Array i e
更新する添字とデータは連想リストで指定します。Array の更新には時間がかかるので、複数のデータを連想リストで指定できるようになっています。
簡単な実行例を示します。
ghci> a array (0,3) [(0,0),(1,10),(2,20),(3,30)] ghci> c = a // [(1,100), (3,300)] ghci> c array (0,3) [(0,0),(1,100),(2,20),(3,300)] ghci> a array (0,3) [(0,0),(1,10),(2,20),(3,30)]
配列 a の 1 番目と 3 番目の要素を演算子 // で更新します。その結果、変数 c には更新された配列が格納されますが、変数 a の配列は更新されていません。このように、演算子 // は配列を破壊的に更新するのではなく、値を更新した新しい配列を生成します。
ここで、Data.Array に用意されている関数をいくつか紹介しましょう。関数 listArray はリストの要素を順番に配列に格納します。
listArray :: Ix i => (i, i) -> [e] -> Array i e
ghci> listArray (0, 3) [1,2,3,4] array (0,3) [(0,1),(1,2),(2,3),(3,4)] ghci> listArray (0, 3) [1,2,3] array (0,3) [(0,1),(1,2),(2,3),(3,*** Exception: (Array.!): undefined array element ghci> listArray (0, 3) [1,2,3,4,5] array (0,3) [(0,1),(1,2),(2,3),(3,4)]
リストの要素数が配列の大きさに満たない場合はエラーになります。余った要素は捨てられます。
配列の添字の範囲は関数 bounds で求めることができます。
bounds :: Ix i => Array i e -> (i, i)
ghci> a = listArray (0,3) [1,2,3,4] ghci> a array (0,3) [(0,1),(1,2),(2,3),(3,4)] ghci> bounds a (0,3)
関数 elems は配列の要素をリストに格納して返します。関数 assocs は配列を連想リストに変換します。
elems :: Ix i => Array i e -> [e] assocs :: Ix i => Array i e -> [(i, e)]
ghci> a array (0,3) [(0,1),(1,2),(2,3),(3,4)] ghci> elems a [1,2,3,4] ghci> assocs a [(0,1),(1,2),(2,3),(3,4)]
関数 accumArray は配列の初期値と連想リスト (添字と値) を指定し、配列の値と連想リストの値に関数を適用して、その結果を配列に格納します。連想リストには同じ添字が複数あってもかまいません。その添字に対して関数を繰り返し適用します。
accumArray の型を示します。
accumArray :: Ix i => (e -> a -> e) -> e -> (i, i) -> [(i, a)] -> Array i e
第 1 引数が関数、第 2 引数が配列の初期値、第 3 引数が配列の大きさ、第 4 引数が連想リストです。型変数 e が配列の要素の型、型変数 a が連想リストの値の型になります。
簡単な使用例を示します。
ghci> accumArray (+) 0 (0,3) [(0,1),(1,2),(2,3),(3,4)] array (0,3) [(0,1),(1,2),(2,3),(3,4)] ghci> accumArray (+) 0 (0,3) [(0,1),(1,2),(0,3),(1,4)] array (0,3) [(0,4),(1,6),(2,0),(3,0)]
関数が + で初期値が 0 なので、配列の値は連想リストで同じ添字の値を合計した値になります。最初の例は同じ添字がないので、連想リストの値がそのまま配列の値になります。次の例では、添字 0 と 1 が 2 つずつあるので、その合計値 4 と 6 が 0 番目と 1 番目の値になります。2, 3 番目の値は初期値 0 のままです。
次は、配列の応用例として「二分探索 (バイナリサーチ：binary searching)」を例題として取り上げます。線形探索の実行時間は要素数 N に比例するので、数が多くなると時間がかかるようになります。これに対し二分探索は log2 N に比例する時間でデータを探すことができます。ただし、探索するデータはあらかじめ昇順に並べておく必要があります。つまり、二分探索は最初にデータをソートしておかないといけないので、線形探索に比べて準備に時間がかかります。
二分探索の動作を下図に示します。
[11 22 33 44 55 66 77 88 99] key は 66
↑ 66 > 55 後半を探す
11 22 33 44 55 [66 77 88 99] 88 > 66 前半を探す
↑
11 22 33 44 55 [66 77] 88 99 77 > 66 前半を探す
↑
11 22 33 44 55 [66] 77 88 99 66 = 66 発見
↑
図 : 二分探索
二分探索は探索する区間を半分に分割しながら調べていきます。キーが 66 の場合を考えてみましょう。まず区間の中央値 55 とキーを比較します。データが昇順にソートされている場合、66 は中央値 55 より大きいので区間の前半を調べる必要はありません。したがって、後半部分だけを探索すればいいのです。
あとは、これと同じことを後半部分に対して行います。最後には区間の要素が一つしかなくなり、それとキーが一致すれば探索は成功、そうでなければ探索は失敗です。ようするに、探索するデータ数が 1 / 2 ずつ減少していくわけです。
上図の場合、線形探索ではデータの比較が 6 回必要になりますが、二分探索であれば 4 回で済みます。また、データ数が 1,000,000 個になったとしても、二分探索を使えば高々 20 回程度の比較で探索を完了することができます。
二分探索は要素をランダムアクセスすることになるので、リストには不向きのアルゴリズムです。そこで、配列からデータを二分探索するプログラムを作ってみましょう。二分探索は簡単にプログラムできます。次のリストを見てください。
リスト : 二分探索
bsearch :: Ord a => a -> Array Int a -> Bool
bsearch x ary = iter low high
where
(low, high) = bounds ary
iter low high
| low > high = False
| otherwise = let mid = low + (high - low) `div` 2
y = ary ! mid
in if x == y then True
else if x < y then iter low (mid - 1)
else iter (mid + 1) high
関数 bsearch は配列 ary の中から x と等しい要素を二分探索します。配列の添字は Int に限定するので、型は Array Int a になります。実際の処理は局所関数 iter で行います。引数 low と high で探索する配列の範囲を指定します。bounds で ary の範囲を求め、それを iter に渡します。
low が high よりも大きくなった場合、x と等しい要素は見つからなかったので False を返します。そうでなければ、区間の中央の位置を求めて変数 mid にセットし、mid の位置にある要素を演算子 ! で取り出して変数 y にセットします。
x と y が等しい場合は True を返します。x < y の場合、配列の前半部分を探索するため iter low (mid - 1) を呼び出します。x > y の場合は後半部分を調べるため iter (mid + 1) high を呼び出します。
これでプログラムは完成です。簡単な実行例を示しましょう。
ghci> a = array (0,9) [(x, x*11) | x <- [0..9]] :: Array Int Int ghci> a array (0,9) [(0,0),(1,11),(2,22),(3,33),(4,44),(5,55),(6,66),(7,77),(8,88),(9,99)] ghci> bsearch 55 a True ghci> bsearch 50 a False ghci> bsearch 0 a True ghci> bsearch 99 a True ghci> bsearch 100 a False
二分探索はデータを高速に探索することができますが、あらかじめデータをソートしておく必要があります。このため、二分探索はプログラムの実行中にデータを登録し、同時に探索も行うという使い方には向いていません。途中でデータを追加して探索も行う場合は、他の高速な探索アルゴリズムを検討してみてください。
次は MArray (mutable-array) 型の配列について説明します。MArray 型を操作する関数はモジュール Data.MArray に定義されていますが、実際に IO モナドで使用する場合はモジュール Data.Array.IO をインポートします。配列のデータ型は IOArray i e で、i が添字を表す型変数、e が配列に格納する値の型変数です。
配列の生成は関数 newArray を使います。newArray の型を示します。
newArray :: (Ix i, MArray a e m) => (i, i) -> e -> m (a i e) newArray_ :: (Ix i, MArray a e m) => (i, i) -> m (a i e)
MArray の型変数 m はモナドを表します。生成される配列の型は (a i e) で、IOArray の場合は a が IOArray、i が添字の型、e が要素の型で、生成された配列は IO に格納されて返されます。第 1 引数が配列の大きさ、第 2 引数が要素の初期値です。関数 newArray_ は初期値の指定を省略したもので、このまま要素にアクセスするとエラーになります。
データの参照と更新は関数 readArray と writeArray で行います。型を示します。
readArray :: (Ix i, MArray a e m) => a i e -> i -> m e writeArray :: (Ix i, MArray a e m) => a i e -> i -> e -> m ()
第 1 引数は配列、第 2 引数は添字です。readArray の場合、値はモナド m に格納されて返されます。writeArray の第 3 引数が更新する値です。
それでは、簡単な使用例を示します。
ghci> :m + Data.Array.IO ghci> a <- newArray (0,9) 0 :: IO (IOArray Int Int) ghci> readArray a 0 0 ghci> writeArray a 0 10 ghci> readArray a 0 10 ghci> b <- newArray_ (0,9) :: IO (IOArray Int Int) ghci> readArray b 0 *** Exception: MArray: undefined array element ghci> writeArray b 0 10 ghci> readArray b 0 10
インタプリタ ghci の対話モードは do 構文の <- をそのまま利用することができます。newArray で配列を生成するときは型の指定が必要になることがあります。初期値に 0 を指定しているので、readArray で配列 a の 0 番目の要素を求めると値は 0 になります。次に、writeArray で 0 番目の要素を 10 に書き換えます。readArray で再度 0 番目の要素を参照すると 10 になり、配列 a の値が書き換えられていることがわかります。
newArray_ の場合、配列は初期化されないことに注意してください。たとえば、配列 b の 0 番目の要素を readArray で求めるとエラーになります。次に、writeArray で b の 0 番目の要素を 10 にセットします。そして、readArray で 0 番目の要素を参照すると、エラーにならずに 10 となります。
ここで、Data.MArray に用意されている関数をいくつか紹介しましょう。関数 getBounds は配列の大きさを求めます。
getBounds :: (Ix i, MArray a e m) => a i e -> m (i, i)
ghci> a <- newArray (0,9) 0 :: IO (IOArray Int Int) ghci> getBounds a (0,9)
関数 newListArray はリストから配列を生成します。
newListArray :: (Ix i, MArray a e m) => (i, i) -> [e] -> m (a i e)
ghci> b <- newListArray (0,9) [1..10] :: IO (IOArray Int Int) ghci> readArray b 0 1 ghci> readArray b 5 6 ghci> readArray b 9 10 ghci> c <- newListArray (0,9) [1..5] :: IO (IOArray Int Int) ghci> readArray c 9 *** Exception: MArray: undefined array element ghci> readArray c 5 *** Exception: MArray: undefined array element ghci> readArray c 4 5
リストの要素が足りない場合、配列はその分だけ初期化されません。リストの要素が多い場合、余分な値は捨てられます。
配列用のマップ関数もあります。
mapArray :: (Ix i, MArray a e m, MArray a e' m) => (e' -> e) -> a i e' -> m (a i e)
ghci> d <- newListArray (0,4) [1..5] :: IO (IOArray Int Int) ghci> e <- mapArray (*2) d ghci> readArray e 0 2 ghci> readArray e 1 4 ghci> readArray e 2 6 ghci> readArray e 3 8 ghci> readArray e 4 10
getElems は配列のデータをリストに格納して返します。getAssoc は配列を連想リストに変換します。どちらの場合も、返り値はモナド (IOArray であれば IO) に格納されます。
getElems :: (Ix i, MArray a e m) => a i e -> m [e] getAssocs :: (Ix i, MArray a e m) => a i e -> m [(i, e)]
ghci> f <- getElems e ghci> f [2,4,6,8,10] ghci> g <- getAssocs e ghci> g [(0,2),(1,4),(2,6),(3,8),(4,10)]
関数 freeze は mutable-array を immutable-array に変換します。逆に、関数 thaw は immutable-array を mutable-array に変換します。
freeze :: (Ix i, MArray a e m, Data.Array.Base.IArray b e) => a i e -> m (b i e) thaw :: (Ix i, MArray b e m, Data.Array.Base.IArray a e) => a i e -> m (b i e)
簡単な実行例を示します。
ghci> a <- newListArray (0,9) [1..10] :: IO (IOArray Int Int) ghci> :m + Data.Array ghci> b <- freeze a :: IO (Array Int Int) ghci> b array (0,9) [(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,10)] ghci> c <- thaw b :: IO (IOArray Int Int) ghci> readArray c 0 1 ghci> writeArray c 0 10 ghci> readArray c 0 10
それでは簡単な例題として、整数 n 以下の素数を求めるプログラムを作ってみましょう。次のリストを見てください。
リスト : エラトステネスの篩 (配列版)
import Control.Monad
import Data.Array.IO
sieve :: Int ->IO [Int]
sieve n = do
ary <- newArray (0, n `div` 2 + 1) True :: IO (IOArray Int Bool)
mapM_ (\x -> do f <- readArray ary (x `div` 2)
when f $ do delete_multiple ary x (x `div` 2))
[3, 5 .. m]
xs <- filterM (\x -> readArray ary (x `div` 2)) [3, 5 .. n]
return (2:xs)
where m = (floor . sqrt . fromIntegral) n
delete_multiple :: IOArray Int Bool -> Int -> Int -> IO ()
delete_multiple ary i j =
mapM_ (\x -> writeArray ary x False) [j+i, j+i*2 .. n `div` 2 + 1]
Bool 型の配列 ary で奇数列 (1, 3, 5, 7, ... ) を表します。True で素数を表し、素数でない場合は False に書き換えます。配列 ary は true で初期化されるので、最初はすべての数が素数ということになります。
奇数を変数 i とし、それに対応する配列 ary の添字を変数 j とすると、変数 i は 3, 5, 7, 9, ... に、それに対応する変数 j は 1, 2, 3, 4, ... になります。この場合、i の倍数に対応する j の値は j + i, j + i * 2, j + i * 3, ... になります。たとえば、3, 5, 7 の倍数は次のようになります。
i | 3 5 7 9 11 13 15 17 19 21 23 25 j | 1 2 3 4 5 6 7 8 9 10 11 12 --+------------------------------------- 3 | O 0 O 0 5 | 0 0 0 7 | 0 0
プログラムは簡単です。mapM_ で奇数 x が素数であれば、局所関数 delete_multiple で x の倍数を False に書き換えます。mapM_ に渡す奇数列の上限値は √n で十分です。この値を関数合成 floor . sqrt . fromIntegral で求め、局所変数 m にセットします。関数 fromIntegral, sqrt, floor の型を示します。
fromIntegral :: (Integral a, Num b) => a -> b sqrt :: Floating a => a -> a floor :: (Integral b, RealFrac a) => a -> b
sqrt はルートを求めます。floor は「床関数」といって、実数 x に対して x 以下の最大の整数を求めます。fromIntegral は整数を他の数値型に変換します。簡単な例を示します。
ghci> sqrt 2 1.4142135623730951 ghci> floor 2.5 2 ghci> fromIntegral 10 :: Double 10.0
when はモジュール Control.Monad に定義されている関数です。
when :: Monad m => Bool -> m () -> m ()
IO モナドの場合、when は真偽値と I/O アクションを受け取り、真の場合は I/O アクションを実行し、そうでなければ IO () を返します。when を使わない場合は、次のように記述することになります。
リスト : when を使わない場合
mapM_ (\x -> do f <- readArray ary (x `div` 2)
if f then delete_multiple ary x (x `div` 2) else return ())
[3, 5 .. m]
mapM_ で素数の倍数を削除したあと、filterM で素数を集めます。最後に、リストの先頭に 2 を追加します。
それでは実行してみましょう。
ghci> sieve 100 [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97] ghci> sieve 1000 [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103, 107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211, 223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331, 337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449, 457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587, 593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709, 719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853, 857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991, 997]