haskell-ja > Archives > 2012/11/08

Queueの代数的仕様として必要なことを考えてみましょう．

まず必要なのはQueueを構成する方法です．
  empty :: Queue a
  join  :: a -> Queue a -> Queue a
さらに構成方法を区別する述語が必要です．
  isEmpty :: Queue a -> Bool
次に既存の空ではないQueueに含まれている要素すべてを知る方法が必要です．
  front :: Queue a -> a
  back  :: Queue a -> Queue a
frontは最初に登録した要素，backは最初に登録した要素を取り除いたQueue
です．この2つがあれば既存の空ではないQueueに含まれるすべての要素を
知ることができます．どちらか一方が欠けるとすべての要素にアクセスでき
ません．

isEmptyに関する公理はemptyで構成されたものかを判定しています．
  isEmpty empty       = True
  isEmpty (join x xq) = False

frontの公理はfrontが最初に登録した要素を示すことを表しています．
  front (join x empty)      = x
  front (join x (join y xq) = front (join y xq)

backの公理はbackが最初に登録した要素を除いたQueueであることを表しています．
  back (join x empty)       = empty
  back (join x (join y xq)) = join x (back (join y xq))

これだけの性質を持っているなら，Queue a，empty，join，isEmpty，front，backの
組み合わせをキュー(FIFO)として使えます．これ以外の性質は必要ないでしょう．

もしこれ以外の性質で，たとえば，frontとbackの関係があるとすれば，その性質は
上の公理から導けるものでしょう．もし導けないような性質が必要であれば確かに
公理に追加する必要がありますが，FIFOとして使うだけ（効率などを考えない）
なら上の公理で十分ですよね．