Purely Functional Data Structures 写経 5.2 Queues

Purely Functional Data Structures

Haskell 写経の続きです。4章は遅延評価の章で、Standard ML は標準が正格評価なので遅延評価についての解説を行っています。
Haskell では遅延評価が標準なのでまるっと飛ばしてしまいます。P42〜P45

Queue のシグネチャから。

class Queue q where
  empty :: q a
  isEmpty :: q a -> Bool
  snoc :: q a -> a -> q a
  head' :: q a -> a
  tail' :: q a -> q a

続いて実装。この章は割合シンプルなので一気に全部いっちゃいます。

data BatchedQueue a = BQ [a] [a] deriving Show

checkf :: [a] -> [a] -> BatchedQueue a
checkf [] r = BQ (reverse r) []
checkf f r = BQ f r

instance Queue BatchedQueue where
  empty = BQ [] []
  isEmpty (BQ f _) = null f

  snoc (BQ f r) x = checkf f $ x : r

  head' (BQ [] _) = error "Empty"
  head' (BQ (x : f) _) = x

  tail' (BQ [] _) = error "Empty"
  tail' (BQ (x : f) r) = checkf f r

ポイントとしては checkf ですね。 snoc と tail' が checkf によって定義されています。