data Queue a = Queue { _front :: [a], _back :: [a] }

Queue.hs

module Data.Queue
  ( Queue
  , newQueue
  , enqueue
  , dequeue
  , filterQueue
  ) where

-- | A functional queue.
data Queue a = Queue { _front :: [a], _back :: [a] }

newQueue :: Queue a
newQueue = Queue [] []

enqueue :: a -> Queue a -> Queue a
enqueue a (Queue f b) = Queue f (a : b)

dequeue :: Queue a -> Maybe (a, Queue a)
dequeue (Queue []      []) = Nothing
dequeue (Queue []      b ) = dequeue (Queue (reverse b) [])
dequeue (Queue (h : t) b ) = Just (h, Queue t b)

filterQueue :: (a -> Bool) -> Queue a -> Queue a
filterQueue p (Queue f b) = Queue (filter p f) (filter p b)