Haskell は純粋な関数型言語なので、関数の引数や let で定義した局所変数の値を書き換えることはできません。ところが、Haskell には値を書き換えることができるデータ型 IORef がモジュール Data.IORef に用意されています。
ただし、IORef は IO モナドの中でしか使用することができません。このほかにも、ST モナドの中で使う STRef というデータ型がありますが、本稿では取り上げません。配列や IORef を使うと、手続き型言語のように「副作用」を伴う操作を Haskell でも行うことができます。
書き換え可能な変数のデータ型は IORef a で表されます。a は型変数です。IORef a は関数 newIORef で生成します。newIORef の型を示します。
newIORef :: a -> IO (IORef a)
newIORef x は初期値が x の IORef を生成します。返り値は IO に格納されて返されます。
データの参照と更新は関数 readIORef と writeIORef で行います。IORef の値に関数を適用して値を書き換える関数 modifyIORef もあります。
readIORef :: IORef a -> IO a writeIORef :: IORef a -> a -> IO () modifyIORef :: IORef a -> (a -> a) -> IO ()
返り値は IO に格納されて返されます。簡単な使用例を示します。
ghci> :m + Data.IORef ghci> a <- newIORef 0 ghci> :t a a :: IORef Integer ghci> readIORef a 0 ghci> writeIORef a 10 ghci> readIORef a 10 ghci> modifyIORef a (*2) ghci> readIORef a 20
newIORef で初期値が 0 の IORef を生成します。この場合、変数 a の型は IORef Integer になります。readIORef で a の値を参照すると 0 になります。
次に、writeIORef で a の値を 10 に書き換えます。再度、readIORef で a の値を参照すると 10 になり、変数の値が書き換えられていることがわかります。modifyIORef で a に関数 (*2) を適用すると、変数 a の値は 10 * 2 = 20 に書き換えられます。
Haskell の場合、スタックはリストを使って簡単に実現できます。関数型言語の場合、データ構造の主役はリストですが、配列を使ってもスタックを実装することができます。実際のところ、Haskell でこのようなスタックを使うことはないと思いますが、IORef の簡単な例題ということで、ご容赦くださいませ。
配列でスタックを実現する場合、データを格納するための配列本体と、スタックのトップを表す変数が必要になります。この変数のことを「スタックポインタ (stack pointer)」と呼びます。次の図を見てください。
buffer 0 1 2 3 4 5 top
(1) [ ] 0 空の状態
(2) [ A ] 1 PUSH A
(3) [ A B ] 2 PUSH B
(4) [ A B C ] 3 PUSH C
(5) [ A B ] 2 POP => C
(6) [ A ] 1 POP => B
(7) [ ] 0 POP => A
図 : 配列によるスタックの実現
まず、配列 buffer とスタックポインタ top を用意します。top の値は 0 に初期化しておきます。データをプッシュするときは buffer の top 番目にデータを格納してから、top の値をインクリメントします。逆にポップするときは、top の値をデクリメントしてから、buffer の top 番目にあるデータを取り出します。スタックを操作するたびに、top の値は上図のように変化します。
データをプッシュしていくと、top の値は配列の大きさと等しくなります。配列はリストと違って大きさに限りがあるので、これ以上データを追加することはできません。つまり、スタックは満杯となります。したがって、データをプッシュするとき、スタックに空きがあるかチェックする必要があります。また、top の値が 0 のときはスタックが空の状態なので、ポップすることはできません。このチェックも必要です。
プログラムは次のようになります。
リスト : 配列によるスタックの実装
import Data.Array.IO
import Data.IORef
-- データ型の定義
data Stack a = S Int (IORef Int) (IOArray Int a)
-- スタックの生成
makeStack :: Int -> IO (Stack a)
makeStack n = do
buff <- newArray_ (0, n - 1)
cnt <- newIORef 0
return (S n cnt buff)
-- スタックにデータを追加する
push :: Stack a -> a -> IO ()
push (S size cnt buff) x = do
n <- readIORef cnt
if n >= size
then error "Full Stack"
else do
writeArray buff n x
writeIORef cnt (n + 1)
-- スタックからデータを取り出す
pop :: Stack a -> IO a
pop (S _ cnt buff) = do
n <- readIORef cnt
if n <= 0
then error "Empty Stack"
else do
writeIORef cnt (n - 1)
readArray buff (n - 1)
-- スタックは空か
isEmpty :: Stack a -> IO Bool
isEmpty (S _ cnt _) = do
n <- readIORef cnt
return (n == 0)
-- スタックは満杯か
isFull :: Stack a -> IO Bool
isFull (S size cnt _) = do
n <- readIORef cnt
return (n == size)
-- データ数を求める
len :: Stack a -> IO Int
len (S _ cnt _) = readIORef cnt
スタックのデータ型は Stack a とし、データ構築子を S としました。S の第 1 引数がスタックの大きさを表す整数値 (Int) で、第 2 引数がスタックポインタを表す変数です。値を書き換えるので IORef Int とします。なお、このプログラムでは、スタックポインタはスタックに格納されているデータ数を表すことになります。第 3 引数がスタック本体を表す配列です。
関数 makeStack n は大きさ n のスタックを生成して、IO に格納して返します。newArray_ で大きさ (0, n - 1) の配列を生成し、newIORef で初期値 0 の変数 (スタックポインタ) を生成し、それらを S に格納して返します。
関数 push s x はスタック s に x を追加します。最初に readIORef でスタックポインタの値を取り出して変数 n にセットします。n がスタックの大きさ size 以上であれば、スタックは満杯なのでエラーを送出します。そうでなければ、配列の n 番目の位置に writeArray で x を書き込み、writeIORef でスタックポインタの値を +1 します。
関数 pop s はスタックからデータを取り出して IO に格納して返します。最初にスタックポインタの値を取り出して変数 n にセットします。n が 0 以下であれば、スタックは空なのでエラーを送出します。そうでなければ、writeIORef でスタックポインタの値を -1 して、readArray で buff の n - 1 番目の値を取り出して返します。
isEmpty s はスタック s が空ならば True を返します。関数 isFull s はスタック s が満杯であれば True を返します。関数 len はスタックに格納されているデータの個数を返します。これらの関数は返り値を IO に格納して返すことに注意してください。
それでは簡単な実行例を示します。
ghci> a <- makeStack 10 :: IO (Stack Integer) ghci> isEmpty a True ghci> mapM_ (push a) [1..10] ghci> isEmpty a False ghci> isFull a True ghci> pop a 10 ghci> pop a 9 ghci> pop a 8 ghci> pop a 7 ghci> pop a 6 ghci> pop a 5 ghci> pop a 4 ghci> pop a 3 ghci> pop a 2 ghci> pop a 1 ghci> isEmpty a True
拙作のページ「モジュール」では、リストを使ってキュー (queue) を実現しました。キューは配列を使っても簡単に実現できます。先頭位置を示す front と末尾を示す rear を用意し、front と rear の間にあるデータをキューに格納されているデータとするのがポイントです。次の図を見てください。
0 1 2 3 4 5 6 7 8 9
rear = 0 ↓
QUEUE [ ] : QUEUE は空
front= 0 ↑
rear = 3 ↓
QUEUE [10 20 30 ] : データの追加
front= 0 ↑
rear = 3 ↓
QUEUE [10 20 30 ] : 10を取り出す
front= 1 ↑
rear = 3 ↓
QUEUE [10 20 30 ] : 20,30を取り出す
front= 3 ↑
図 : キューの動作
まずキューは空の状態で、rear, front ともに 0 です。データの追加は、rear が示す位置にデータを書き込み、rear の値をインクリメントします。データ 10, 20, 30 を追加すると、図のようにデータが追加され rear は 3 になります。このとき front は 0 のままなので、先頭のデータは 10 ということになります。
次に、データを取り出す場合、front の示すデータを取り出してから front の値をインクリメントします。この場合、front が 0 なので 10 を取り出して front の値は 1 となり、次のデータ 20 が先頭になります。データを順番に 20, 30 と取り出していくと、3 つしかデータを書き込んでいないので当然キューは空になります。このとき front は 3 になり rear と同じ値になります。このように、front と rear の値が 0 の場合だけが空の状態ではなく、front と rear の値が等しくなると、キューは空になることに注意してください。
rear, fornt ともに値は増加していく方向なので、いつかは配列の範囲をオーバーします。このため、配列を先頭と末尾がつがっているリング状と考え、rear, front が配列の範囲を超えたら 0 に戻すことにします。これを「循環配列」とか「リングバッファ」と呼びます。一般に、配列を使ってキューを実現する場合は、リングバッファとするのがふつうです。
Haskell の場合、リングバッファを使うことはほとんどないと思いますが、配列と IORef の簡単な例題ということで、実際に作ってみることにしましょう。最初に、キューを表すデータ型を定義します。
リスト : キューの定義と生成 -- データ型の定義 data Queue a = Q Int (IORef Int) (IORef Int) (IORef Int) (IOArray Int a) -- キューの生成 makeQueue :: Int -> IO (Queue a) makeQueue n = do a <- newIORef 0 b <- newIORef 0 c <- newIORef 0 d <- newArray_ (0, n - 1) return (Q n a b c d)
データ型は Queue a とし、データ構築子は Q としました。第 1 引数がキューの大きさを表す整数値 (Int) で、第 2, 3, 4 引数が front, rear, cnt を表します。cnt はキューに格納されているデータ数を表します。これらの変数は値を書き換えるので IORef Int を使っています。最後の引数がキュー本体を表す配列です。
配列を生成する関数 makeQueue も簡単です。newIORef で front, rear, cnt 用の変数を、newArray_ でキュー本体を生成し、それらを Q に格納して返すだけです。
次はデータを追加する関数 enqueue を作ります。
リスト : キューにデータを追加する
enqueue :: Queue a -> a -> IO ()
enqueue (Q size _ rear cnt buff) x = do
c <- readIORef cnt
if c >= size
then error "Full Queue"
else do
r <- readIORef rear
writeArray buff r x
writeIORef cnt (c + 1)
if r + 1 >= size
then writeIORef rear 0
else writeIORef rear (r + 1)
まず、cnt の値と readIORef で取り出して変数 c にセットします。c がキューの大きさ size 以上の場合、キューは満杯なのでエラーを送出します。そうでなければ、readIORef で rear の値を取り出して r にセットします。そして、writeArray で buff の r 番目に x を書き込み、writeIORef で cnt の値を c + 1 に書き換えます。最後に、r + 1 が size 以上になるかチェックします。その場合は rear を 0 に書き換えます。そうでなければ rear の値を +1 します。
次は、キューからデータを取り出す関数 dequeue を作ります。
リスト : キューからデータを取り出す
dequeue :: Queue a -> IO a
dequeue (Q size front _ cnt buff) = do
c <- readIORef cnt
if c <= 0
then error "Empty Queue"
else do
f <- readIORef front
x <- readArray buff f
writeIORef cnt (c - 1)
if f + 1 >= size
then writeIORef front 0
else writeIORef front (f + 1)
return x
最初に readIORef で cnt の値を取り出して変数 c にセットします。c が 0 以下であればキューは空なのでエラーを送出します。そうでなければ、front の値を readIORef で取り出して変数 f にセットし、buff の f 番目のデータを readArray で取り出して変数 x にセットします。あとは、writeIORef で cnt の値を -1 して、f + 1 が size 以上になるかチェックします。そうであれば、front の値を 0 に書き換えます。そうでなければ、front の値を +1 します。最後に、x を IO に格納して返します。
あとの関数 isEmpty, isFull, clear は簡単なので説明は省略します。プログラムリストをお読みくださいませ。
リスト : キューの操作関数 -- キューは空か isEmpty :: Queue a -> IO Bool isEmpty (Q _ _ _ cnt _) = do c <- readIORef cnt return (c == 0) -- キューは満杯か isFull :: Queue a -> IO Bool isFull (Q _ _ _ cnt _) = do c <- readIORef cnt return (c /= 0) -- キューを空にする clear :: Queue a -> IO () clear (Q _ front rear cnt _) = do writeIORef front 0 writeIORef rear 0 writeIORef cnt 0
これでプログラムは完成です。それでは、簡単な実行例を示しましょう。
ghci> a <- makeQueue 8 :: IO (Queue Integer) ghci> isEmpty a True ghci> isFull a False ghci> mapM_ (enqueue a) [1..8] ghci> isEmpty a False ghci> isFull a True ghci> dequeue a 1 ghci> dequeue a 2 ghci> dequeue a 3 ghci> dequeue a 4 ghci> dequeue a 5 ghci> dequeue a 6 ghci> dequeue a 7 ghci> dequeue a 8 ghci> isEmpty a True ghci> isFull a False
makeQueue でキューを作成して変数 a にセットします。mapM_ でキューにデータを 8 個セットします。これでキューは満杯になるので、これ以上データを追加することはできません。次に、dequeue でデータを取り出します。先に入れたデータから順番に取り出されていることがわかりますね。これでキューは空の状態になります。