Namaran

Code daily. Without assist.

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. 位置を持つ実装では、1つ分の場所を空けたまま (w + 1) `mod` cap == r なら満杯とするか、要素の数を別に持つのが定番です。通算の回数を持つ書き方で Int があふれるのは、2の63乗回ほど書き込んだ後です。