2026-10-05
Queue.hs
import Data.Array
data Queue = Queue Int Int (Array Int Char)
push :: Char -> Queue -> Maybe Queue
push x (Queue r w buf)
| w - r == cap = Nothing
| otherwise = Just (Queue r ((w + 1) `mod` cap) (buf // [(w `mod` cap, x)]))
where
cap = rangeSize (bounds buf)
toList :: Queue -> String
toList (Queue r w buf) = [buf ! (i `mod` cap) | i <- [r .. w - 1]]
where
cap = rangeSize (bounds buf)
main :: IO ()
main = print (toList <$> (push 'a' emptyQ >>= push 'b' >>= push 'c'))
where
emptyQ = Queue 0 0 (listArray (0, 1) "..")
Queue r w buf は、配列 buf を輪のように使う容量固定のキューで、r は次に取り出す位置、w は次に書き込む位置です。push は、キューが満杯なら Nothing を返すつもりです。容量2の空のキューに 'a' 'b' 'c' を順に入れると、いまは Just "c" が出ます。本来は3つ目で満杯になるので、Nothing が出るはずです。
Answer
Wrong
| w - r == cap = Nothing
| otherwise = Just (Queue r ((w + 1) `mod` cap) (buf // [(w `mod` cap, x)]))
書き込むたびに w を mod cap で巻き戻しているので、w は0から容量−1までの値しか取りません。容量2で 'a' を書くと w は1、'b' を書くと 2 `mod` 2 で0に戻り、r と同じ0になります。
このとき満杯の判定 w - r == cap は 0 == 2 で成り立たず、toList が読む範囲 [r .. w - 1] も [0 .. -1] で空です。2つ入ったキューが空に見えるので、'c' は受け入れられて位置0の 'a' を上書きし、w が1になったキューから読めるのは "c" だけになります。
Right
| otherwise = Just (Queue r (w + 1) (buf // [(w `mod` cap, x)]))
r と w を、取り出しと書き込みの通算の回数として増やし続け、配列に触るときだけ mod cap で位置に直します。これで w - r がいつも入っている要素の数になり、空は w == r、満杯は w - r == cap と区別できます。'b' を書いた後は w が2になって満杯と判定され、3つ目は Nothing です。
位置そのものを持つと、空のときも満杯のときも2つの位置が一致してしまい、区別する手がかりが残りません1。
- 位置を持つ実装では、1つ分の場所を空けたまま
(w + 1) `mod` cap == rなら満杯とするか、要素の数を別に持つのが定番です。通算の回数を持つ書き方でIntがあふれるのは、2の63乗回ほど書き込んだ後です。